Двоичное дерево поиска (BST)

Двоичное дерево поиска хранит ключи так, что в каждом узле все ключи слева меньше, а справа больше. Это даёт упорядоченный обход и бинарный поиск по структуре.

Сложность: поиск, вставка, удаление — O(log n) в среднем для сбалансированного дерева, но O(n) в худшем случае, если дерево выродилось в список. Для гарантии баланса используют AVL или красно-чёрные деревья. Память: O(n).

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