Бинарное дерево поиска (BST, binary search tree) — двоичное дерево, в котором для каждого узла все ключи левого поддерева меньше, а все ключи правого больше. Благодаря этому свойству поиск работает как бинарный: на каждом шаге отбрасывается половина дерева. Реализацию двоичного дерева см. в предыдущей теме.

Поиск ключа `7` в BST: `8 → 3 → 6 → 7`
Поиск ключа 7 в BST: 8 → 3 → 6 → 7

Свойство и поиск

Если ключ меньше узла, идём влево, больше, вправо; равен, нашли; дошли до None, ключа нет. Число шагов ограничено высотой дерева h: O(h).

Вставка

Идём тем же путём, что и при поиске, и на месте None ставим новый лист. Новый ключ всегда становится листом; существующие ключи не двигаются. Дубликаты в этом примере отвергаются (insert возвращает False).

python
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None
        self.size = 0

    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
            self.size = 1
            return True
        node = self.root
        while True:
            if key < node.key:
                if node.left is None:
                    node.left = Node(key)
                    break
                node = node.left
            elif key > node.key:
                if node.right is None:
                    node.right = Node(key)
                    break
                node = node.right
            else:
                return False
        self.size += 1
        return True