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

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.

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

• Красно-чёрное дерево и АВЛ-дерево — сбалансированные BST.
• Декартово дерево — рандомизированный BST (treap).
• B-дерево — страничный BST-аналог для диска.
• Двоичная куча — двоичное дерево с другим инвариантом (без BST-свойства).
• Хеш-таблица — неупорядоченная альтернатива.
• Асимптотическая сложность — средние и худшие оценки.

Источники

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.