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

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

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

Пример BST и порядок in-order обхода: 1, 3, 6, 8, 10, 13, 14

Реализация BST

type TreeNode struct {
    Value       int
    Left, Right *TreeNode
}

type BST struct {
    Root *TreeNode
}

func (t *BST) Insert(val int) {
    t.Root = insert(t.Root, val)
}

func insert(node *TreeNode, val int) *TreeNode {
    if node == nil {
        return &TreeNode{Value: val}
    }
    if val < node.Value {
        node.Left = insert(node.Left, val)
    } else if val > node.Value {
        node.Right = insert(node.Right, val)
    }
    return node
}

func (t *BST) Search(val int) bool {
    return search(t.Root, val)
}

func search(node *TreeNode, val int) bool {
    if node == nil {
        return false
    }
    switch {
    case val == node.Value:
        return true
    case val < node.Value:
        return search(node.Left, val)
    default:
        return search(node.Right, val)
    }
}
<?php
declare(strict_types=1);

final class TreeNode
{
    public ?TreeNode $left = null;
    public ?TreeNode $right = null;

    public function __construct(public readonly int $value) {}
}

final class BinarySearchTree
{
    public ?TreeNode $root = null;

    public function insert(int $val): void
    {
        $this->root = $this->insertNode($this->root, $val);
    }

    private function insertNode(?TreeNode $node, int $val): TreeNode
    {
        if ($node === null) {
            return new TreeNode($val);
        }

        if ($val < $node->value) {
            $node->left = $this->insertNode($node->left, $val);
        } elseif ($val > $node->value) {
            $node->right = $this->insertNode($node->right, $val);
        }
        return $node;
    }

    public function search(int $val): bool
    {
        return $this->searchNode($this->root, $val);
    }

    private function searchNode(?TreeNode $node, int $val): bool
    {
        if ($node === null) {
            return false;
        }
        return match (true) {
            $val === $node->value => true,
            $val < $node->value => $this->searchNode($node->left, $val),
            default => $this->searchNode($node->right, $val),
        };
    }
}

В PHP native бинарного дерева нет - пишем руками. Структура TreeNode тривиальна, поведение - в отдельном BinarySearchTree.

from dataclasses import dataclass


@dataclass(slots=True)
class TreeNode:
    value: int
    left: "TreeNode | None" = None
    right: "TreeNode | None" = None


class BST:
    def __init__(self) -> None:
        self.root: TreeNode | None = None

    def insert(self, val: int) -> None:
        self.root = _insert(self.root, val)

    def search(self, val: int) -> bool:
        return _search(self.root, val)


def _insert(node: TreeNode | None, val: int) -> TreeNode:
    if node is None:
        return TreeNode(val)
    if val < node.value:
        node.left = _insert(node.left, val)
    elif val > node.value:
        node.right = _insert(node.right, val)
    return node


def _search(node: TreeNode | None, val: int) -> bool:
    if node is None:
        return False
    if val == node.value:
        return True
    if val < node.value:
        return _search(node.left, val)
    return _search(node.right, val)

В PHP готового сбалансированного дерева нет ни в ядре, ни в ext-ds: \Ds\Set - это хеш-таблица (O(1) на add/contains, порядок вставки, без сортировки). Если нужен отсортированный обход, храни данные в массиве и сортируй (sort) или держи отсортированный массив с бинарным поиском. Дерево руками пиши только для учебных задач.

Удаление узла

Удаление - самая хитрая операция BST, потому что после него дерево должно остаться деревом поиска. Сначала узел находим обычным спуском, потом смотрим, сколько у него детей:

  1. Лист (детей нет) - просто убираем узел.
  2. Один потомок - ставим потомка на место удаляемого узла.
  3. Два потомка - находим in-order преемника: минимальный узел правого поддерева (идём направо один раз, потом влево до упора). Копируем его значение в удаляемый узел, а самого преемника удаляем из правого поддерева. У преемника нет левого потомка, поэтому его удаление сводится к случаю 1 или 2.
func (t *BST) Delete(val int) {
    t.Root = deleteNode(t.Root, val)
}

func deleteNode(node *TreeNode, val int) *TreeNode {
    if node == nil {
        return nil // значения нет - нечего удалять
    }
    switch {
    case val < node.Value:
        node.Left = deleteNode(node.Left, val)
    case val > node.Value:
        node.Right = deleteNode(node.Right, val)
    default:
        // Случаи 1 и 2: лист или один потомок - поднимаем потомка
        if node.Left == nil {
            return node.Right
        }
        if node.Right == nil {
            return node.Left
        }
        // Случай 3: два потомка - берём минимум правого поддерева
        successor := node.Right
        for successor.Left != nil {
            successor = successor.Left
        }
        node.Value = successor.Value
        node.Right = deleteNode(node.Right, successor.Value)
    }
    return node
}

Сложность та же, что у поиска: O(h), где h - высота дерева. На сбалансированном дереве это O(log n), на вырожденном O(n).

Обходы дерева

// Inorder: Left → Root → Right (отсортированный порядок!)
func inorder(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }
    inorder(node.Left, result)
    *result = append(*result, node.Value)
    inorder(node.Right, result)
}

// Preorder: Root → Left → Right (для сериализации)
func preorder(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }
    *result = append(*result, node.Value)
    preorder(node.Left, result)
    preorder(node.Right, result)
}

// Postorder: Left → Right → Root (для удаления)
func postorder(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }
    postorder(node.Left, result)
    postorder(node.Right, result)
    *result = append(*result, node.Value)
}

// Level order (BFS)
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }

    var result [][]int
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        levelSize := len(queue)
        var level []int

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Value)

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        result = append(result, level)
    }

    return result
}
<?php
declare(strict_types=1);

final class TreeTraversal
{
    /**
     * @param array<int> $result
     */
    public function inorder(?TreeNode $node, array &$result): void
    {
        if ($node === null) {
            return;
        }
        $this->inorder($node->left, $result);
        $result[] = $node->value;
        $this->inorder($node->right, $result);
    }

    /**
     * @param array<int> $result
     */
    public function preorder(?TreeNode $node, array &$result): void
    {
        if ($node === null) {
            return;
        }
        $result[] = $node->value;
        $this->preorder($node->left, $result);
        $this->preorder($node->right, $result);
    }

    /**
     * @param array<int> $result
     */
    public function postorder(?TreeNode $node, array &$result): void
    {
        if ($node === null) {
            return;
        }
        $this->postorder($node->left, $result);
        $this->postorder($node->right, $result);
        $result[] = $node->value;
    }

    /**
     * @return array<int, array<int>>
     */
    public function levelOrder(?TreeNode $root): array
    {
        if ($root === null) {
            return [];
        }

        $result = [];
        $queue = new SplQueue();
        $queue->enqueue($root);

        while (!$queue->isEmpty()) {
            $levelSize = count($queue);
            $level = [];

            for ($i = 0; $i < $levelSize; $i++) {
                /** @var TreeNode $node */
                $node = $queue->dequeue();
                $level[] = $node->value;

                if ($node->left !== null) {
                    $queue->enqueue($node->left);
                }
                if ($node->right !== null) {
                    $queue->enqueue($node->right);
                }
            }

            $result[] = $level;
        }

        return $result;
    }
}
from collections import deque


def inorder(node: TreeNode | None, result: list[int]) -> None:
    """Left -> Root -> Right (отсортированный порядок!)."""
    if node is None:
        return
    inorder(node.left, result)
    result.append(node.value)
    inorder(node.right, result)


def preorder(node: TreeNode | None, result: list[int]) -> None:
    """Root -> Left -> Right (для сериализации)."""
    if node is None:
        return
    result.append(node.value)
    preorder(node.left, result)
    preorder(node.right, result)


def postorder(node: TreeNode | None, result: list[int]) -> None:
    """Left -> Right -> Root (для удаления)."""
    if node is None:
        return
    postorder(node.left, result)
    postorder(node.right, result)
    result.append(node.value)


# Level order (BFS)
def level_order(root: TreeNode | None) -> list[list[int]]:
    if root is None:
        return []

    result: list[list[int]] = []
    # deque: popleft за O(1), в отличие от list.pop(0)
    queue: deque[TreeNode] = deque([root])

    while queue:
        level_size = len(queue)
        level: list[int] = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.value)

            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)

        result.append(level)

    return result

Сложность

ОперацияСреднееХудшее (вырожденное)
ПоискO(log n)O(n)
ВставкаO(log n)O(n)
УдалениеO(log n)O(n)

Вырожденное дерево - когда все элементы вставлены по порядку и дерево превращается в список.

Рекурсивные insert и search на вырожденном дереве имеют глубину n. В Python это RecursionError уже около 1000 элементов (лимит рекурсии по умолчанию), в Go - рост стека горутины. Для больших данных пиши итеративную версию или используй сбалансированное дерево.

ℹ️ Сбалансированные деревья

Сбалансированным называют дерево, у которого высота на n узлах около log₂ n: каждый следующий уровень вмещает вдвое больше узлов, чем предыдущий, поэтому до любого узла не больше log₂ n шагов. В реальных системах используют AVL-деревья или Red-Black деревья, которые держат дерево сбалансированным и тем гарантируют O(log n). После каждой вставки и удаления они восстанавливают баланс поворотами (ротациями) узлов. AVL держит разницу высот поддеревьев не больше 1, поэтому дерево ниже и поиск чуть быстрее, но вставки чаще требуют ротаций. Red-Black допускает перекос до 2 раз по высоте и делает меньше ротаций, поэтому его чаще берут для структур с частыми изменениями. В Go стандартная map использует hash table, а не дерево. B-tree - основа индексов в PostgreSQL.

Куча: дерево в массиве

Ещё одно важное дерево - двоичная куча (binary heap), на которой строится очередь с приоритетом. Это не дерево поиска: правило другое. В min-heap каждый родитель не больше своих детей, поэтому минимум всегда в корне, а порядок между братьями не важен. Куча всегда почти полная, и её хранят прямо в массиве: дети элемента i лежат в 2i+1 и 2i+2. Вставка и извлечение минимума - O(log n): элемент «всплывает» или «тонет» по одной ветке.

Классическая задача - top-K: найти K наибольших из n чисел. Сортировать всё - O(n log n). Быстрее держать min-heap размера K: в корне лежит самый маленький из текущих K лучших. Каждое новое число сравниваем с корнем: если оно больше, заменяем корень и восстанавливаем кучу за O(log K). Итого O(n log K) времени и O(K) памяти.

// IntHeap - min-heap из урока про очередь с приоритетом
// (Len, Less, Swap, Push, Pop для container/heap).

func topK(nums []int, k int) []int {
    h := &IntHeap{}
    for _, x := range nums {
        if h.Len() < k {
            heap.Push(h, x)
        } else if k > 0 && x > (*h)[0] {
            (*h)[0] = x    // заменяем минимум
            heap.Fix(h, 0) // и восстанавливаем кучу: O(log k)
        }
    }
    return *h // K наибольших, в порядке кучи
}

// topK([]int{5, 1, 9, 3, 7, 2}, 3) -> 3 наибольших: 5, 7, 9
<?php
declare(strict_types=1);

/**
 * @param list<int> $nums
 * @return list<int>
 */
function topK(array $nums, int $k): array
{
    $heap = new SplMinHeap(); // в корне - минимум из текущих K лучших
    foreach ($nums as $x) {
        if ($heap->count() < $k) {
            $heap->insert($x);
        } elseif ($k > 0 && $x > $heap->top()) {
            $heap->extract();    // убираем минимум
            $heap->insert($x);   // O(log k)
        }
    }
    return iterator_to_array($heap, false); // извлекает элементы по возрастанию
}

// topK([5, 1, 9, 3, 7, 2], 3) -> [5, 7, 9]
import heapq


def top_k(nums: list[int], k: int) -> list[int]:
    h: list[int] = []  # min-heap: в h[0] минимум из текущих K лучших
    for x in nums:
        if len(h) < k:
            heapq.heappush(h, x)
        elif k > 0 and x > h[0]:
            heapq.heapreplace(h, x)  # pop минимума + push за O(log k)
    return h


# top_k([5, 1, 9, 3, 7, 2], 3) -> 3 наибольших: 5, 7, 9
# (в стандартной библиотеке есть готовое: heapq.nlargest(k, nums))

Зарегистрируйтесь бесплатно, чтобы пройти квиз, решить задание с автопроверкой, вести прогресс.