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

Question

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

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

1. Я хочу вставлять, искать, удалять значения в O (log n) (сбалансированное дерево).
2. Я хотел бы удалить поддерево, сохраняя баланс всего дерева, в O (log 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

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

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

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

Answer 3

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

Answer 4

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

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

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

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

Answer 5

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