До появления мобильных телефонов и Интернета мы использовали такие вещи, как телефонные книги. Большинство из вас, вероятно, знают, что такое телефонная книга, но на всякий случай: телефонная книга — это каталог, в котором предприятия платят за перечисление своих телефонных номеров, обычно упорядоченных по типу бизнеса, а затем в алфавитном порядке в каждом разделе.
Допустим, вы узнали от друга, что он пользовался услугой под названием «Roach-B-Gone», но забыл номер. Поскольку на дворе 1991 год, мы должны заглянуть в телефонную книгу. Мы открываем его примерно на полпути и видим список «Ларри Слесарь». Мы находимся в разделе «Слесарь», и нам нужно попасть в раздел «Борьба с вредителями». Мы знаем, что нам нужен поиск в правой половине книги, поэтому мы фактически удаляем всю левую половину книги.
Если мы вернемся к середине правой половины книги, мы окажемся в разделе «Буксировка», где мы можем удалить все после него, поскольку наша компания теперь находится слева от того места, где мы находимся. Если мы продолжим этот процесс, в конце концов мы достигнем «Roach-B-Gone». Мы только что использовали логику бинарного дерева поиска.
Основы дерева
Деревья — это структуры данных, в которых используется иерархия, соединяющая узлы друг с другом. Они нелинейны и могут хранить данные любого типа. Деревья начинаются в корневом узле (выше корня 2), который может быть связан со многими различными узлами и формировать множество путей. Деревья следуют нисходящей иерархии, где узел, указывающий на другой узел, называется родительским, а узел, на который он указывает, является дочерним. В приведенном выше примере2 является родительским для дочерних элементов 7 и 5, а 5 является родительским для дочернего узла 9. Дочерние узлы 7 — (2,10,6) — называются братья и сестры, поскольку у них один и тот же родитель. узел 4 называется листом, поскольку у него нет потомков.
Некоторыми распространенными примерами деревьев являются HTML DOM или структуры файлов и папок на компьютере.
Бинарные деревья поиска
Двоичное дерево поиска — это структура данных, которая организует наши данные в определенной конфигурации, позволяя нам быстро вставлять и искать наши данные. Дерево в приведенном выше примере НЕ является допустимым двоичным деревом поиска. Бинарные деревья поиска следуют двум конкретным правилам:
- Каждый родительский узел может иметь максимум 2 дочерних узла.
- Левый потомок родительского узла должен быть меньше родителя, а правый потомок должен быть больше. Для этого мы будем использовать числа, но обратите внимание, что это также можно использовать со строками, учитывая их алфавитный порядок.
Выполнение
Мы начнем с реализации класса Node, который по определению имеет левую и правую ссылки на другие узлы, а затем реализуем insert и find.
Вы заметите, что я использовал рекурсию для реализации методов find и insert — вы также можете использовать итерацию, если хотите.
Сложность времени
Двоичные деревья поиска в лучшем случае могут иметь временную сложность O(log n) для вставки и поиска. Однако это не гарантируется, поскольку не все бинарные деревья поиска идеально отсортированы.
В качестве примера рассмотрим односвязный список. Односвязный список, упорядоченный от наименьшего к наибольшему, технически является двоичным деревом поиска. Корень — это наименьшее значение, а все «правильные» узлы больше. Если бы нам нужно было вставить новое наибольшее число или найти наибольшее число, нам нужно было бы выполнить поиск по каждому отдельному узлу. В этом случае наша временная сложность будет O(n). При реализации этих деревьев важно выбрать узел рядом с серединой ваших данных, чтобы ваше дерево работало наиболее эффективно.
