Hard: AVL Trees

Question

Мне был задан этот вопрос, который мне лично трудно найти:

Создать структуру данных, которая может:

Вставить элементы, Удалить элементы, Элементы поиска, Во времени O (log n)

Кроме того, он должен иметь следующие две функции, которые работают во времени O (1):

1. next (x): дан указатель на узел значения х, вернуть указатель на узел с наименьшим большим значением, чем х.

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

Answer 1

@ Идея Роджера Линдсё из комментариев - хорошая. По сути, сохраняйте регулярный сбалансированный BST, а затем продвигайте двусвязный список через узлы, сохраняя их в отсортированном порядке. Таким образом, учитывая указатель на узел в дереве, вы можете найти наибольшее значение, меньшее его или наименьшее значение, большее его, просто следуя следующим или предыдущим указателям в каждом узле.

Вы можете сохранить этот список посредством вставок и удалений без изменения общего времени выполнения вставки или удаления. Например, вот как вы можете сделать вставку элемента x:

1. Выполните стандартный запрос преемника BST, чтобы найти наименьшее значение, большее, чем x в дереве, и стандартный запрос предшественника BST, чтобы найти наибольшее значение меньше, чем х в дереве. Каждый поиск занимает время O (log n).
2. Для вставки x выполните обычную вставку BST. Затем установите его следующий и предыдущий указатели на два элемента, которые вы нашли на предыдущем шаге, и обновите эти узлы, чтобы они указывали на ваш новый узел x. Это также требует времени O (log n).

Общее время для вставки равно O (log n) , что соответствует сбалансированному дереву.

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

Answer 2

Если каждый узел содержит указатель на своего преемника и указатель на своего предшественника или, что то же самое, - если вы поддерживаете как дважды связанный список, так и дерево, где каждый узел в дереве указывает на свой эквивалентный узел в списке и т. наоборот - вы получите хотите, что хотите. Обновление списка при вставке / удалении - O (1) (после нахождения ближайшего узла в дереве). Поиск осуществляется по дереву. Succesor / предшественник выполняются в списке.

Answer 3

Как и большинство самобалансируемых деревьев, B + дерево обеспечивает операции вставки, удаления и поиска с O (log n) сложность времени.

В B + дерево, конечный узел содержит несколько ключей в массиве, поэтому концепция «указатель на узел со значением x » на самом деле не существует, но мы можем определить его как кортеж (указатель, индекс), где указатель на узел, а индекс - это ячейка, в которой хранится x .

В дереве B + узлы на нижнем уровне содержат все ключи, и эти узлы часто связаны, как правило, только в прямом направлении (т. е. вправо), но вполне возможно также поддерживать связь в противоположном направлении, не увеличивая временную сложность вышеуказанных операций.

С этими двумя замечаниями помните, что предыдущие операции могут быть явно выполнены за O (1) время.

Answer 4

Если ваши элементы являются целыми числами, вы можете использовать y-fast tr ie, который поддерживает все упомянутые операции в O (log log m). Кроме того, почти любое дерево поиска позволит выполнять эти операции за O (log n), просто сначала поднимаясь, а затем опускаясь (хотя потребуется много концентрации, чтобы не ошибиться с порядком)