Двоичное дерево поиска: различия между версиями

Материал из Викиконспекты ПМ-ПУ
 
(не показана 1 промежуточная версия этого же участника)
Строка 85: Строка 85:
'''Разбор.''' Поиск 45: <code>50 → 30 → 40 → 45</code> (рис. 2).
'''Разбор.''' Поиск 45: <code>50 → 30 → 40 → 45</code> (рис. 2).


[[Файл:bst-02-search.svg|frame|none|700px|Рис. 2. Поиск идёт по одному пути; число сравнений равно глубине узла.]]
[[Файл:bst-02-search.svg|frame|none|700px|Рис. 2. Поиск идёт по одному пути; число сравнений равно числу узлов на пути от корня.]]


=== Операция: вставка (Insert) ===
=== Операция: вставка (Insert) ===
Строка 480: Строка 480:
# Адельсон-Вельский Г. М., Ландис Е. М. Об одном алгоритме организации информации // Доклады АН СССР. — 1962. — С. 263–266.
# Адельсон-Вельский Г. М., Ландис Е. М. Об одном алгоритме организации информации // Доклады АН СССР. — 1962. — С. 263–266.
# Wikipedia: Binary search tree. URL: https://en.wikipedia.org/wiki/Binary_search_tree.
# Wikipedia: Binary search tree. URL: https://en.wikipedia.org/wiki/Binary_search_tree.
[[Category:Алгоритмы и структуры данных]]

Текущая версия на 00:37, 26 октября 2026

TL;DR

Двоичное дерево поиска (binary search tree, BST) — двоичное дерево, в котором для каждого узла все ключи левого поддерева меньше ключа узла, а правого — больше. Это свойство делает поиск двоичным: на каждом шаге отбрасывается половина потенциальных ключей. Поиск, вставка, удаление, minimum/maximum и поиск соседних (successor/predecessor) выполняются за [math]\displaystyle{ O(h) }[/math], где [math]\displaystyle{ h }[/math] — высота; при удачном (сбалансированном) дереве [math]\displaystyle{ h = O(\log n) }[/math], но при неудачном порядке вставок BST вырождается в список с [math]\displaystyle{ h = n-1 }[/math] и операциями [math]\displaystyle{ O(n) }[/math]. Обход inorder даёт ключи по возрастанию — отсюда сортировка деревом (tree sort) за [math]\displaystyle{ O(n\log n) }[/math] в среднем. Разновидности с гарантией высоты [math]\displaystyle{ O(\log n) }[/math] — АВЛ, красно-чёрные и B-деревья. BST — базовая структура для множеств и словарей с упорядоченностью.

Свойство Значение
Класс Двоичное дерево поиска (BST), упорядоченное множество/отображение
Свойство left(поддерево) < node < right(поддерево)
Поиск / вставка / удаление [math]\displaystyle{ O(h) }[/math]: [math]\displaystyle{ O(\log n) }[/math] в среднем, [math]\displaystyle{ O(n) }[/math] в худшем
Min / Max / Successor / Predecessor [math]\displaystyle{ O(h) }[/math]
Обход inorder [math]\displaystyle{ O(n) }[/math]; выдаёт ключи по возрастанию
Высота (средняя / худшая) [math]\displaystyle{ \approx 2.99\log_2 n }[/math] / [math]\displaystyle{ n-1 }[/math]
Память [math]\displaystyle{ O(n) }[/math]; на узел — key + left, right, parent
Балансировка Нет (в базовом варианте)
Упорядоченность Да (в отличие от хеш-таблицы)
Варианты с балансом АВЛ, красно-чёрное, B-дерево, treap
Где встречается std::map (как КЧ), словари, диапазонные запросы, основа сбалансированных BST

Определения

Двоичное дерево поиска — двоичное дерево, каждый узел которого хранит ключ и для которого выполняется BST-свойство: если [math]\displaystyle{ x }[/math] — узел с ключом [math]\displaystyle{ k }[/math], то

[math]\displaystyle{ \text{key}(y) \lt k \;\text{для всех } y \in \text{left}(x), \qquad \text{key}(y) \gt k \;\text{для всех } y \in \text{right}(x). }[/math]

Высота [math]\displaystyle{ h }[/math] — число рёбер на самом длинном пути от корня к листу. У листа [math]\displaystyle{ h=0 }[/math]; у пустого поддерева NIL высота [math]\displaystyle{ -1 }[/math]. Стоимость операций пропорциональна [math]\displaystyle{ h }[/math].

Обход inorder — «левый → узел → правый». Для BST он даёт ключи в возрастающем порядке (теорема из §10). preorder (узел → левый → правый) и postorder (левый → правый → узел) используются для копирования и удаления деревьев.

Преемник (successor) узла — следующий по величине ключ; предшественник (predecessor) — предыдущий. Узел с двумя детьми удаляют, заменяя преемником.

Обозначения. [math]\displaystyle{ n }[/math] — число узлов; [math]\displaystyle{ h }[/math] — высота; ключи сравнимы; [math]\displaystyle{ O(\log n) }[/math] — средняя оценка при случайном порядке вставок.

Рис. 1. BST-свойство: слева меньшие ключи, справа большие. Inorder даёт возрастающую последовательность.

Мотивация и интуиция

Отсортированный массив позволяет искать бинарным поиском за [math]\displaystyle{ O(\log n) }[/math], но вставка и удаление стоят [math]\displaystyle{ O(n) }[/math] (сдвиг элементов). Связный список дёшево вставляет, но ищет за [math]\displaystyle{ O(n) }[/math]. Хеш-таблица ищет за [math]\displaystyle{ O(1) }[/math], но не поддерживает порядок. BST соединяет достоинства: это структура, которая держит ключи в упорядоченном виде и при этом позволяет искать, вставлять и удалять по одному пути от корня.

Интуиция — двоичный поиск, встроенный в дерево. В отсортированном массиве сравнение с серединой отбрасывает половину диапазона. В BST роль «середины» играет корень: сравнение с ним отправляет нас в левое или правое поддерево, и процесс повторяется. Высота дерева — это число сравнений.

Ключевое свойство: BST-свойство инвариантно относительно операций. Вставка добавляет лист, удаление аккуратно «залечивает» разрыв, но порядок сохраняется. Отсюда простота базовой структуры. Её слабость — зависимость от порядка вставок: чтобы держать высоту логарифмической, дерево вращают (АВЛ, красно-чёрные) или рандомизируют (treap). BST — фундамент, на котором строятся все сбалансированные деревья.

Устройство

Узел BST хранит ключ и ссылки на левого/правого ребёнка и (обычно) на родителя. Листья — узлы без детей; пустые ссылки обозначаются NIL. Инварианты:

  1. BST-свойство: left < node < right;
  2. ключи сравнимы (линейный порядок);
  3. структура двоичная — не более двух детей.

Операции идут по одному пути от корня: сравнение с ключом узла решает, идти влево, вправо или остановиться. Поэтому время операций — [math]\displaystyle{ O(h) }[/math], а память — [math]\displaystyle{ O(n) }[/math].

Операции и алгоритмы

Операция: поиск (Search)

Идея. Спуск от корня: меньше — влево, больше — вправо, равно — нашли. 

Алгоритм Tree-Search(x, k)
1  while x ≠ NIL and k ≠ key[x]
2      if k < key[x]  x ← left[x]
3      else           x ← right[x]
4  return x

Сложность: O(h); при сбалансированном дереве O(log n). Память O(1).

Корректность: BST-свойство гарантирует, что при наличии k спуск приведёт к нему.

Разбор. Поиск 45: 50 → 30 → 40 → 45 (рис. 2).

Рис. 2. Поиск идёт по одному пути; число сравнений равно числу узлов на пути от корня.

Операция: вставка (Insert)

Идея. Спуститься как при поиске и подключить новый ключ листом. 

Алгоритм Tree-Insert(T, z)
1  y ← NIL;  x ← root[T]
2  while x ≠ NIL
3      y ← x
4      if key[z] < key[x]  x ← left[x]
5      else                 x ← right[x]
6  parent[z] ← y
7  if y = NIL            root[T] ← z
8  else if key[z] < key[y]  left[y] ← z
9  else                     right[y] ← z
10 z принят со ссылками left = right = NIL

Сложность: O(h). Память O(1).

Корректность: z подключается на место пустой ссылки, где сравнения уже гарантируют правильное положение относительно всех предков.

Разбор. Вставка 65: 50 → 70 → 60 → правый ребёнок 60 (рис. 3).

Крайний случай. Дубликат — отклоняется (или идёт по договорённой стороне / хранится со счётчиком).

Рис. 3. Вставка добавляет лист на месте пустого поддерева; существующая структура не меняется.

Операция: удаление (Delete)

Идея. Три случая по числу детей; узел с двумя детьми заменяется преемником — минимумом правого поддерева.

Пошаговое описание.

  1. Лист: просто отцепить (заменить поддерево на NIL).
  2. Один ребёнок: заменить узел его ребёнком.
  3. Два ребёнка: найти преемника y = Minimum(right), перевесить y на место узла.
Алгоритм Tree-Delete(T, z)
1  if left[z] = NIL
2      Transplant(T, z, right[z])
3  else if right[z] = NIL
4      Transplant(T, z, left[z])
5  else
6      y ← Tree-Minimum(right[z])          # преемник, у него нет левого ребёнка
7      if parent[y] ≠ z
8          Transplant(T, y, right[y])
9          right[y] ← right[z];  parent[right[y]] ← y
10     Transplant(T, z, y)
11     left[y] ← left[z];  parent[left[y]] ← y

Алгоритм Transplant(T, u, v)
12 if parent[u] = NIL       root[T] ← v
13 else if u = left[parent[u]]  left[parent[u]] ← v
14 else                     right[parent[u]] ← v
15 if v ≠ NIL  parent[v] ← parent[u]

Сложность: O(h). Память O(1).

Корректность: преемник — наименьший в правом поддереве; он не меньше всего левого поддерева узла и не больше остального правого, поэтому замена сохраняет BST-свойство.


Рис. 4. Три случая: лист, один ребёнок, два ребёнка (замена преемником).

Операции: минимум, максимум, соседние

Minimum/Maximum — спуск влево/вправо до конца, [math]\displaystyle{ O(h) }[/math]. Successor([math]\displaystyle{ x }[/math]) — если есть правый ребёнок, то минимум правого поддерева; иначе — первый предок, для которого [math]\displaystyle{ x }[/math] лежит в левом поддереве. Predecessor — зеркально. Все за [math]\displaystyle{ O(h) }[/math].

Операция: обходы (Traversal)

Inorder даёт ключи по возрастанию; preorder (узел раньше детей) удобен для копирования; postorder (узел позже детей) — для освобождения памяти. 

Алгоритм Inorder(x)
1  if x ≠ NIL
2      Inorder(left[x])
3      посетить x
4      Inorder(right[x])

Сложность: O(n). Рекурсия использует стек вызовов глубиной O(h).

Рис. 5. Inorder, preorder, postorder на одном дереве; inorder даёт возрастающий порядок.

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

BST с итеративными поиском/вставкой, удалением по CLRS (через transplant), минимумом/максимумом и проверкой инвариантов. 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstddef>

template <typename T>
class BST {
    struct Node {
        T key;
        Node *l = nullptr, *r = nullptr, *p = nullptr;
        explicit Node(const T& k) : key(k) {}
    };
    Node* root_ = nullptr;
    std::size_t size_ = 0;

    void transplant(Node* u, Node* v) {         // заменить поддерево u поддеревом v
        if (!u->p)            root_ = v;
        else if (u == u->p->l) u->p->l = v;
        else                   u->p->r = v;
        if (v) v->p = u->p;
    }
    static Node* minimum(Node* x) { while (x->l) x = x->l; return x; }
    static Node* maximum(Node* x) { while (x->r) x = x->r; return x; }
    static void destroy(Node* n) {
        if (!n) return;
        destroy(n->l);
        destroy(n->r);
        delete n;
    }
    static bool check(Node* n, const T* lo, const T* hi) {
        if (!n) return true;
        if (lo && !(*lo < n->key)) return false;
        if (hi && !(n->key < *hi)) return false;
        if (n->l && n->l->p != n) return false;
        if (n->r && n->r->p != n) return false;
        return check(n->l, lo, &n->key) && check(n->r, &n->key, hi);
    }
    static void inorder(Node* n, std::vector<T>& out) {
        if (!n) return;
        inorder(n->l, out);
        out.push_back(n->key);
        inorder(n->r, out);
    }

public:
    BST() = default;
    ~BST() { destroy(root_); }
    BST(const BST&) = delete;
    BST& operator=(const BST&) = delete;

    bool contains(const T& k) const {
        const Node* x = root_;
        while (x) {
            if (k < x->key)      x = x->l;
            else if (x->key < k) x = x->r;
            else                 return true;
        }
        return false;
    }

    void insert(const T& k) {                   // вставка листом
        Node* z = new Node(k);
        if (!root_) { root_ = z; ++size_; return; }
        Node* x = root_;
        Node* y = nullptr;
        while (x) {
            y = x;
            if (k < x->key)      x = x->l;
            else if (x->key < k) x = x->r;
            else { delete z; return; }          // дубликаты отклоняются
        }
        z->p = y;
        if (k < y->key) y->l = z; else y->r = z;
        ++size_;
    }

    void erase(const T& k) {
        Node* z = root_;
        while (z) {
            if (k < z->key)      z = z->l;
            else if (z->key < k) z = z->r;
            else                 break;
        }
        if (!z) return;
        if (!z->l) {
            transplant(z, z->r);                // нет левого ребёнка
        } else if (!z->r) {
            transplant(z, z->l);                // нет правого ребёнка
        } else {
            Node* y = minimum(z->r);            // преемник
            if (y->p != z) {
                transplant(y, y->r);
                y->r = z->r;
                y->r->p = y;
            }
            transplant(z, y);
            y->l = z->l;
            y->l->p = y;
        }
        delete z;
        --size_;
    }

    T minimum() const { return minimum(root_)->key; }
    T maximum() const { return maximum(root_)->key; }
    std::size_t size() const { return size_; }
    bool validate() const { return check(root_, nullptr, nullptr); }

    std::vector<T> sorted() const {
        std::vector<T> out;
        inorder(root_, out);
        return out;
    }
};

int main() {
    BST<int> t;
    for (int v : {50, 30, 70, 20, 40, 60, 80, 35, 45}) t.insert(v);
    assert(t.validate());
    assert(t.contains(45) && !t.contains(99));
    assert(t.minimum() == 20 && t.maximum() == 80);

    std::vector<int> s = t.sorted();
    assert(std::is_sorted(s.begin(), s.end()));
    assert(s.size() == 9);

    t.erase(30);                                // два ребёнка
    assert(t.validate() && !t.contains(30));
    t.erase(20);                                // лист
    assert(t.validate() && !t.contains(20));
    t.erase(70);                                // два ребёнка
    assert(t.validate() && !t.contains(70));
    assert(t.size() == 6);

    s = t.sorted();
    assert(std::is_sorted(s.begin(), s.end()));
    assert(!t.contains(30) && t.contains(35) && t.contains(40));

    std::cout << "ok\n";
    return 0;
}

Замечания по реализации.

  • Удаление через transplant (CLRS) единообразно обрабатывает все случаи.
  • Дубликаты отклоняются; для мультимножества нужен счётчик или сторона.
  • check проверяет BST-свойство с границами и корректность ссылок на родителей.
  • Рекурсивные destroy/inorder безопасны при высоте [math]\displaystyle{ O(\log n) }[/math], но при вырождении возможна глубокая рекурсия — для продакшна используют итеративные обходы.

Сводная таблица сложности

Операция Средний Худший Память Замечание
Search [math]\displaystyle{ O(\log n) }[/math] [math]\displaystyle{ O(n) }[/math] [math]\displaystyle{ O(1) }[/math] один путь от корня
Insert [math]\displaystyle{ O(\log n) }[/math] [math]\displaystyle{ O(n) }[/math] [math]\displaystyle{ O(1) }[/math] добавляет лист
Delete [math]\displaystyle{ O(\log n) }[/math] [math]\displaystyle{ O(n) }[/math] [math]\displaystyle{ O(1) }[/math] замена преемником
Min / Max [math]\displaystyle{ O(\log n) }[/math] [math]\displaystyle{ O(n) }[/math] [math]\displaystyle{ O(1) }[/math] спуск к краю
Successor / Predecessor [math]\displaystyle{ O(\log n) }[/math] [math]\displaystyle{ O(n) }[/math] [math]\displaystyle{ O(1) }[/math] вверх/вниз
Inorder (sorted) [math]\displaystyle{ O(n) }[/math] [math]\displaystyle{ O(n) }[/math] [math]\displaystyle{ O(h) }[/math] стека выдаёт по возрастанию
Память структуры [math]\displaystyle{ O(n) }[/math] [math]\displaystyle{ O(n) }[/math] [math]\displaystyle{ O(n) }[/math] key + 3 ссылки

Примечание. Все оценки зависят от высоты [math]\displaystyle{ h }[/math], а не только от [math]\displaystyle{ n }[/math]. При случайном порядке вставок ожидаемая высота [math]\displaystyle{ \approx 2.99\log_2 n }[/math], но при отсортированном входе BST вырождается в список высоты [math]\displaystyle{ n-1 }[/math] и операции становятся [math]\displaystyle{ O(n) }[/math]. Именно отсутствие гарантии [math]\displaystyle{ O(\log n) }[/math] — причина, по которой на практике берут сбалансированные деревья.

Рис. 6. Сбалансированное дерево даёт [math]\displaystyle{ O(\log n) }[/math], вырожденное — [math]\displaystyle{ O(n) }[/math]; высота решает.

Трассировка примера

Вставим [math]\displaystyle{ 50, 30, 70, 20, 40, 60 }[/math] и удалим 30.

Шаг Операция BST (по возрастанию) Действие
1 insert 50 50 корень
2 insert 30 30, 50 30 < 50 → левый ребёнок
3 insert 70 30, 50, 70 70 > 50 → правый ребёнок
4 insert 20 20, 30, 50, 70 20 < 30 → левый ребёнок 30
5 insert 40 20, 30, 40, 50, 70 40 > 30 → правый ребёнок 30
6 insert 60 20, 30, 40, 50, 60, 70 60 < 70 → левый ребёнок 70
7 erase 30 20, 40, 50, 60, 70 два ребёнка: преемник 40 встаёт на место 30

После удаления 30 его место занимает преемник 40 (минимум правого поддерева), а его левый ребёнок 20 и правый 45 (если был) остаются на месте — BST-свойство сохранено. inorder на каждом шаге возрастает, validate() подтверждает инварианты.

Корректность и оценка сложности

Теорема (inorder сортирует):
Обход inorder BST выдаёт ключи в неубывающем порядке.
Доказательство:

Индукция по структуре. Для узла [math]\displaystyle{ x }[/math]: по BST-свойству все ключи левого поддерева меньше [math]\displaystyle{ \text{key}(x) }[/math], правого — больше. По индукции inorder левого поддерева даёт возрастающую последовательность меньших ключей, затем идёт [math]\displaystyle{ \text{key}(x) }[/math], затем — возрастающая последовательность больших. Итог возрастает.

[math]\displaystyle{ \blacksquare }[/math]


Лемма (инвариант BST при вставке и удалении):
После Insert и Delete BST-свойство сохраняется.
Доказательство:

Вставка подключает лист на место пустой ссылки: все предки уже сравнены, поэтому ключ попадает точно между меньшими и большими. Удаление: случаи одного ребёнка и листа очевидны; при двух детях преемник [math]\displaystyle{ y }[/math] — наименьший в правом поддереве, он больше всего левого поддерева (которое всё меньше [math]\displaystyle{ z }[/math]) и не больше остальных правого, поэтому замена [math]\displaystyle{ z }[/math] на [math]\displaystyle{ y }[/math] сохраняет порядок.

[math]\displaystyle{ \blacksquare }[/math]


Теорема (ожидаемая высота):
При вставке [math]\displaystyle{ n }[/math] различных ключей в случайном порядке ожидаемая высота BST есть [math]\displaystyle{ \Theta(\log n) }[/math]; точнее, [math]\displaystyle{ \approx 2.99\log_2 n }[/math], а средняя глубина узла [math]\displaystyle{ \approx 1.39\log_2 n }[/math].
Доказательство:

Идея. Форма BST, построенного случайной перестановкой ключей, совпадает с формой дерева рандомизированного быстрого поиска (связь с quicksort): корень — случайный ключ, и подзадачи независимы. Анализ даёт логарифмическую ожидаемую высоту.

[math]\displaystyle{ \blacksquare }[/math]


Следствие:
(tree sort) Вставка [math]\displaystyle{ n }[/math] ключей и inorder-обход дают сортировку за [math]\displaystyle{ O(n\log n) }[/math] в среднем; худший случай [math]\displaystyle{ O(n^2) }[/math] при вырождении (сравните с quicksort).
Доказательство:

доказательство (необязательно)

[math]\displaystyle{ \blacksquare }[/math]


Сравнение с альтернативами

Структура Поиск Упорядоченность Диапазон Худший поиск Баланс
BST (базовый) [math]\displaystyle{ O(h) }[/math] да да [math]\displaystyle{ O(n) }[/math] нет
АВЛ [math]\displaystyle{ O(\log n) }[/math] да да [math]\displaystyle{ O(\log n) }[/math] строгий
Красно-чёрное [math]\displaystyle{ O(\log n) }[/math] да да [math]\displaystyle{ O(\log n) }[/math] умеренный
Декартово (treap) [math]\displaystyle{ O(\log n) }[/math] ожид. да да [math]\displaystyle{ O(n) }[/math] рандомизированный
B-дерево [math]\displaystyle{ O(\log_t n) }[/math] да да [math]\displaystyle{ O(\log_t n) }[/math] страничный
Хеш-таблица [math]\displaystyle{ O(1) }[/math] средн. нет нет [math]\displaystyle{ O(n) }[/math] —

Вердикт. Базовый BST прост и даёт упорядоченность, но не гарантирует [math]\displaystyle{ O(\log n) }[/math]. Если вход может быть недружественным, берут сбалансированные варианты (АВЛ, красно-чёрное, treap). Если порядок не нужен — хеш-таблицу. Если данные на диске — B-дерево.

Где применяется

  1. Упорядоченные контейнеры. Идея BST лежит в основе std::map/set (реализованных как красно-чёрные деревья), TreeMap в Java, SortedDictionary в .NET.
  2. Диапазонные запросы. Поиск всех ключей в [math]\displaystyle{ [a, b] }[/math], successor/predecessor — там, где нужно упорядоченное множество.
  3. Сортировка деревом. Tree sort: вставка + inorder-обход за [math]\displaystyle{ O(n\log n) }[/math] в среднем.
  4. Символьные таблицы. Компиляторы хранят имена в упорядоченных деревьях для быстрого поиска и обхода в порядке.
  5. Структуры-надстройки. Декартовы деревья, splay-деревья, интервальные деревья, link-cut trees — всё это расширения идеи BST.
  6. Геометрия и базы данных. Пространственные индексы и диапазонные запросы по одному измерению строятся на BST-идее.

Историческая справка

  • 1960-е. Идея упорядоченного двоичного дерева для поиска возникла в ранних работах по информационному поиску; в учебники BST вошёл в 1960-е ⚠️ точная атрибуция.
  • 1962. Адельсон-Вельский и Ландис предложили АВЛ-деревья — первый сбалансированный BST, устраняющий вырождение [4].
  • 1970-е. BST стал стандартной темой курсов; Хиббард, а затем другие исследовали удаление и обходы; связь со quicksort установлена в анализе случайных BST.
  • 1978. Гийба и Седжвик предложили красно-чёрные деревья — доминирующую реализацию сбалансированного BST.

Типичные ошибки и подводные камни

  • Вырождение в список. Отсортированный вход (1, 2, 3, …) даёт высоту [math]\displaystyle{ n }[/math]; нужны балансировка или рандомизация.
  • Ошибка BST-свойства при удалении. Замена не преемником, а произвольным узлом, ломает порядок.
  • Преемник с левым ребёнком. Преемник (минимум правого поддерева) левого ребёнка не имеет — иначе он не минимум.
  • Потеря ссылки на родителя. transplant должен обновлять parent у нового поддерева.
  • Дубликаты. Их надо явно обрабатывать (отклонять/счётчик/сторона), иначе возможен дисбаланс.
  • Рекурсия и глубина. Рекурсивные операции при вырождении дают стек глубины [math]\displaystyle{ O(n) }[/math]; используйте итеративные версии.
  • erase без поиска. Нужно сначала найти узел, затем удалять именно его.
  • Мутация ключей. Изменение ключа узла ломает BST-свойство; удаляют и вставляют заново.
  • Сравнение с плавающими ключами. Неточные сравнения ведут к нарушению порядка; используйте целые ключи или строгий компаратор.
  • Ожидание гарантии [math]\displaystyle{ O(\log n) }[/math]. У базового BST её нет: все оценки — в среднем по случайному порядку вставок.

Задачи для практики

  1. Реализация. Реализуйте поиск, вставку, удаление; проверьте BST-свойство. Подсказка: validate с границами.
  2. Высота. Постройте BST из случайной перестановки и из отсортированного массива; сравните высоты. Подсказка: вырождение даёт [math]\displaystyle{ n }[/math].
  3. Проверка BST. Проверьте, является ли дерево BST, за [math]\displaystyle{ O(n) }[/math]. Подсказка: inorder возрастает или рекурсия с границами.
  4. k-й элемент. Найдите [math]\displaystyle{ k }[/math]-й по величине ключ. Подсказка: размеры поддеревьев.
  5. Ближайший ключ. Найдите floor/ceil данного ключа за [math]\displaystyle{ O(h) }[/math]. Подсказка: спуск с кандидатом.
  6. Два узла с данным «расстоянием». Найдите пару ключей с заданной суммой. Подсказка: inorder двух указателей.
  7. Tree sort. Отсортируйте массив через BST; сравните с std::sort. Подсказка: вырождение ухудшает время.
  8. Валидация после удаления. Сгенерируйте случайные операции вставки/удаления и проверяйте инварианты после каждой. Подсказка: validate.

Связанные темы

Источники

  1. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 12 «Binary Search Trees» (поиск, вставка, удаление, обходы).
  2. Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §6.2.2 «Binary Tree Searching».
  3. Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — Гл. 3.2 «Binary Search Trees».
  4. Адельсон-Вельский Г. М., Ландис Е. М. Об одном алгоритме организации информации // Доклады АН СССР. — 1962. — С. 263–266.
  5. Wikipedia: Binary search tree. URL: https://en.wikipedia.org/wiki/Binary_search_tree.
Источник — https://apmath.info/w/index.php?title=Двоичное_дерево_поиска&oldid=686