Узел в двоичном дереве (или как его еще называют бинарном) имеет не более двух дочерних элементов: левого и правого элемента. Это определение позволяет вам писать алгоритмы для более эффективной вставки, поиска и удаления узлов.
Двоичное дерево поиска (binary search tree — BST) — это тоже двоичное дерево.
Основное отличие состоит в том, что BST позволяет хранить отсортированные узлы с меньшим значением слева и узлы с большим значением справа.
Обход дерева (Traverse) — это процесс посещения всех узлов дерева и выполнения операции на каждом узле.
Существует три общих подхода:
- Прямой (in-order);
- Симметричный или поперечный (pre-order);
- В обратном порядке (post-order).
При прямом обходе будут посещаться все узлы в порядке возрастания, начиная с указанного узла (хотя это и необязательно), и выполнять заданную функцию обратного вызова callback (также необязательно).
При симметричном обходе посещаются каждый узел до его потомков.
При обходе в обратном порядке посещаются узлы после посещения его потомков.
Метод удаления является наиболее сложным. Его сложность обусловлена различными сценариями, которые нам нужны.
В начале мы ищем соответствующий узел, который нужно удалить, а потом есть три сценария, которые мы рассмотрим более подробно ниже.
Первый сценарий включает в себя крайний узел (leaf node), то есть у которого нет левого или правого дочернего элемента. В этом случае нам нужно будет удалить узел, присвоив ему значение null. Однако не стоит забывать, что мы также должны позаботиться о ссылках из родительского узла.
Второй сценарий включает в себя узел, который имеет левый или правый дочерний узел. Как вы можете видеть на диаграмме ниже, нам нужно пропустить соответствующий узел и назначить родительский указатель на дочерний узел:
Третий и последний сценарий включает в себя узел с двумя дочерними элементами. Чтобы удалить такой узел, нужно выполнить следующие действия:
- Как только вы найдете узел, который нужно удалить, найдите минимальный узел из его правого края поддерева (см. заштрихованную область на диаграмме ниже).
- Далее вы можете обновить значение узла ключом минимального узла из его правого поддерева. Этим действием вы заменяете ключ узла, что означает, что он будет удален.
- Теперь у вас есть два узла в дереве с одним и тем же ключом, что не правильно. Таким образом, нужно удалить минимальный узел из правого поддерева, поскольку вы переместили его на место удаленного узла.
- Наконец, нужно вернуть обновленную ссылку на узел его родителю.
