Я получаю доступ к минимальному элементу двоичного дерева много раз. Какие реализации позволяют мне получить доступ к минимальному элементу в постоянном времени, а не O(log n)?Двоичное дерево для получения минимального элемента в O (1)
Найдите его один раз в O (log n), а затем сравните новые значения, которые вы собираетесь добавить с помощью этого минимального элемента кэширования.
UPD: о том, как это может быть выполнено, если вы удалите минимальный элемент. Вам просто нужно потратить O (log n) еще раз и найти новый.
Предположим, что у вас есть 10 000 000 000 000 целых чисел в вашем дереве. Каждому элементу требуется 4 байта в памяти. В этом случае для всего вашего дерева требуется около 40 ТБ пространства жесткого диска. Время O (log n), которое должно быть потрачено на поиск минимального элемента в этом огромном дереве, составляет около 43 операций. Конечно, это не самые простые операции, но в любом случае это почти ничего, даже для 20-летних процессоров.
Конечно, это актуально, если это проблема реального мира. Если для некоторых целей (возможно, академических) вам нужен реальный алгоритм O (1), то я не уверен, что мой подход может дать вам такую производительность без использования дополнительной памяти.
Если минимальный элемент удаляется из дерева, вам нужно найти новый минимум. Оказывает ли это влияние на этот подход? – Rudiger
Если у вас есть контроль над реализацией дерева: вы будете сталкиваться с новым минимальным элементом при удалении минимального элемента из дерева, чтобы вы могли обновить минимальный элемент в O (1) дополнительное время.(Конечно, фактическое удаление самого маленького элемента по-прежнему будет стоить O (log n).) – meriton
Просто обновляйте кешированный минимум каждый раз, когда есть вставка/удаление. FindMin все равно будет O (1) и вставляет/удаляет все еще O (log n), предполагая RB или некоторую подобную сбалансированную реализацию дерева. Если дерево позволяет вам ходить (например, dfs), нет необходимости возиться с внутренней реализацией. – 2010-02-15 09:03:45
В зависимости от ваших требований, min-heap может быть тем, что вы ищете. Это дает вам постоянный поиск минимального элемента.
Однако вы не можете выполнять некоторые другие операции с такой же легкостью, как с простым двоичным деревом поиска, например, определить, находится ли значение в дереве или нет. Вы можете взглянуть на splay trees, своеобразное самобалансирующееся двоичное дерево, которое обеспечивает улучшенное время доступа к недавно доступным элементам.
Он должен поддерживать полный порядок элементов для других целей; Тем не менее, я получаю доступ к элементу верхнего уровня. – Rudiger
Если элемент, к которому вы часто обращаетесь, на самом деле является «вершиной» или корнем дерева (а не минимальным * значением *), то доступ к этому напрямую должен быть O (1) уже, поскольку обход не требуется. –
@Ben: Я думаю, что Рудигер имел в виду верхний элемент, если он был реализован с кучей (в моем ответе первоначально упоминались только кучи) –
Прогулка по дереву всегда будет O (log n). Вы сами записывали реализацию дерева? Вы всегда можете просто привязать ссылку к текущему элементу с наименьшим значением рядом с вашей структурой данных и обновлять его при добавлении/удалении узлов. (Если вы не написали дерево, вы также можете сделать это, обернув реализацию дерева в собственном объекте обертку, который делает то же самое.)
Если по минимального элемента вы имеете в виду элемент с наименьшим значением, то вы можете использовать TreeSet с пользовательским номером Comparator, который сортирует элементы в правильном порядке, чтобы сохранить отдельные элементы, а затем просто позвоните по номеру SortedSet#first() или #last(), чтобы получить как можно более высокие/наименьшие значения.
Обратите внимание, что вставка новых элементов в TreeSet немного медленнее по сравнению с другими наборами/списками, но если у вас нет большого количества элементов, которые постоянно меняются, это не должно быть проблемой.
Я уверен, что это (красно-черное дерево) будет «O (log n)». – Rudiger
Rudiger правильно: TreeSet реализован с помощью TreeMap (находится в документах), а TreeMap - красно-черное дерево: http://java.sun.com/javase/6/docs/api/java/util /TreeMap.html –
Если элементы уже «сопоставимы», вам даже не нужен «компаратор». – trashgod
Это может показаться глупым, но если вы в основном обращаетесь к минимальному элементу и не слишком сильно меняете дерево, то лучшим решением может оказаться указатель на минимальный элемент add/delete (на любом дереве).
Обратите внимание, что это будет работать только в том случае, если вы используете дерево. Если вы берете заданное дерево (с заданным интерфейсом), сохранение указателя может оказаться невозможным (но значение ...). – Anna
Добавление/удаление узлов в BST равно O (log n), поэтому сохранение минимального указателя в один и тот же момент времени не изменяет алгоритмическую сложность. Планировщик CFS ядра Linux делает это для своих задач на самом деле: см. 'Cfs_rq.rb_leftmost' в'/usr/src/linux/kernel/sched_fair.c'. – ephemient
Существует реализация в TAOCP, в которой используются «запасные» указатели в неполных узлах для выполнения двойного связанного списка по узлам по порядку (я не помню подробностей прямо сейчас, но я имею в виду, что у вас есть иметь флаг «has_child» для каждого направления, чтобы он работал).
С этим и указателем начала вы можете иметь начальный элемент в O (1) раз.
Это решение не быстрее и эффективнее, чем кеширование минимума.
Вы хотите сказать: http://en.wikipedia.org/wiki/Threaded_binary_tree? –
@Martinho: Это будет один. Хорошая ссылка. – dmckee
Если вы можете использовать небольшую память, это звучит так, будто комбинированная коллекция может работать на вас.
Например, то, что вы ищете, похоже на связанный список. Вы всегда можете получить минимальный элемент, но вставка или поиск произвольного узла может занять больше времени, потому что вам нужно выполнить поиск O (n)
Если вы объедините связанный список и дерево, вы можете получить лучшее из оба мира. Чтобы найти элемент для операций get/insert/delete, вы должны использовать дерево для поиска элемента. У узла «владельца» элемента должен быть способ переходить от дерева к связанному списку для операций удаления. Также связанный список должен быть дважды связанным списком.
Я думаю, что получение наименьшего элемента будет O (1), любой произвольный поиск/удаление будет O (logN) - я думаю, что даже вставка будет O (logN), потому что вы можете найти, куда ее поместить в дереве, посмотрите на предыдущий элемент и перейдите к узлу связанного списка, затем добавьте «next».
Хм, это начинает казаться очень полезной структурой данных, возможно, немного расточительно в памяти, но я не думаю, что любая операция была бы хуже, чем O (logN), если вам не нужно балансировать дерево.
Если вы обновите/«upcomplex» свое двоичное дерево до threaded binary tree, вы можете получить O (1) первый и последний элементы.
Вы в основном держите ссылку на текущий первый и последний узлы.
Сразу после вставки, если предыдущая версия не имеет значения null, сначала обновите ее. Аналогично для последнего.
Всякий раз, когда вы удаляете, сначала проверяете, является ли удаляемый узел первым или последним. И обновите, что сохранили сначала, последним соответствующим образом.
Возможно, вы захотите добавить информацию о том, как часто меняется дерево, и если вы можете жить с вставкой/удалением, являющимся дорогостоящим (для восстановления кэшированной информации). –