hello-algo/ru/docs/chapter_tree/summary.md

Резюме

Основные моменты

• Двоичное дерево — это нелинейная структура данных, отражающая логику «разделяй и властвуй». Каждый узел двоичного дерева содержит значение и два указателя, указывающие на его левый и правый дочерние узлы.
• Для заданного узла дерева дерево, образованное его левым (правым) дочерним узлом и всеми узлами ниже него, называется левым (правым) поддеревом этого узла.
• Основные понятия двоичного дерева включают корневой узел, листовой узел, уровень, степень, ребро, высоту и глубину.
• Операции инициализации двоичного дерева, вставки и удаления узлов аналогичны операциям со связными списками.
• Распространенные типы двоичных деревьев включают идеальное двоичное дерево, совершенное двоичное дерево, полное двоичное дерево и сбалансированное двоичное дерево. Идеальное двоичное дерево является наиболее оптимальным состоянием, а связный список — наихудшим вырожденным состоянием.
• Двоичное дерево может быть представлено с помощью массива, при этом значения узлов и пустые позиции располагаются в порядке обхода по уровням, а указатели реализуются на основе отношений индексов между родительскими и дочерними узлами.
• Обход двоичного дерева по уровням является методом поиска в ширину, который отражает способ обхода «постепенное расширение кольцами», обычно реализуемый с помощью очереди.
• Прямой, симметричный и обратный обходы относятся к поиску в глубину, который отражает способ обхода «сначала до конца, затем возврат и продолжение», обычно реализуемый с помощью рекурсии.
• Двоичное дерево поиска — это эффективная структура данных для поиска элементов, временная сложность операций поиска, вставки и удаления составляет O(\log n). Когда двоичное дерево поиска вырождается в связный список, временная сложность всех операций ухудшается до O(n).
• AVL-дерево, также называемое сбалансированным двоичным деревом поиска, обеспечивает сохранение баланса дерева после непрерывных операций вставки и удаления узлов с помощью операций поворота.
• Операции поворота AVL-дерева включают правый поворот, левый поворот, сначала правый затем левый поворот, сначала левый затем правый поворот. После вставки или удаления узла AVL-дерево выполняет операции поворота снизу вверх, чтобы восстановить баланс дерева.

Вопросы и ответы

В: Для двоичного дерева с одним узлом высота дерева и глубина корневого узла равны 0?

Да, поскольку высота и глубина обычно определяются как «количество пройденных ребер».

В: Вставка и удаление в двоичном дереве обычно выполняются набором операций. Что означает «набор операций»? Можно ли понимать это как освобождение ресурсов дочерних узлов?

Возьмем в качестве примера двоичное дерево поиска: операция удаления узла требует обработки трех различных случаев, и в каждом случае необходимо выполнить несколько шагов операций с узлами.

В: Почему обход DFS двоичного дерева имеет три порядка: прямой, симметричный и обратный, и для чего они используются?

Подобно прямому и обратному обходу массива, прямой, симметричный и обратный обходы — это три метода обхода двоичного дерева, с помощью которых мы можем получить результат обхода в определенном порядке. Например, в двоичном дереве поиска, поскольку размер узлов удовлетворяет условию значение левого дочернего узла < значение корневого узла < значение правого дочернего узла, если мы обходим дерево в приоритете «левый \rightarrow корень \rightarrow правый», мы можем получить упорядоченную последовательность узлов.

В: Операция правого поворота обрабатывает отношения между несбалансированными узлами node, child, grand_child. Нужно ли поддерживать связь между родительским узлом node и самим node? Не разорвется ли она после операции правого поворота?

Нужно рассматривать эту проблему с точки зрения рекурсии. Операция правого поворота right_rotate(root) принимает корневой узел поддерева, и в конце return child возвращает корневой узел поддерева после поворота. Связь между корневым узлом поддерева и его родительским узлом устанавливается после возврата из функции и не входит в область поддержки операции правого поворота.

В: В C++ функции разделены на private и public. Какие соображения здесь учитываются? Почему функции height() и updateHeight() размещены в public и private соответственно?

В основном это зависит от области использования метода. Если метод используется только внутри класса, то он проектируется как private. Например, отдельный вызов updateHeight() пользователем не имеет смысла, это всего лишь один из шагов в операциях вставки и удаления. А height() — это доступ к высоте узла, аналогично vector.size(), поэтому он установлен как public для удобства использования.

В: Как построить двоичное дерево поиска из набора входных данных? Важен ли выбор корневого узла?

Да, метод построения дерева уже представлен в методе build_tree() в коде двоичного дерева поиска. Что касается выбора корневого узла, мы обычно сортируем входные данные, затем выбираем средний элемент в качестве корневого узла и рекурсивно строим левое и правое поддеревья. Это позволяет максимально обеспечить сбалансированность дерева.

В: В Java обязательно ли использовать метод equals() для сравнения строк?

В Java для базовых типов данных == используется для сравнения значений двух переменных. Для ссылочных типов эти два символа работают по-разному.

• ==: используется для сравнения того, указывают ли две переменные на один и тот же объект, т. е. одинаковы ли их позиции в памяти.
• equals(): используется для сравнения значений двух объектов.

Поэтому, если нужно сравнить значения, следует использовать equals(). Однако строки, инициализированные через String a = "hi"; String b = "hi";, хранятся в пуле строковых констант и указывают на один и тот же объект, поэтому также можно использовать a == b для сравнения содержимого двух строк.

В: До достижения самого нижнего уровня при обходе в ширину количество узлов в очереди равно 2^h?

Да, например, для полного двоичного дерева высоты h = 2 общее количество узлов n = 7, тогда количество узлов на нижнем уровне 4 = 2^h = (n + 1) / 2.