7.6 Краткие итоги¶
1. Основные моменты¶
- Двоичное дерево - это нелинейная структура данных, отражающая логику "разделения надвое". Каждый узел двоичного дерева содержит значение и два указателя, которые соответственно ведут к левому и правому дочерним узлам.
- Для любого узла двоичного дерева дерево, образованное его левым (правым) дочерним узлом и всеми нижележащими узлами, называется левым (правым) поддеревом этого узла.
- К связанным с двоичным деревом терминам относятся корневой узел, листовой узел, уровень, степень, ребро, высота, глубина и так далее.
- Инициализация двоичного дерева, вставка узлов и удаление узлов похожи по способу реализации на операции со связным списком.
- К распространенным видам двоичного дерева относятся идеальное двоичное дерево, полное двоичное дерево, строгое двоичное дерево и сбалансированное двоичное дерево. Идеальное двоичное дерево - наиболее желательное состояние, а связный список - худший случай после вырождения.
- Двоичное дерево можно представить массивом: значения узлов и пустые позиции располагаются в порядке обхода по уровням, а связи между родителем и детьми реализуются через отображение индексов.
- Обход двоичного дерева по уровням является методом поиска в ширину; он отражает идею "расширяться слой за слоем наружу" и обычно реализуется через очередь.
- Прямой, симметричный и обратный обходы относятся к поиску в глубину; они отражают идею "сначала дойти до конца, затем откатиться и продолжить" и обычно реализуются рекурсивно.
- Двоичное дерево поиска - это эффективная структура данных для поиска элементов; его поиск, вставка и удаление имеют временную сложность \(O(\log n)\) . Когда двоичное дерево поиска вырождается в связный список, все эти сложности деградируют до \(O(n)\) .
- AVL-дерево, также называемое сбалансированным двоичным деревом поиска, с помощью вращений гарантирует, что после постоянных вставок и удалений узлов дерево остается сбалансированным.
- Вращения AVL-дерева включают правое вращение, левое вращение, сначала правое затем левое и сначала левое затем правое. После вставки или удаления узла AVL-дерево выполняет вращения снизу вверх, чтобы снова восстановить баланс.
2. Q & A¶
Q: Для двоичного дерева, состоящего из одного узла, высота дерева и глубина корня обе равны \(0\) ?
Да, потому что высота и глубина обычно определяются как "число пройденных ребер".
Q: Вставка и удаление в двоичном дереве обычно выполняются в составе набора операций. Что именно означает этот "набор операций"? Можно ли понимать это как освобождение ресурсов у дочерних узлов ресурса?
Возьмем в качестве примера двоичное дерево поиска: операция удаления узла делится на три случая, и каждый из этих случаев требует нескольких последовательных шагов работы с узлами.
Q: Почему у DFS для двоичного дерева есть три порядка: прямой, симметричный и обратный? Для чего они нужны?
Подобно прямому и обратному обходу массива, прямой, симметричный и обратный обходы - это три способа обхода двоичного дерева, с помощью которых можно получить результаты в определенном порядке. Например, в двоичном дереве поиска, где соблюдается отношение значение левого дочернего узла < значение корня < значение правого дочернего узла , если обходить дерево с приоритетом "лево \(\rightarrow\) корень \(\rightarrow\) право", то получится упорядоченная последовательность узлов.
Q: Правое вращение работает с отношениями между node , child и grand_child . А связь между node и его исходным родителем разве не нужно поддерживать? После правого вращения она ведь не оборвется?
На это нужно смотреть с точки зрения рекурсии. В правое вращение right_rotate(root) передается корень поддерева, а затем через return child возвращается корень этого поддерева уже после вращения. Соединение между новым корнем поддерева и его родителем восстанавливается после возврата функции и не входит в обязанности самой операции правого вращения.
Q: В C++ функции делятся на private и public . Какая логика стоит за этим? Почему height() и updateHeight() помещают в разные области видимости?
Главный критерий - область использования метода. Если метод нужен только внутри класса, его следует проектировать как private . Например, самостоятельный вызов updateHeight() пользователем не имеет смысла: это лишь один из шагов внутри вставки или удаления. А height() используется для чтения высоты узла, подобно vector.size() , поэтому его разумно делать public .
Q: Как построить двоичное дерево поиска из набора входных данных? Важен ли выбор корневого узла?
Да, важен. Способ построения дерева уже показан в методе build_tree() в коде двоичного дерева поиска. Что касается выбора корня, обычно входные данные сортируют, берут средний элемент как корень, а затем рекурсивно строят левое и правое поддеревья. Это позволяет в наибольшей степени сохранить баланс дерева.
Q: Нужно ли в Java всегда использовать equals() для сравнения строк?
В Java для базовых типов == используется, чтобы сравнивать, равны ли значения двух переменных. Для ссылочных типов логика у этих двух способов уже разная.
==: сравнивает, ссылаются ли две переменные на один и тот же объект, то есть совпадает ли их адрес в памяти.equals(): сравнивает, равны ли значения двух объектов.
Поэтому если нужно сравнить значения, то следует использовать equals() . Но строки, инициализированные как String a = "hi"; String b = "hi"; , хранятся в строковом пуле констант и указывают на один и тот же объект, поэтому в таком случае a == b тоже может дать истинный результат при сравнении содержимого.
Q: До достижения самого нижнего уровня при обходе в ширину число узлов в очереди равно \(2^h\) ?
Да. Например, для полного двоичного дерева высоты \(h = 2\) общее число узлов равно \(n = 7\) , а число узлов на нижнем уровне равно \(4 = 2^h = (n + 1) / 2\) .