Бинарные деревья поиска
Бинарные деревья поиска
- Бинарное дерево поиска (BST) хранит значения так, чтобы они оставались отсортированными и были быстрыми для поиска.
- Каждый узел содержит значение и ссылки на до двух детей: левый
leftи правыйright. - Верхний узел — это корень. Узел без детей — это лист.
Правило BST
- Для каждого узла: всё в его левом поддереве меньше, всё в правом — больше или равно (в этом уроке равные значения отправляются вправо).
- Это одно правило позволяет найти значение, двигаясь влево или вправо — никогда в обе стороны.
5
/ \
3 8
/ \ \
1 4 9
left < node <= right, at every node
Узел
- Мы моделируем узел как небольшой объект со
value,leftиright. - Новый узел еще не имеет детей, поэтому
leftиrightначинаются какNone.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
n = Node(5)
print(n.value) # 5
print(n.left) # None
Вставка значения
- Начните с корня. Если дерево пусто, новое значение становится корнем.
- Если значение меньше текущего узла, идите влево; иначе идите вправо.
- Повторяйте, пока не достигнете пустого места, и поместите туда новый узел.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
root = None
for v in [5, 3, 8, 1]:
root = insert(root, v)
print(root.value) # 5
print(root.left.value) # 3
print(root.right.value) # 8
Обход in-order дает отсортированный порядок
- Обход в порядке посещает: левое поддерево, затем узел, затем правое поддерево.
- Благодаря правилу BST это посещает значения в сортированном порядке — бесплатно.
- Это естественно рекурсивно: обходите влево, берите значение, обходите вправо.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def in_order(root):
if root is None:
return []
return in_order(root.left) + [root.value] + in_order(root.right)
root = None
for v in [5, 3, 8, 1, 4]:
root = insert(root, v)
print(in_order(root)) # [1, 3, 4, 5, 8]
Поиск быстрый
- Чтобы найти значение, сравните его с узлом, затем перейдите влево или вправо — на каждом шаге пропускайте половину дерева.
- В сбалансированном дереве это занимает около
O(log n)шагов, что намного быстрее, чем перебор списка. - Плохо отформатированное дерево (значения, вставленные уже в отсортированном виде), может деградировать до линии —
O(n).
Распространенные ошибки
- В бинарном дереве поиска: левый ребёнок < узел <= правый ребёнок (равные значения здесь уходят вправо).
- Несбалансированное дерево теряет преимущество в скорости.
Теперь попробуйте сами
- Постройте три основных операции:
insert,in_orderиcontains. - Класс
Node(и рабочая функцияinsert, где она нужна) предоставляется. - Нажмите Проверить ответ, чтобы протестировать это на нескольких деревьях.
Поиск в BST
Левое меньше, правое больше — поэтому каждый шаг пропускает половину дерева.
Сложность 5/5 · 400 монет + небольшой бонус за первое завершение сегодня
Класс Node предоставлен. Напишите insert(root, value), которая добавляет ⟨value⟩ в BST и возвращает корень. Если ⟨root⟩ равно ⟨None⟩, верните новый ⟨Node(value)⟩. Если ⟨value < root.value⟩ нужно пойти влево, иначе направо — и переприсвойте этого потомка результату рекурсивного вставки.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 5/5 · 400 монет + небольшой бонус за первое завершение сегодня
Функция Node и рабочая функция insert предоставлены. Напишите in_order(root), которая возвращает список значений из инфиксного обхода: левое поддерево, затем значение текущего узла, затем правое поддерево. Благодаря правилу BST список получается отсортированным. Пустое дерево (None) дает [].
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 5/5 · 400 монет + небольшой бонус за первое завершение сегодня
Предоставлены Node и рабочая insert. Напишите contains(root, value), который возвращает True, если ⟨value⟩ находится в дереве, иначе False. Используйте правило бинарного дерева поиска: если оно равно этому узлу, верните True; если оно меньше, ищите слева, иначе ищите справа; пустая ветвь (None) означает, что элемента нет.
Нажмите Запустить, чтобы увидеть результат здесь.