Binary search trees

English

A binary search tree (BST) stores values so they stay sorted and are fast to find.
Each node holds a value and links to up to two children: a left and a right.
The top node is the root. A node with no children is a leaf.

Русский

Бинарные деревья поиска

Бинарное дерево поиска (BST) хранит значения так, чтобы они оставались отсортированными и были быстрыми для поиска.
Каждый узел содержит значение и ссылки на до двух детей: левый left и правый right.
Верхний узел — это корень. Узел без детей — это лист.

English

The BST rule

For every node: everything in its left subtree is smaller, everything in its right is larger.
This one rule is what lets you find a value by going left or right — never both.

Русский

Правило BST

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

        5
       / \
      3   8
     / \   \
    1   4   9

left < node < right, at every node

English

A node

We model a node as a small object with a value, a left, and a right.
A brand-new node has no children yet, so left and right start as None.

Русский

Узел

Мы моделируем узел как небольшой объект со value, left и right.
Новый узел еще не имеет детей, поэтому left и right начинаются как None.

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

n = Node(5)
print(n.value)   # 5
print(n.left)    # None

English

Inserting a value

Start at the root. If the tree is empty, the new value becomes the root.
If the value is smaller than the current node, go left; otherwise go right.
Repeat until you reach an empty spot, and put the new node there.

Русский

Вставка значения

Начните с корня. Если дерево пусто, новое значение становится корнем.
Если значение меньше текущего узла, идите влево; иначе идите вправо.
Повторяйте, пока не достигнете пустого места, и поместите туда новый узел.

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

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

root = None
for v in [5, 3, 8, 1]:
    root = insert(root, v)
print(root.value)            # 5
print(root.left.value)       # 3
print(root.right.value)      # 8

English

In-order traversal gives sorted order

In-order traversal visits: the left subtree, then the node, then the right subtree.
Because of the BST rule, this visits the values in sorted order — for free.
It is naturally recursive: traverse left, take the value, traverse right.

Русский

Обход in-order дает отсортированный порядок

Обход в порядке посещает: левое поддерево, затем узел, затем правое поддерево.
Благодаря правилу BST это посещает значения в сортированном порядке — бесплатно.
Это естественно рекурсивно: обходите влево, берите значение, обходите вправо.

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

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

def in_order(root):
    if root is None:
        return []
    return in_order(root.left) + [root.value] + in_order(root.right)

root = None
for v in [5, 3, 8, 1, 4]:
    root = insert(root, v)
print(in_order(root))   # [1, 3, 4, 5, 8]

English

Searching is fast

To find a value, compare it with the node, then go left or right — skipping half the tree each step.
In a balanced tree this takes about O(log n) steps, much faster than scanning a list.
A badly-shaped tree (values inserted already sorted) can degrade to a line — O(n).

Русский

Поиск быстрый

Чтобы найти значение, сравните его с узлом, затем перейдите влево или вправо — на каждом шаге пропускайте половину дерева.
В сбалансированном дереве это занимает около O(log n) шагов, что намного быстрее, чем перебор списка.
Плохо отформатированное дерево (значения, вставленные уже в отсортированном виде), может деградировать до линии — O(n).

English

Common mistakes

In a binary search tree: left child < node < right child.
An unbalanced tree loses the speed advantage.

Русский

Распространенные ошибки

В бинарном дереве поиска: левый потомок < узел < правый потомок.
Несбалансированное дерево теряет преимущество в скорости.

English

Now you try

Build the three core operations: insert, in_order, and contains.
The Node class (and a working insert, where you need it) is provided.
Press Check answer to test it on several trees.

Русский

Теперь попробуйте сами

Постройте три основных операции: insert, in_order и contains.
Класс Node (и рабочая функция insert, где она нужна) предоставляется.
Нажмите Проверить ответ, чтобы протестировать это на нескольких деревьях.

Explore · ⁨Исследовать⁩

Searching a BST

Left is smaller, right is bigger — so each step skips half the tree.

The Node class is provided. Write insert(root, value) that adds value to the BST and returns the root. If root is None, return a new Node(value). If value < root.value go left, otherwise go right — and reassign that child to the result of inserting into it.

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

def insert(root, value):
    # Empty -> new Node. Else go left if smaller, right otherwise. Return root.
    pass

Click Run to see the output here. · ⁨Нажмите Запустить, чтобы увидеть результат здесь.⁩

Node and a working insert are provided. Write in_order(root) that returns a list of the values from an in-order traversal: left subtree, then this node's value, then right subtree. Thanks to the BST rule the list comes out sorted. An empty tree (None) gives [].

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

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

def in_order(root):
    # Return left values + [this value] + right values; [] when root is None
    pass

Click Run to see the output here. · ⁨Нажмите Запустить, чтобы увидеть результат здесь.⁩

Node and a working insert are provided. Write contains(root, value) that returns True if value is in the tree, else False. Use the BST rule: if it equals this node return True; if it is smaller search left, otherwise search right; an empty branch (None) means it is not there.

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

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

def contains(root, value):
    # None -> False. Equal -> True. Smaller -> search left, else search right.
    pass

Click Run to see the output here. · ⁨Нажмите Запустить, чтобы увидеть результат здесь.⁩

Binary search trees