всегда возможно построить двоичное дерево в массиве, используя простую арифметику для поиска дочерних узлов от родителя.Обычный метод (особенно для двоичных кучи) заключается в использовании следующего ...
left_child_index = (2 * parent_index) + 1
right_child_index = (2 * parent_index) + 2
Таким образом, корневой узел в 0 имеет дочерние элементы в 1 и 2, узел в 1 имеет дочерние элементы в 3 и 4 и т. Д..
Недостатком этой схемы является то, что, хотя вы получаете пространство, не сохраняя указатели, вы, как правило, теряете пространство из-за необходимости оставлять пробелы в массиве для неиспользуемых узлов.Двоичные кучи позволяют избежать этого, будучи полными двоичными деревьями - каждый узел в диапазоне для текущего количества элементов является допустимым.Это работает для кучи, но не может работать для операций бинарного дерева поиска.
Пока вы можете изменять размеры своих массивов (например, std::vector в C ++), вам не нужно ставить верхнюю границу числавставок, но вы можете получить много пробелов в более глубоких частях вашего массива, особенно если дерево становится несбалансированным.
Вам также нужен какой-то способ определить, является ли позицияв массиве содержится действительный узел или нет - либо флаг, либо значение данных, которое не может присутствовать в допустимом узле.Флаги потенциально могут храниться в виде упакованного битового массива, отдельно от основных узлов.
Еще один недостаток заключается в том, что реструктуризация дерева означает перемещение данных, а не просто настройку указателей.Повороты указателя (необходимые для многих сбалансированных бинарных деревьев, таких как красно-черные деревья и деревья AVL) становятся потенциально очень дорогостоящими операциями - им не нужно просто перемещать обычные три узла, но все поддерево происходит от повернутых узлов.
Тем не менее, если ваши предметы очень маленькие, и если ваше дерево останется маленьким или у вас все в порядке с простым несбалансированным деревом, то вполне возможно, что эта схема будет полезна.Это может быть правдоподобно в виде структуры данных набора целых чисел, может быть.
Кстати - «правдоподобный» не означает «рекомендуемый».Даже если вам удастся найти случай, когда он более эффективен, мне трудно поверить, что время разработки было оправданным.
Возможно, более полезно ...
Множественные деревья содержат небольшие массивы элементов в каждом узле, а не обычный ключ.Они чаще всего используются для индексов базы данных на жестком диске.Наиболее известными являются B-деревья, B + деревья и B * деревья.
Многолинейные деревья имеют указатели дочерних узлов, но для узла, который может содержать не более n ключей, количество дочерних указателей обычно равно n илиn + 1 - не дважды n.Кроме того, общей стратегией является использование разных макетов узлов для узлов ветвления и листьев.Только узлы ветвления имеют дочерние указатели.Каждый элемент данных находится в листовом узле, и только конечные узлы содержат неключевые данные.Узлы ветвления используются только для поиска.Поскольку конечные узлы являются безусловно самыми многочисленными узлами, отсутствие дочерних указателей в них является полезным сохранением.
Однако - узлы многострочного дерева редко упаковываются полностью.Опять же, есть место для неиспользуемых слотов массива.Обычное правило заключается в том, что каждый узел (кроме корневого) должен быть заполнен как минимум наполовину.Некоторые реализации прикладывают немало усилий, чтобы избежать разделения узлов и, таким образом, минимизировать затраты пространства, но обычно ожидаемые издержки примерно пропорциональны количеству элементов.
Я также слышал о форме дереваон содержит несколько ключей на узел, но имеет только два дочерних указателя на узел.Боюсь, я даже не помню, как это называется.
Также возможно хранить пары (родительский указатель, дочерний указатель) в отдельной структуре данных.Это довольно распространено для представления деревьев в базах данных с использованием таблицы пар (родительский идентификатор, дочерний идентификатор) или таблицы (родительский идентификатор, индекс родного брата, дочерний идентификатор) или чего-либо еще.Одним из преимуществ является то, что вам не нужно хранить нулевые указатели.
Однако, возможно, лучшим вариантом, вместо того, чтобы пытаться уменьшить или устранить издержки на хранение указателей, является использование этих накладных расходов для лучшего использования. Двоичные двоичные деревья лучше используют дочерние указатели для поддержки эффективных обходов дерева - http://en.wikipedia.org/wiki/Threaded_binary_tree.