Деревья представляют собой иерархическую структуру данных, аналогичную генеалогическому древу, где элементы, называемые узлами, связаны отношениями родитель-потомок. Верхушку структуры занимает корневой узел, от которого отходят ветви к потомкам. Узлы, не имеющие потомков, называются листьями. Такая организация позволяет эффективно представлять данные с вложенными отношениями.
Примером может служить простое дерево:
10
/ \
5 15
/ \
2 7
Здесь узел со значением 10 является корнем. У него два потомка — узлы 5 и 15. Узел 5, в свою очередь, является родителем для узлов 2 и 7, которые являются листьями. Узел 15 также является листом в этой структуре.
Особым и очень полезным видом дерева является двоичное дерево поиска, или BST. «Двоичное» означает, что каждый узел может иметь не более двух потомков — левого и правого. Ключевая же особенность «дерева поиска» заключается в строгом правиле упорядочивания элементов. Для любого узла все значения в его левом поддереве должны быть меньше его собственного значения, а все значения в правом поддереве — больше. Это свойство делает структуру идеальной для эффективного поиска.
Рассмотрим проверку правила на примере:
10
/ \
5 15
/ \
2 7
Для узла 10: все значения слева (5, 2, 7) меньше 10, а значение справа (15) больше. Для узла 5: значение слева (2) меньше 5, а значение справа (7) больше. Это правило соблюдено для всех узлов, что подтверждает, что дерево является корректным BST.
Главное преимущество двоичного дерева поиска — скорость. Благодаря упорядоченности, алгоритм поиска, начиная с корня, может на каждом шаге отбрасывать половину оставшегося дерева, двигаясь либо влево, либо вправо. Например, чтобы найти число 7 в приведенном дереве, потребуется всего три шага: сравнить с 10 (7<10, идем влево), сравнить с 5 (7>5, идем вправо), сравнить с 7 (найдено). Это значительно быстрее, чем проверять все пять элементов подряд.
Реализация BST начинается с создания базового элемента — узла. На языке Python это выглядит следующим образом:
class TreeNode:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
Этот класс создает объект-узел, который хранит значение
key и содержит ссылки на левого и правого потомка, изначально пустые. Например, создание корневого узла root = TreeNode(10) дает структуру с одним значением и двумя пустыми указателями.Для добавления новых элементов в дерево с сохранением его основного свойства используется рекурсивная функция вставки.
def insert(root, key):
if root is None:
return TreeNode(key)
else:
if root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root
Алгоритм работает так: начиная с корня, значение для вставки сравнивается с текущим узлом. Если оно больше, рекурсивный вызов идет в правое поддерево, если меньше или равно — в левое. Этот процесс продолжается до тех пор, пока не будет обнаружено пустое место (значение
None), куда и помещается новый узел. Визуально последовательная вставка чисел 10, 5, 15, 2, 7 формирует именно то дерево, что было представлено в примерах выше.Одной из фундаментальных операций над деревьями является обход, то есть посещение всех узлов в определенном порядке. Симметричный обход, или inorder traversal, посещает узлы в последовательности: левое поддерево, текущий узел, правое поддерево.
def inorder_traversal(root):
res = []
if root:
res = inorder_traversal(root.left)
res.append(root.val)
res = res + inorder_traversal(root.right)
return res
Примененный к BST, такой обход возвращает все значения в отсортированном по возрастанию виде, что является прямым следствием правила упорядочивания. Для нашего примера вызов
print(inorder_traversal(root)) вернет список [2, 5, 7, 10, 15].