Дерево статистики заказа
В информатике — дерево статистики заказов это вариант двоичного дерева поиска (или, в более общем смысле, B-дерева) . [1] ), который поддерживает две дополнительные операции помимо вставки, поиска и удаления:
- Select( i ) – найти i -й наименьший элемент, хранящийся в дереве.
- Rank( x ) – найти ранг элемента x в дереве, т.е. его индекс в отсортированном списке элементов дерева.
Обе операции могут быть выполнены за время O (log n ) в худшем случае , когда самобалансирующееся дерево в качестве базовой структуры данных используется .
Реализация расширенного дерева поиска [ править ]
Чтобы превратить обычное дерево поиска в дерево статистики порядка, узлы дерева должны хранить одно дополнительное значение, которое представляет собой размер поддерева, корнем которого является этот узел (т. е. количество узлов ниже него). Все операции, изменяющие дерево, должны корректировать эту информацию, чтобы сохранить инвариант , который
size[x] = size[left[x]] + size[right[x]] + 1
где size[nil] = 0 по определению. Затем Select можно реализовать как [2] : 342
function Select(t, i)
// Returns the i'th element (one-indexed) of the elements in t
p ← size[left[t]]+1
if i = p
return t
else if i < p
return Select(left[t], i)
else
return Select(right[t], i - p)
Ранг может быть реализован с использованием родительской функции p[x] как [3] : 342
function Rank(T, x)
// Returns the position of x (one-indexed) in the linear sorted list of elements of the tree 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 статистики заказов , или бит цвета, чтобы получить красно-черное дерево статистики заказов). В качестве альтернативы поле размера можно использовать в сочетании со схемой балансировки веса без дополнительных затрат на хранение. [4]
Ссылки [ править ]
- ^ «Считанные B-деревья» . 11 декабря 2004 года . Проверено 18 января 2014 г.
- ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03293-7 .
- ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стоун, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4 .
- ^ Рура, Сальвадор (2001). Новый метод балансировки бинарных деревьев поиска . ИКАЛП . Конспекты лекций по информатике. Том. 2076. стр. 469–480. дои : 10.1007/3-540-48224-5_39 . ISBN 978-3-540-42287-7 .
Внешние ссылки [ править ]
- Дерево статистики заказов на PineWiki, Йельский университет.
- Пакет Python blist списков использует B-деревья статистики порядка для реализации с быстрой вставкой в произвольные позиции .