Расширение структур данных: Дерево порядковой статистики, Интервальные деревья и B-деревья

1. Дерево порядковой статистики (Order Statistic Tree)

К каждому узлу красно-чёрного дерева добавляется поле size[x] — число узлов в поддереве.

Операции за $O(\log N)$:

OS-Select(x, i): поиск $i$-го наименьшего ключа;

OS-Rank(T, x): определение ранга (порядкового номера) ключа $x$.

---

2. B-деревья (B-Trees) для внешних носителей

B-дерево порядка $t \ge 2$ оптимизировано под блочный ввод-вывод дисков:

Каждый узел содержит от $t-1$ до $2t-1$ ключей;

Все листья находятся на строго одинаковой глубине;

Высота дерева $h \le \log_t \frac{n+1}{2}$, что при $t=1000$ даёт высоту $\le 3$ для миллиарда записей!