# Резюме

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

- Двоичное дерево — это нелинейная структура данных, отражающая логику «разделяй и властвуй». Каждый узел двоичного дерева содержит значение и два указателя, указывающие на его левый и правый дочерние узлы.
- Для заданного узла дерева дерево, образованное его левым (правым) дочерним узлом и всеми узлами ниже него, называется левым (правым) поддеревом этого узла.
- Основные понятия двоичного дерева включают корневой узел, листовой узел, уровень, степень, ребро, высоту и глубину.
- Операции инициализации двоичного дерева, вставки и удаления узлов аналогичны операциям со связными списками.
- Распространенные типы двоичных деревьев включают идеальное двоичное дерево, совершенное двоичное дерево, полное двоичное дерево и сбалансированное двоичное дерево. Идеальное двоичное дерево является наиболее оптимальным состоянием, а связный список — наихудшим вырожденным состоянием.
- Двоичное дерево может быть представлено с помощью массива, при этом значения узлов и пустые позиции располагаются в порядке обхода по уровням, а указатели реализуются на основе отношений индексов между родительскими и дочерними узлами.
- Обход двоичного дерева по уровням является методом поиска в ширину, который отражает способ обхода «постепенное расширение кольцами», обычно реализуемый с помощью очереди.
- Прямой, симметричный и обратный обходы относятся к поиску в глубину, который отражает способ обхода «сначала до конца, затем возврат и продолжение», обычно реализуемый с помощью рекурсии.
- Двоичное дерево поиска — это эффективная структура данных для поиска элементов, временная сложность операций поиска, вставки и удаления составляет $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$.