Кучи против двоичных деревьев - как реализовать?

Question

при реализации структуры кучи мы можем хранить данные в массиве так, чтобы дочерние элементы узла в позиции i находились в позициях 2i и 2i + 1.

Мой вопрос заключается в том, почему мы не используеммассив для представления двоичных деревьев поиска, и вместо этого мы имеем дело с указателями и т. д .?

спасибо

Answer 1

Лично

1. Потому что с помощью указателей легче увеличить размер структуры данных динамически

2. Я считаю, что легче поддерживать бен дерево чем куча

3. Алгоритмы балансировки, удаления, вставки элементов в дерево будут изменять только указатели, а не физически перемещаться, как в векторе.

и так далее ...

Answer 2

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

Не все бинарные деревья в «реальной жизни» являются полностью полными и идеально сбалансированными. Если у вас должно получиться несколько особенно длинных ветвей, вам придется увеличить весь массив, чтобы разместить все узлы на самом нижнем уровне.

• Если двоичное дерево, связанное с массивом, в основном пустое, большая часть пространства массива теряется.

• Если только некоторые из ветвей дерева достаточно глубоки, чтобы достичь «дна» массива, значит, много места теряется.

• Если дерево (или только одна ветвь) должно расти «глубже», чем позволяет размер массива, это потребует «увеличения» массива, что обычно реализуется как копирование в больший массив. Это дорогостоящая операция.

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

Answer 3

В основном потому, что рекурсивное дерево допускает очень простой код. Если вы сведете дерево в массив, код становится действительно сложным, потому что вам приходится много вести, что делает для вас рекурсивный алгоритм.

Кроме того, дерево высотой N может иметь что угодно между N и 2^(N+1)-1 узлами (только памятью потребуются только фактические узлы. Если вы используете массив, вы должны всегда выделять пространство для всех узлов (даже пустых) если только вы не используете разреженный массив (который сделает код еще более сложным). Поэтому, хотя разреженное дерево высотой 100 легко хранить в памяти, было бы проблематично найти компьютер, который может выделить 20282409603651670423947251286008 байтов ОЗУ. 1004 *

Answer 4

Чтобы вставить элемент в кучу, вы можете поместить его в любое место и поменять его местами с родительским элементом, пока ограничение кучи снова не вступит в силу. Swap-with-parent - это операция, которая сохраняет структуру двоичного дерева кучи без изменений. Это означает, что куча размера N будет представлена ​​как массив из N-ячеек, и вы можете добавить новый элемент в логарифмическом времени.

Двоичное дерево поиска может быть представлено в виде массива размера N, использующего ту же структуру представления, что и куча (дочерние элементы 2n и 2n + 1), но вставить элемент таким способом намного сложнее, поскольку в отличие от ограничения кучи, Ограничение бинарного дерева поиска требует выполнения поворотов для получения сбалансированного дерева. Таким образом, либо вам удастся сохранить дерево с N-узлами в массиве из N-ячеек по цене, превышающей логарифмический, либо вы тратите пространство, сохраняя дерево в большем массиве (если мне не изменяет память, красное дерево тратить до 50% вашего массива).

Итак, двоичное дерево поиска в массиве интересно только в том случае, если данные внутри него постоянны. И если это так, то вам не нужна структура кучи (дочерние элементы 2n и 2n + 1): вы можете просто отсортировать массив и использовать двоичный поиск .

Answer 5

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

Ссылкой для этого является алгоритм Голдберга и Тарьяна об эффективном вычислении оптимального сетевого потока в ориентированных графах, iirc.

Answer 6

Насколько я знаю, мы можем использовать Array для представления двоичных деревьев поиска. Но указатели более гибкие.