Войти
В информатике дерево статистики порядка является вариантом двоичного дерева поиска (или в более общем смысле, B-дерево ), которое поддерживает две дополнительные операции помимо вставки, поиска и удаления:
Обе операции могут быть выполнены за O (log n) худший случай время, когда самобалансирующееся дерево используется в качестве базовой структуры данных.
Чтобы превратить обычное дерево поиска в дерево статистики порядка, узлы дерева должны хранить одно дополнительное значение, которое представляет собой размер корневого поддерева. узел (т. е. количество узлов под ним). Все операции, которые изменяют дерево, должны корректировать эту информацию, чтобы сохранить инвариант, что
size [x] = size [left [x]] + size [right [x]] + 1
, где size [nil] = 0по определению. Затем выбор может быть реализован как
function Select (t, i) // Возвращает i-й элемент (с нулевым индексом) элементов в tl ← size [left [t]] + 1 if i = l return t else if i < l return Select(left[t], i) else return Select (right [t], i - l)
Ранг может быть реализован как
function Rank (T, x) // Возвращает позицию x (с одним индексом) в линейном отсортированном списке элементов дерева T r ← size [left [x]] + 1 y ← x while y ≠ T.root if y = right [p [y]] r ← r + size [left [p [y]]] + 1 y ← p [y] return r
Деревья статистики заказов могут быть дополнительно дополнены бухгалтерской информацией для поддержания баланса (например, можно добавить высоту дерева, чтобы получить статистику заказа дерево AVL, или бит цвета, чтобы получить значение красно-чёрное дерево статистики порядка). В качестве альтернативы, поле размера можно использовать в сочетании со схемой балансировки веса без дополнительных затрат на хранение.
