Структуры данных: рандомизированная куча, дерево двоичного поиска, декартово дерево по явному и неявному ключу

Структуры данных

Рандомизированная куча минимума

Куча минимума — это двоичное дерево, в котором ключ каждой вершины не больше ключей её детей, поэтому наименьший ключ находится в корне. Все операции с кучей выражаются через слияние двух куч $\mathrm{merge}(a, b)$.

Слияние устроено так. Если одна из куч пуста, результатом становится другая. Иначе корнем результата становится вершина с меньшим ключом, и её поддеревья с вероятностью $\frac{1}{2}$ меняются местами. После этого вторая куча сливается с левым поддеревом корня. Поэтому слияние с равной вероятностью продолжается то в одном, то в другом поддереве исходной вершины.

Вставка ключа $x$ — это слияние кучи с одновершинной кучей $\{x\}$. Извлечение минимума — это удаление корня и слияние его левого и правого поддеревьев.

Ожидаемая длина пути слияния равна $O(\log n)$, где $n$ — число вершин. Усреднение идёт по результатам монетки, а не по входным данным. Поэтому слияние, вставка и извлечение минимума выполняются за ожидаемое время $O(\log n)$. Без монетки, если всегда сливать в левое поддерево, вставка возрастающих ключей давала бы путь длины $O(n)$.

Реализация на Python

# Рандомизированная куча минимума: слияние, вставка и извлечение минимума за ожидаемое O(log n)
from __future__ import annotations

import random
from dataclasses import dataclass


@dataclass
class Node:
    key: int
    left: Node | None = None
    right: Node | None = None


def merge(a: Node | None, b: Node | None) -> Node | None:
    """Сливает две кучи. Ожидаемое время O(log n)."""
    if a is None:
        return b
    if b is None:
        return a
    if b.key < a.key:
        a, b = b, a  # в корне остаётся вершина с меньшим ключом
    if random.random() < 0.5:  # монетка: в левое или в правое поддерево пойдёт слияние
        a.left, a.right = a.right, a.left
    a.left = merge(a.left, b)
    return a


def insert(heap: Node | None, key: int) -> Node | None:
    return merge(heap, Node(key))


def extract_min(heap: Node | None) -> tuple[int, Node | None]:
    """Возвращает минимум и кучу без него. Куча должна быть непустой."""
    if heap is None:
        raise IndexError("извлечение из пустой кучи")
    return heap.key, merge(heap.left, heap.right)


def main() -> None:
    random.seed(7)  # фиксированное зерно: демо всегда выводит один и тот же результат
    heap = None
    for key in [7, 3, 9, 1, 5, 8, 2]:
        heap = insert(heap, key)
    keys = []
    while heap is not None:
        key, heap = extract_min(heap)
        keys.append(key)
    print("Извлечение по возрастанию:", keys)


if __name__ == "__main__":
    main()

Реализация на C++

// Рандомизированная куча минимума: слияние, вставка и извлечение минимума за ожидаемое O(log n)
#include <iostream>
#include <memory>
#include <random>
#include <utility>

struct Node {
    long long key;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
};

using Heap = std::unique_ptr<Node>;

// Слияние двух куч. Монетка решает, в левое или в правое поддерево пойдёт слияние.
Heap merge(Heap a, Heap b, std::mt19937& coins) {
    if (!a) return b;
    if (!b) return a;
    if (b->key < a->key) std::swap(a, b);  // в корне остаётся вершина с меньшим ключом
    if (coins() % 2 == 1) std::swap(a->left, a->right);
    a->left = merge(std::move(a->left), std::move(b), coins);
    return a;
}

// Вставка: слияние кучи с одновершинной кучей.
Heap insert(Heap heap, long long key, std::mt19937& coins) {
    auto node = std::make_unique<Node>(Node{key, nullptr, nullptr});
    return merge(std::move(heap), std::move(node), coins);
}

// Извлечение минимума из непустой кучи: сливаем поддеревья корня.
long long extract_min(Heap& heap, std::mt19937& coins) {
    long long key = heap->key;
    heap = merge(std::move(heap->left), std::move(heap->right), coins);
    return key;
}

int main() {
    std::mt19937 coins(7);  // фиксированное зерно: демо всегда выводит один и тот же результат
    Heap heap;
    for (long long key : {7, 3, 9, 1, 5, 8, 2}) heap = insert(std::move(heap), key, coins);
    std::cout << "Извлечение по возрастанию:";
    while (heap) std::cout << ' ' << extract_min(heap, coins);
    std::cout << '\n';
    return 0;
}

Реализация на Rust

// Рандомизированная куча минимума: слияние, вставка и извлечение минимума за ожидаемое O(log n)

/// Генератор xorshift64 (только std). Зерно должно быть ненулевым.
pub struct Rng(pub u64);

impl Rng {
    pub fn next_u64(&mut self) -> u64 {
        self.0 ^= self.0 << 13;
        self.0 ^= self.0 >> 7;
        self.0 ^= self.0 << 17;
        self.0
    }
}

pub struct Node {
    pub key: i64,
    pub left: Heap,
    pub right: Heap,
}

pub type Heap = Option<Box<Node>>;

/// Слияние двух куч. Монетка решает, в левое или в правое поддерево пойдёт слияние.
pub fn merge(a: Heap, b: Heap, rng: &mut Rng) -> Heap {
    match (a, b) {
        (None, heap) | (heap, None) => heap,
        (Some(x), Some(y)) => {
            // В корне остаётся вершина с меньшим ключом (свойство кучи).
            let (mut root, other) = if y.key < x.key { (y, x) } else { (x, y) };
            if rng.next_u64() % 2 == 1 {
                std::mem::swap(&mut root.left, &mut root.right);
            }
            root.left = merge(root.left.take(), Some(other), rng);
            Some(root)
        }
    }
}

/// Вставка: слияние кучи с одновершинной кучей.
pub fn insert(heap: Heap, key: i64, rng: &mut Rng) -> Heap {
    let node = Box::new(Node { key, left: None, right: None });
    merge(heap, Some(node), rng)
}

/// Извлечение минимума: сливаем поддеревья корня.
pub fn extract_min(heap: Heap, rng: &mut Rng) -> Option<(i64, Heap)> {
    let Node { key, left, right } = *heap?;
    Some((key, merge(left, right, rng)))
}

fn main() {
    let mut rng = Rng(7); // фиксированное зерно: демо всегда выводит один и тот же результат
    let mut heap: Heap = None;
    for key in [7, 3, 9, 1, 5, 8, 2] {
        heap = insert(heap, key, &mut rng);
    }
    let mut keys = Vec::new();
    while let Some((key, rest)) = extract_min(heap, &mut rng) {
        keys.push(key);
        heap = rest;
    }
    println!("Извлечение по возрастанию: {keys:?}");
}

Дерево двоичного поиска

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

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

Поиск и вставка работают за $O(h)$, где $h$ — высота дерева. Для сбалансированного дерева $h = O(\log n)$, но в худшем случае $h = O(n)$, например когда ключи вставляются по возрастанию.

Обход по порядку (сначала левое поддерево, затем вершина, затем правое поддерево) выводит ключи по возрастанию за $O(n)$. Декартово дерево, упомянутое в заголовке страницы, — это дерево двоичного поиска по ключу, которое одновременно является кучей по случайным приоритетам вершин; здесь оно не рассматривается.

Реализация на Python

# Дерево двоичного поиска: поиск и вставка за O(h), обход по порядку за O(n), h - высота дерева
from __future__ import annotations

from collections.abc import Iterator
from dataclasses import dataclass


@dataclass
class Node:
    key: int
    left: Node | None = None
    right: Node | None = None


def insert(root: Node | None, key: int) -> Node:
    """Вставка: равные ключи уходят вправо, дубликаты сохраняются."""
    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


def contains(root: Node | None, key: int) -> bool:
    node = root
    while node is not None:
        if node.key == key:
            return True
        node = node.left if key < node.key else node.right
    return False


def keys_in_order(root: Node | None) -> Iterator[int]:
    """Обход по порядку: левое поддерево, вершина, правое поддерево."""
    if root is None:
        return
    yield from keys_in_order(root.left)
    yield root.key
    yield from keys_in_order(root.right)


def main() -> None:
    root = None
    for key in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
        root = insert(root, key)
    print(f"Поиск 6: {contains(root, 6)}, поиск 5: {contains(root, 5)}")
    keys = list(keys_in_order(root))
    print("Обход по порядку:", keys)
    print("Отсортировано:", keys == sorted(keys))


if __name__ == "__main__":
    main()

Реализация на C++

// Дерево двоичного поиска: поиск и вставка за O(h), обход по порядку за O(n), h - высота дерева
#include <algorithm>
#include <iostream>
#include <memory>
#include <vector>

struct Node {
    int key;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
};

using Tree = std::unique_ptr<Node>;

// Вставка: равные ключи уходят вправо, дубликаты сохраняются.
void insert(Tree& node, int key) {
    if (!node) {
        node = std::make_unique<Node>(Node{key, nullptr, nullptr});
        return;
    }
    insert(key < node->key ? node->left : node->right, key);
}

// Поиск: спускаемся от корня, сравнивая ключи.
bool contains(const Tree& root, int key) {
    const Node* node = root.get();
    while (node) {
        if (node->key == key) return true;
        node = key < node->key ? node->left.get() : node->right.get();
    }
    return false;
}

// Обход по порядку: левое поддерево, вершина, правое поддерево.
void inorder(const Tree& node, std::vector<int>& keys) {
    if (!node) return;
    inorder(node->left, keys);
    keys.push_back(node->key);
    inorder(node->right, keys);
}

int main() {
    Tree root;
    for (int key : {8, 3, 10, 1, 6, 14, 4, 7, 13}) insert(root, key);
    std::cout << std::boolalpha;
    std::cout << "Поиск 6: " << contains(root, 6) << ", поиск 5: " << contains(root, 5) << '\n';
    std::vector<int> keys;
    inorder(root, keys);
    std::cout << "Обход по порядку:";
    for (int key : keys) std::cout << ' ' << key;
    std::cout << '\n';
    std::cout << "Отсортировано: " << std::is_sorted(keys.begin(), keys.end()) << '\n';
    return 0;
}

Реализация на Rust

// Дерево двоичного поиска: поиск и вставка за O(h), обход по порядку за O(n), h - высота дерева

pub struct Node {
    pub key: i64,
    pub left: Tree,
    pub right: Tree,
}

pub type Tree = Option<Box<Node>>;

/// Вставка: равные ключи уходят вправо, дубликаты сохраняются.
pub fn insert(tree: &mut Tree, key: i64) {
    match tree {
        None => *tree = Some(Box::new(Node { key, left: None, right: None })),
        Some(node) if key < node.key => insert(&mut node.left, key),
        Some(node) => insert(&mut node.right, key),
    }
}

/// Поиск: спускаемся от корня, сравнивая ключи.
pub fn contains(mut tree: &Tree, key: i64) -> bool {
    while let Some(node) = tree {
        if node.key == key {
            return true;
        }
        tree = if key < node.key { &node.left } else { &node.right };
    }
    false
}

/// Обход по порядку: левое поддерево, вершина, правое поддерево.
pub fn inorder(tree: &Tree, keys: &mut Vec<i64>) {
    if let Some(node) = tree {
        inorder(&node.left, keys);
        keys.push(node.key);
        inorder(&node.right, keys);
    }
}

fn main() {
    let mut root: Tree = None;
    for key in [8, 3, 10, 1, 6, 14, 4, 7, 13] {
        insert(&mut root, key);
    }
    println!("Поиск 6: {}, поиск 5: {}", contains(&root, 6), contains(&root, 5));
    let mut keys = Vec::new();
    inorder(&root, &mut keys);
    println!("Обход по порядку: {keys:?}");
    println!("Отсортировано: {}", keys.windows(2).all(|w| w[0] <= w[1]));
}