Простыми словами: Бинарное дерево поиска

Бинарное дерево поиска (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

Давайте проверим ваши знания работы бинарного дерева поиска. Посмотрите на изображение и ответьте на вопрос ниже.

#викторина #bst