[Powered by Google Translate] Как бы вы представляете всех членов вашей семьи в компьютере?
Мы могли бы просто использовать список,
но есть четкая иерархия здесь.
>> Скажем, мы начинаем с вашей прабабушки, Alice.
Она имеет 2 сыновей, Боба
и ваши дедушки, Чарли.
Чарли имеет 3 детей,
Ваш дядя, Дэйв, твоя тетя, Ева, и ваш отец, Фред.
Вы единственный ребенок в семье Фреда.
>> Почему организацию членов вашей семьи, таким образом,
быть лучше, чем простое представление списка?
Одной из причин является то, что эта иерархическая структура,
называют «деревом», содержит больше информации, чем простой список.
Мы знаем, что семейные отношения между всеми
только путем изучения дерева.
Кроме того, это может ускорить
справочной время чрезвычайно, если дерево сортировки данных.
>> Мы не можем воспользоваться тем, что здесь, но мы видим пример этому в ближайшее время.
Каждый человек представляет собой узел на дереве.
Узлы могут иметь дочерние узлы
а также родительского узла.
Эти технические термины,
даже при использовании деревьев для вещей, кроме семьи.
Узлу Алисы имеет 2 детей, и нет родителей,
в то время как узел Чарли имеет 3 детей и 1 родитель.
>> Листовым узлом является тот, который не имеет детей
по внешнему краю дерева.
Самый верхний узел дерева, корневой узел,
не имеет родителя.
>> Бинарное дерево является специфический тип дерева,
, в которой каждый узел имеет, самое большее, 2 детей.
Вот структура узла в бинарном дереве в C.
Каждый узел имеет некоторые связанные с ним данные
и 2 указатели на другие узлы.
>> В наше генеалогическое дерево,
связанные с ним данные звали каждого человека.
Вот она Int, хотя это может быть что угодно.
Как выяснилось,
бинарное дерево не было бы хорошее представление для семьи,
так как люди часто имеют более 2 детей.
>> Бинарное дерево поиска
это особый, упорядоченный тип бинарного дерева
, что позволяет нам смотреть на значениях быстро.
Вы, возможно, заметили,
что каждый узел под корень дерева
корень другого дерева, называемого "поддерево".
Здесь, корень дерева 6,
и ее ребенка, 2, является корнем поддерева.
>> В бинарном дереве поиска
все значения узла правого поддерева
больше, чем значение узла. Здесь: 6.
Ну, значения в левом поддереве узла
меньше, чем значение узла.
Если нужно обрабатывать повторяющиеся значения,
мы можем изменить любой из тех, свободные неравенство,
то есть одинаковые значения может упасть либо на левый или правый,
тех пор, как мы последовательны об этом всем.
Это дерево бинарное дерево поиска
потому что он следует этим правилам.
>> Вот как это будет выглядеть, если мы повернули всех узлов в структурах C.
Обратите внимание, что если ребенок отсутствует,
указатель является нулевым.
Как мы проверяем, если 7 в дереве?
Мы начинаем в корне.
Семь больше 6, так что если это в дерево, оно должно быть с правой стороны.
Тогда, это меньше, чем 8, поэтому он должен быть слева.
Здесь мы нашли 7.
Сейчас мы проверим на 5.
Пять меньше, чем 6, поэтому он должен быть слева.
Пять больше 2,
поэтому он должен быть правильным,
и это также больше 4, поэтому он должен быть еще раз направо.
Тем не менее, нет ни одного ребенка здесь.
Указатель является нулевым.
Это означает, что 5 не в наших деревьев.
>> Мы можем искать двоичного дерева с помощью следующего кода:
На каждом узле, мы проверяем, если мы нашли
Значение, которое мы ищем.
Если мы не найдем его, мы определить, если она должна быть
на левый или правый и убедиться, что поддерево.
Этот цикл будет продолжаться вниз по дереву
пока не будет дочерний узел на левом или правом.
>> Помните, что 5 не был в дерево.
Как мы можем вставить его?
Этот процесс похож на поиск.
Мы итерацию по дереву, начиная с 6,
слева 2,
Право 4,
и еще раз направо, а 4 не имеет ребенком на этой стороне.
Это будет новая должность на 5,
и он начнет без детей.
>> Как быстро операций на бинарном дереве поиска?
Помните, что Bigohnotation стремится обеспечить верхней границы.
В худшем случае,
наше дерево может быть просто связанный список
Это означает, что вставки, удаления и поиска
может занять время, пропорциональное числу узлов в дереве.
Это O (N).
>> Например, следующее является действительным бинарное дерево поиска.
Однако, если мы пытаемся найти 9,
мы должны пройти каждом узле.
Это не лучше, чем связанный список.
В идеале, мы хотели бы, каждый узел
наши бинарное дерево поиска, чтобы иметь 2 детей.
Таким образом, вставка, удаление и поиск
бы, на худой конец, O (журнал N) времени.
Дерево, прежде чем могла бы быть более сбалансированной,
как это.
Теперь, глядя любое значение имеет, самое большее, 3 шага.
Это дерево является сбалансированным,
значение, которое имеет минимальную глубину
по сравнению с числом узлов.
>> Ищет значение в бинарное дерево
похоже на двоичный поиск в отсортированном массиве.
В самом деле, если нам не нужно вставлять или удалять элементы,
они ведут себя точно так же.
Тем не менее, структура дерева лучше
для обработки вставок и удалений
>> Меня зовут Bannus Ван-дер-Kloot.
Это CS50.