Дерево статистики заказов - Википедия - Order statistic tree

В Информатика, дерево статистики заказов это вариант двоичное дерево поиска (или, в более общем смысле, B-дерево[1]), который поддерживает две дополнительные операции помимо вставки, поиска и удаления:

  • Выбирать(я) - Найди я'th наименьший элемент, хранящийся в дереве
  • Классифицировать(Икс) - найти ранг элемента Икс в дереве, т.е. его индекс в отсортированном списке элементов дерева

Обе операции можно выполнять в О(бревно п) худший случай время, когда самобалансирующееся дерево используется в качестве базовой структуры данных.

Реализация расширенного дерева поиска

Чтобы превратить обычное дерево поиска в дерево статистики порядка, узлы дерева должны хранить одно дополнительное значение, которое представляет собой размер поддерева с корнем в этом узле (т. Е. Количество узлов под ним). Все операции, которые изменяют дерево, должны корректировать эту информацию, чтобы сохранить инвариантный который

размер [x] = размер [слева [x]] + размер [справа [x]] + 1

куда размер [nil] = 0 по определению. Затем выбор может быть реализован как[2]:342

функция Select (t, i) // Возвращает i-й элемент (с нулевым индексом) элементов в t l ← size [left [t]] + 1 если я = я возвращаю т иначе если i еще        return Select (right [t], i - l)

Ранг может быть реализован как[3]:342

функция Rank (T, x) // Возвращает позицию x (с одним индексом) в линейном отсортированном списке элементов дерева T r ← size [left [x]] + 1 y ← x пока y ≠ T.root если y = право [p [y]] r ← r + размер [слева [p [y]]] + 1 y ← p [y] возвращаться р

Деревья статистики заказов могут быть дополнительно дополнены бухгалтерской информацией для поддержания баланса (например, можно добавить высоту дерева, чтобы получить статистику заказов. AVL дерево, или немного цвета, чтобы получить красно-черный дерево статистики порядка). В качестве альтернативы поле размера можно использовать вместе с балансировка веса схема без дополнительных затрат на хранение.[4]

Рекомендации

  1. ^ "Счетные B-деревья". 11 декабря 2004 г.. Получено 18 января 2014.
  2. ^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001) [1990]. Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. ISBN  0-262-03293-7.
  3. ^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN  0-262-03384-4.
  4. ^ Роура, Сальвадор (2001). Новый метод балансировки двоичных деревьев поиска. ИКАЛП. Конспект лекций по информатике. 2076. С. 469–480. Дои:10.1007/3-540-48224-5_39. ISBN  978-3-540-42287-7.

внешняя ссылка