Двоичное дерево для получения минимального элемента в O (1)

Question

Я получаю доступ к минимальному элементу двоичного дерева много раз. Какие реализации позволяют мне получить доступ к минимальному элементу в постоянном времени , а не O(log n)?

Answer 1

В зависимости от ваших других требований, min-heap может быть тем, что вы ищете. Это дает вам постоянное время поиска минимального элемента.

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

Answer 2

Найдите его один раз в O (log n) и затем сравните новые значения, которые вы собираетесь добавить с этим кэшированным минимальным элементом.

UPD: о том, как это может работать, если вы удалите минимальный элемент. Вам просто нужно потратить O (log n) еще раз и найти новый.

Давайте представим, что у вас есть 10 000 000 000 000 целых чисел в вашем дереве. Каждому элементу нужно 4 байта в памяти. В этом случае все ваше дерево требует около 40 ТБ свободного места на жестком диске. Время O (log n), которое нужно потратить на поиск минимального элемента в этом огромном дереве, составляет около 43 операций. Конечно, это не самые простые операции, но в любом случае это почти ничего, даже для 20-летних процессоров.

Конечно, это актуально, если это проблема реального мира. Если для каких-то целей (возможно, академических) вам нужен настоящий алгоритм O (1), я не уверен, что мой подход может дать вам такую ​​производительность без использования дополнительной памяти.

Answer 3

Это может звучать глупо, но если вы в основном обращаетесь к минимальному элементу и не слишком сильно меняете дерево, лучшим указателем может быть указатель минимального элемента при добавлении / удалении (в любом дереве). 1001 *

Answer 4

Ходить по дереву всегда будет O (log n). Вы сами написали реализацию дерева? Вы всегда можете просто сохранить ссылку на текущий элемент с наименьшим значением вместе со своей структурой данных и обновлять его при добавлении / удалении узлов. (Если вы не написали дерево, вы также можете сделать это, обернув реализацию дерева в свой собственный объект-обертку, который делает то же самое.)

Answer 5

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

С этим и указателем начала вы можете получить начальный элемент за O (1) раз.

Это решение не быстрее и не эффективнее, чем минимальное кэширование.

Answer 6

Если под минимальный элемент вы имеете в виду элемент с наименьшим значением , то вы можете использовать TreeSet с пользовательским Comparator который сортирует элементы в правильном порядке для хранения отдельных элементов, а затем просто вызывает SortedSet#first() или #last(), чтобы получить максимально большие / наименьшие значения максимально эффективно.

Обратите внимание, что добавление новых элементов в TreeSet немного медленнее по сравнению с другими наборами / списками, но если у вас нет большого количества элементов, которые постоянно меняются, это не должно быть проблемой.

Answer 7

Если вы обновите / "upcomplex" ваше двоичное дерево до двоичного дерева , то вы можете получить O (1) первый и последний элементы.

Вы в основном сохраняете ссылку на текущий первый и последний узлы.

Сразу после вставки, если предыдущий first не равен NULL, обновите сначала. Аналогично для последнего.

При каждом удалении вы сначала проверяете, является ли удаляемый узел первым или последним. И обновите то, что сохранено первым, последним соответствующим образом.

Answer 8

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

Например, то, что вы ищете, очень похоже на связанный список. Вы всегда можете добраться до минимального элемента, но вставка или поиск произвольного узла может занять больше времени, потому что вам нужно выполнить поиск O (n)

Если вы объедините связанный список и дерево, вы можете получить лучшее из обоих миров. Чтобы найти элемент для операций get / insert / delete, вы должны использовать дерево для поиска элемента. Узел "holder" элемента должен иметь способы перехода из дерева в связанный список для операций удаления. Также связанный список должен быть двусвязным списком.

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

Хм, это начинает казаться действительно полезной структурой данных, возможно, немного расточительной в памяти, но я не думаю, что какая-либо операция будет хуже, чем O (logN), если вам не придется заново балансировать дерево.