Дерево двоичного поиска для определенного намерения
Все мы знаем, что существует много самоуравновешивающихся деревьев двоичного поиска (BST), будучи самым известным Красно-черный и AVL. Могло бы быть полезно смотреть на деревья AA и деревья козла отпущения также.
Я хочу сделать вставки удалений и поиски, как любое другое BST. Однако будет распространено удалить все значения в данном диапазоне или удаление целых поддеревьев. Так:
- Я хочу вставить, искать, удалить значения в O (зарегистрируйте n) (сбалансированное дерево).
- Я хотел бы удалить поддерево, сохраняя целое дерево сбалансированным, в O (зарегистрируйте n) (худший случай или амортизируемый)
- Могло бы быть полезно удалить несколько значений подряд, прежде, чем сбалансировать дерево
- Я буду чаще всего вставлять 2 значения сразу, однако это не правило (просто подсказка в случае, если существует древовидная структура данных, которая принимает это во внимание),
Существует ли вариант AVL или RB, который помогает мне на этом? Деревья козла отпущения походят на больше это, но также нуждались бы в некоторых изменениях, кто-либо, у кого есть опыт в них, может совместно использовать некоторые мысли?
Более точно, который балансировка процедуры и/или процедуры удаления помогла бы мне сохранить это действиями эффективный временем?
5 ответов
Можно удалить диапазон значений BST в O(logn + objects num).
Самый простой способ, который я знаю, это работа со структурой данных Deterministic Skip List (возможно, вы захотите немного почитать об этой структуре данных перед тем, как продолжить). В детерминистическом списке пропуска все реальные значения хранятся на нижнем уровне, а на верхних уровнях есть указатели на них. Вставка, поиск и удаление выполняются в O(logn).
Операция удаления диапазона может быть выполнена по следующему алгоритму:
- Найти первый элемент в диапазоне - O(logn)
- Перейти вперед в связанный список и удалить все элементы, которые все еще находятся в диапазоне. Если есть элементы с указателями на верхние уровни - удаляйте их тоже, пока не достигнете самого верхнего уровня (удаление из связанного списка) - O(количество удаленных объектов)
- Фиксируйте указатели в соответствии с детерминистическим пропуском списка (2-3 элемента между каждым указателем вверх)
Общая сложность удаления из диапазона - O(logn + количество объектов в диапазоне). Обратите внимание, что если вы решите работать со случайным списком пропуска, то получите ту же сложность, но в среднем, а не в худшем случае. Плюс в том, что вам не придется фиксировать указатели верхнего уровня, чтобы удовлетворить спрос на 2-3.
Детерминистический список пропуска имеет привязку 1-1 к дереву 2-3, поэтому, при наличии еще некоторой работы, процедура, описанная выше, может работать и для дерева 2-3.
Хм, а как насчет B-дерева? Они также сбалансированы, и если вы выберете дерево большого порядка ---, это зависит от того, сколько элементов у вас есть ---, вы сэкономите кучу времени создания/уничтожения объектов.
To 2. Если у вас B-дерево порядка 100, вы можете удалить до 100 элементов одним вызовом функции.
To 3. Эта функция может быть применена практически к любому из деревьев, просто реализуйте функцию RemoveSome(), которая удаляет N элементов и делает ребалансировку. Для B-деревьев это немного сложнее, но может быть сделано.
Примечание: Я предполагал, что вы программист. Если вам нужно полное, проверенное, готовое решение, вам нужен другой ответ.
.] Давным-давно, в пред-STL дни, я написал свой собственный алгоритм B-Tree (BST), потому что в то время у меня был довольно большой набор данных (примерно 700K элементов в 2-х деревьях, которые были взаимозависимыми). Я обнаружил, что перебалансировка после каждых 100-200 вставок/удалений была пиковой производительностью, которую я мог получить в то время, основываясь на экспериментах на аппаратном обеспечении 486 и SGI. Сейчас это число может быть другим, а может и нет, так как это, похоже, предел алгоритмической оптимизации, если только вы не конвертируете в параллельную модель. [
] [] Короче говоря, можно применить триггер модификации для восстановления равновесия и разрешить принудительное восстановление равновесия после завершения всех модификаций. [
] [] Улучшение было замечательным. Первоначальная прямая нагрузка не была полной через 25 м (убила процесс). Перебалансировка, как мы пошли также был убит после 15м. Ограниченные модификационные нагрузки с перебалансировкой через каждые 100 модов загружались и бегали менее чем через 3м. Обратите внимание, что во время "бега" части дерева на каждую начальную запись приходилось 0-8 модификаций. Вам действительно нужно подумать, нужно ли всегда быть в равновесии, когда дерево будет снова модифицировано в ближайшем будущем.[
].] Удаление узла и его подузлов в дереве AVL должно быть легко реализовано, если каждый узел хранит свою высоту вместо коэффициента баланса. После удаления узел продолжает вращаться до тех пор, пока два дочерних узла не будут отличаться друг от друга не более чем на один. Затем двигайтесь вверх по дереву и повторяйте. Единственным реальным отличием от нормального удаления будет [] while[] вместо [] if[] для проверки высоты.[
Реализация Set в стандартной библиотеке OCaml представляет собой чисто функциональное дерево AVL, которое удовлетворяет всем вашим требованиям и, в частности, имеет очень эффективные реализации теоретико-множественных операций ( объединение, пересечение, разность). Вставка и удаление выполняются за O (log n). Вы можете удалить поддеревья и серии элементов, представив их как набор и используя разницу наборов. Вы можете вставить два элемента одновременно, создав набор из двух элементов и применив объединение наборов.