Бинарное дерево поиска (Binary Search Tree, или просто BST) — это структура данных, которая помогает легко и быстро находить, добавлять и удалять элементы. Давайте разберёмся, что это такое и как с ним работать, на простых примерах.
Представьте себе дерево. У каждого узла в этом дереве есть:
— значение (например, число);
— ссылка на левую «веточку» (левого ребенка);
— ссылка на правую «веточку» (правого ребенка).
Правило у этого дерева такое:
— все значения в левом поддереве меньше, чем значение в узле;
— все значения в правом поддереве больше, чем значение в узле.
Простейшие операции с BST
Вставка элемента
Если вы хотите добавить элемент в дерево, вы начинаете с самого верха. Сравниваете новое значение с корнем:
— если оно меньше, переходите влево;
— если больше, переходите вправо;
— повторяете, пока не найдете пустую коробочку (место), и вы поместите туда новое значение.
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
Поиск элемента
Когда вы хотите найти элемент, вы снова начинаете с корня и сравниваете:
— если нашли — отлично, элемент найден!
— если меньше, идете налево.
— если больше, идете направо.
Повторяете, пока не найдете элемент или не убедитесь, что его нет в дереве.
def search(root, key):
if root is None or root.key == key:
return root
if key < root.key:
return search(root.left, key)
return search(root.right, key)
Удаление элемента
Удаление элемента немного сложнее, потому что есть три варианта:
— элемент — это лист (нет детей). Просто удаляем его;
— элемент имеет одного ребенка. Тогда просто заменяем его этим ребенком;
— элемент имеет двух детей. В этом случае мы находим минимальный элемент в правом поддереве и заменяем удаляемый элемент на него.
def deleteNode(root, key):
if root is None:
return root
if key < root.key:
root.left = deleteNode(root.left, key)
elif key > root.key:
root.right = deleteNode(root.right, key)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left
temp = minValueNode(root.right)
root.key = temp.key
root.right = deleteNode(root.right, temp.key)
return root
def minValueNode(node):
current = node
while current.left is not None:
current = current.left
return current
Обход дерева
Обход означает посещение всех узлов в дереве. Существует несколько способов делать это:
1. In-order (Левый-Корень-Правый): посещаем сначала левое поддерево, потом текущий узел, потом правое поддерево.
2. Pre-order (Корень-Левый-Правый): посещаем сначала текущий узел, потом левое поддерево, потом правое поддерево.
3. Post-order (Левый-Правый-Корень): посещаем сначала левое поддерево, потом правое поддерево, потом текущий узел.
Пример in-order обхода:
def inorder(root):
if root:
inorder(root.left)
print(root.key, end=' ')
inorder(root.right)
Давайте резюмируем. Бинарное дерево поиска — это отличный инструмент для быстрого и эффективного управления данными. С его помощью легко найти, добавить или удалить элемент, благодаря чёткой структуре и правилам. Теперь, когда вы знаете, что оно из себя представляет, сможете без труда использовать его в своих проектах
#простымисловами #bst