Почему сбалансированный BST не используется повсеместно вместо двоичной кучи в изменяемых структурах?

Мне кажется, что двоичное дерево поиска может делать все, что может двоичная куча, плюс дополнительные вещи.

|                     |   Heap   | Bal. BST |
---------------------------------------------
| Lookup min element  |  O(1)    |  O(1)    |
---------------------------------------------
| Add an element      |  O(logn) |  O(logn) |
---------------------------------------------    
| Find and Remove     |  O(n)    |  O(logn) |
| an element          |          |          |
---------------------------------------------

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

Преимущества, которые я вижу в Binary Heap:

i) Проще реализовать ii) Выделенная память непрерывна (и, следовательно, более быстрый доступ)

(i) не является проблемой, поскольку я редко буду реализовывать любой из них с нуля. Если мы много мутируем элементы, то (ii) не является значительным преимуществом.

Мне кажется, что сбалансированное бинарное дерево может делать все, что может бинарная куча, тогда почему оно не используется повсеместно? (Подобно тому, как двусвязные списки используются повсеместно вместо односвязных списков)


algorithm red-black-tree binary-search-tree binary-heap
person Anoop    schedule 27.08.2018    source источник

Ответы (3)


arrow_upward
3
arrow_downward

Одна поправка, нахождение минимума O(log(n)) для BST. Другие области, где куча имеет лучшие показатели, чем BST. Добавление элемента в кучу на практике имеет ожидаемое значение O(1) (в среднем 2 сравнения), что лучше, чем BST. Превращение списка в кучу занимает время O(n), что опять же лучше, чем O(n log(n)) для BST.

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

person btilly    schedule 27.08.2018
comment
+1. И хотя удаление минимального элемента как из кучи, так и из красно-черного дерева составляет O(log n), операции перебалансировки в последнем намного сложнее, поэтому постоянный коэффициент значительно выше даже в стороне из соображений локальности памяти. - person ruakh; 28.08.2018
comment
Я считаю, что вы можете реализовать сбалансированные BST, чтобы поиск минимума был O (1). Просто держите указатель на крайний левый узел. - person Cody Johnson; 05.06.2019

arrow_upward
3
arrow_downward

Для двоичных куч:

  • Более простая реализация является значительным преимуществом, поскольку она соответствует более высокой производительности — просто меньше кода для выполнения.
  • Непрерывная память — фантастическое преимущество из-за снижения накладных расходов на выделение памяти и локализации ссылок.
  • Значительно сниженное потребление памяти — еще одно большое преимущество, о котором вы не упомянули.

Кроме того, односвязные списки используются в реальной работе чаще, чем двусвязные. Однако часто это не совсем списки, потому что мы используем тот факт, что у односвязных списков могут быть общие хвосты.

person Matt Timmermans    schedule 28.08.2018

arrow_upward
2
arrow_downward

Сбалансированный BST имеет избыточное пространство, по крайней мере, два указателя на элемент (больше, если информация о балансе хранится отдельно). Это важно, когда предметы маленькие.

person David Eisenstat    schedule 27.08.2018