BST время: эффективные алгоритмы, решение задач, оптимизация выполнения

BST (Binary Search Tree) - это структура данных, в которой каждый узел имеет максимум двух потомков. Ключи узлов в BST удовлетворяют свойству: ключ в левом поддереве меньше текущего узла, а ключ в правом поддереве больше текущего узла.

Время выполнения операций на BST зависит от его балансировки. Балансировка BST означает, что разница в высоте между левым и правым поддеревьями не превышает 1. Если BST сбалансирован, то его операции выполняются за O(log n) времени, где n - количество узлов в дереве. Однако, несбалансированное BST может иметь высоту n, и операции на нем выполняются за O(n) времени.

Пример кода для реализации BST и основных операций:

python
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
class BST:
    def __init__(self):
        self.root = None
    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
        else:
            self._insert_recursive(self.root, key)
    def _insert_recursive(self, root, key):
        if key < root.key:
            if root.left is None:
                root.left = Node(key)
            else:
                self._insert_recursive(root.left, key)
        else:
            if root.right is None:
                root.right = Node(key)
            else:
                self._insert_recursive(root.right, key)
    def search(self, key):
        return self._search_recursive(self.root, key)
    def _search_recursive(self, root, key):
        if root is None or root.key == key:
            return root
        elif key < root.key:
            return self._search_recursive(root.left, key)
        else:
            return self._search_recursive(root.right, key)
    def delete(self, key):
        self.root = self._delete_recursive(self.root, key)
    def _delete_recursive(self, root, key):
        if root is None:
            return root
        if key < root.key:
            root.left = self._delete_recursive(root.left, key)
        elif key > root.key:
            root.right = self._delete_recursive(root.right, key)
        else:
            if root.left is None:
                return root.right
            elif root.right is None:
                return root.left
            else:
                min_key = self._find_min_key(root.right)
                root.key = min_key
                root.right = self._delete_recursive(root.right, min_key)
        return root
    def _find_min_key(self, root):
        while root.left is not None:
            root = root.left
        return root.key

Пример использования:

python
bst = BST()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(2)
bst.insert(4)
print(bst.search(4))  # Output: Node object with key=4
bst.delete(5)
print(bst.search(5))  # Output: None

В приведенном коде реализованы основные операции на BST, такие как вставка, поиск и удаление. Вставка и поиск выполняются за O(log n) в случае сбалансированного дерева, а удаление - также за O(log n), но считается немного более сложной операцией.