при реализации структуры кучи мы можем хранить данные в массиве таким образом, чтобы потомки узла в позиции i находились в позиции 2i и 2i+1.
мой вопрос: почему мы не используем массив для представления двоичных деревьев поиска, а вместо этого мы имеем дело с указателями и т. д.?
Благодарность
Лично
Поскольку с помощью указателей проще динамически увеличивать размер структуры данных.
Я считаю, что проще поддерживать дерево бинов, чем кучу
Алгоритмы балансировки, удаления, вставки элементов в дерево будут изменять только указатели, а не перемещать их физически, как в векторе.
и так далее...
Если положение всех дочерних элементов вычисляется таким образом статически, то массив представляет собой полностью полное, полностью сбалансированное двоичное дерево.
Не все бинарные деревья в «реальной жизни» полностью полны и идеально сбалансированы. Если у вас должно быть несколько особенно длинных ветвей, вам придется сделать весь массив намного больше, чтобы вместить все узлы на самом нижнем уровне.
Если двоичное дерево с привязкой к массиву в основном пусто, большая часть пространства массива тратится впустую.
Если только некоторые из ветвей дерева достаточно глубоки, чтобы добраться до «дна» массива, также много места тратится впустую.
Если дерево (или только одна ветвь) должно расти «глубже», чем позволяет размер массива, это потребует «наращивания» массива, что обычно реализуется как копирование в больший массив. Это затратная по времени операция.
Итак: Использование указателей позволяет нам динамично и гибко наращивать структуру. Представление дерева в виде массива является хорошим академическим упражнением и хорошо подходит для небольших и простых случаев, но часто не удовлетворяет требованиям «настоящих» вычислений.
Главным образом потому, что рекурсивное дерево допускает очень простой код. Если вы сгладите дерево в массив, код станет действительно сложным, потому что вам придется выполнять много бухгалтерских операций, которые делает за вас рекурсивный алгоритм.
Кроме того, дерево высоты N может иметь что угодно между N и 2^(N+1)-1 узлами (. Только фактическим узлам потребуется память. Если вы используете массив, вы всегда должны выделять место для всех узлов (даже пустых), если вы не используете разреженный массив (что сделало бы код еще более сложным).Таким образом, если разреженное дерево высотой 100 легко хранить в памяти, было бы проблематично найти компьютер, который может выделить 20282409603651670423947251286008 байт ОЗУ.
Чтобы вставить элемент в кучу, вы можете разместить его где угодно и поменять местами с его родителем, пока ограничение кучи снова не станет действительным. Swap-with-parent — это операция, которая сохраняет двоичную древовидную структуру кучи нетронутой. Это означает, что куча размера N будет представлена в виде массива из N ячеек, и вы сможете добавить новый элемент за логарифмическое время.
Двоичное дерево поиска можно представить в виде массива размера N, используя ту же структуру представления, что и куча (дочерние элементы 2n и 2n+1), но вставка элемента таким образом намного сложнее, потому что в отличие от ограничения кучи, бинарный поиск ограничение дерева требует выполнения поворотов для получения сбалансированного дерева. Таким образом, либо вам удается сохранить N-узловое дерево в N-ячеечном массиве по цене выше логарифмической, либо вы теряете место, сохраняя дерево в большем массиве (если мне не изменяет память, дерево с красной спиной может тратьте до 50% вашего массива).
Итак, бинарное дерево поиска в массиве интересно только в том случае, если данные внутри него постоянны. И если это так, то вам не нужна структура кучи (дети 2n и 2n+1): вы можете просто отсортировать свой массив и использовать бинарный поиск.
Насколько я знаю, мы можем использовать Array для представления бинарных деревьев поиска. Но более гибко использовать указатели.
Реализация на основе массива полезна, если вам нужна куча, которая используется в качестве приоритетной очереди в алгоритмах графа. В этом случае элементы в куче постоянны, вы выталкиваете самый верхний элемент и вставляете новые элементы. Удаление верхнего элемента (или минимального элемента) требует некоторой повторной балансировки, чтобы снова стать кучей, что можно сделать так, чтобы массив был разумно сбалансирован.
Ссылкой на это является алгоритм Голдберга и Тарьяна об эффективном вычислении оптимального сетевого потока в ориентированных графах, iirc.
Структура данных кучи представляет собой полное двоичное дерево, в отличие от BST. Следовательно, использование массивов не очень полезно для BST.
