Двоичное дерево поиска для определенного намерения

Question

Мы все знаем, что есть много самоустанавливающихся двоичных деревьев поиска (BST), которые являются самыми известными Red-Black и AVL. Возможно, было бы полезно взглянуть на деревья AA и деревья козлов отпущения.

Я хочу сделать удаление и поиск, как и любой другой BST. Тем не менее, будет принято удалять все значения в заданном диапазоне или удалять целые поддеревья. Итак:

1. Я хочу вставлять, искать, удалять значения в O (log n) (сбалансированное дерево).
2. Я хотел бы удалить поддерево, сохраняя все дерево сбалансировано, в O (журнал N) (наихудший или амортизируется)
3. Это может быть полезно, чтобы удалить несколько значений в строке, перед тем балансировки дерева
4. я чаще всего вставить 2 значений одновременно, однако это не является правилом (только наконечник в случае, если есть древовидная структура данных, которая принимает во внимание)

есть вариант AVL или RB что помогает мне в этом? Копытные деревья выглядят более похожими на это, но также нуждаются в некоторых изменениях, любой, у кого есть опыт, может поделиться некоторыми тысячами?

Более точно, какая процедура балансировки и/или процедура удаления помогут мне сохранить это действие с точки зрения времени?

Answer 1

Можно удалить диапазон значений 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 дерева.

Answer 2

Хм, как насчет В-деревьев? Они также сбалансированы, и если вы выбираете большой порядок - это зависит от того, сколько у вас предметов ---, вы сохраните кучу времени создания/уничтожения объекта.

2. Если у вас есть B-дерево порядка 100, вы можете удалить до 100 элементов одним вызовом функции.

Эта функция может быть применена практически к любому из деревьев, просто реализуйте функцию RemoveSome(), которая удаляет N элементов и выполняет балансировку. Для B-деревьев это немного сложнее, но может быть сделано.

Примечание: Я предположил, что вы программист. Если вам нужно полное, проверенное, готовое решение, вам нужен еще один ответ.

Answer 3

Давным-давно в пред-STL-дни я написал свой собственный алгоритм B-Tree (BST), потому что в то время у меня был довольно большой набор данных (примерно 700 тыс. Элементов на двух деревьях, которые были взаимозависимыми). Я обнаружил, что перебалансировка после каждых 100-200 вставок/исключений была максимальной производительностью, которую я мог получить в то время на основе экспериментов на 486 и аппаратных средствах SGI. Это число может быть другим, или, может быть, нет, поскольку оно, по-видимому, является пределом алгоритмической оптимизации, если вы не переходите к параллельной модели.

Короче говоря, вы можете применить триггер модификации для перебалансировки и разрешить принудительное перебалансирование, когда вы выполнили все свои модификации.

Улучшение было замечательным. Начальная прямая загрузка не была полной после 25 м (убил процесс). Перебалансировка, когда мы шли, также была убита после 15 м. Ограниченная модификация загружается с перебалансировкой каждые 100 модов, загружаемых и выполняемых менее чем за 3 м. Обратите внимание, что во время «прогона» на начальную запись было внесено 0-8 изменений в дерево. Вам действительно нужно подумать, нужно ли всегда оставаться в равновесии, когда дерево будет изменено снова в ближайшей перспективе.

Answer 4

Должно быть легко реализовать удаление узла и его узлов в дереве AVL, если каждый узел сохраняет свою высоту вместо коэффициента баланса. После удаления узла продолжайте вращаться, пока два дочерних узла не будут отличаться на несколько. Затем двигайтесь вверх по дереву и повторяйте. Единственное реальное отличие от нормального удаления будет while вместо if для проверки высот.

Answer 5

Реализация Set в стандартной библиотеке OCaml представляет собой чисто функциональное дерево AVL, которое удовлетворяет всем вашим требованиям и, в частности, имеет очень эффективные реализации теоретико-множественных операций (объединение, пересечение, разность). Вставка и удаление - O (log n). Вы можете удалить поддеревья и пробеги элементов, представляя их как набор и используя разницу заданий. Вы можете вставить два элемента одновременно, создав 2-элементный набор и применяя объединение набора.