Хотя это хорошо работает для кучи, вы в конечном итоге используете огромный объем избыточной памяти для других древовидных структур данных, которые не обязательно имеют полное и завершенное двоичное дерево.Например, это означает, что если у вас есть дерево бинарного поиска из 20 узлов глубиной 5, вам придется использовать массив 2 ^ 5 = 32 вместо 20. Теперь представьте, что вам нужно дерево из 25 узловс глубиной 22. В итоге вы используете огромный массив 4194304, тогда как вы могли бы использовать связанное представление для хранения только 25 узлов.
Вы все еще можете использовать массив и не подвергаться такому обращению к памяти,Просто выделите большой блок памяти в виде массива и используйте индексы массива в качестве указателей на дочерние элементы.
Таким образом, где у вас было
node.left = (node.index*2)
node.right = (node.index*2+1)
Вы просто используете
node.left = <index of left child>
node.right = <index of right child>
Или вы можете просто использовать указатели / ссылки вместо целочисленных индексов для массива, если ваш язык поддерживает это.
Редактировать:
Это может быть не очевидно для всехчто полное двоичное дерево поиска занимает O (2 ^ d) памяти.Существует d уровней, и каждый уровень имеет в два раза больше узлов, чем уровень, в котором находится его родитель (поскольку каждый узел, кроме нижних, имеет ровно двух дочерних элементов - ни одного). бинарная куча - это бинарное дерево (но не бинарное дерево поиска), которое всегда завершено по определению, поэтому реализация на основе массива, описанная OP, не приводит к реальным затратам памяти,Для кучи, это лучший способ реализовать это в коде.OTOH, большинство других двоичных деревьев (особенно Binary Search Trees) не гарантированно завершены.Поэтому, чтобы использовать этот подход, потребуется O (2 ^ глубина) памяти, где глубина может быть равна n, где нам нужно только O (n) памяти в связанной реализации.
Так что мой ответ:да, это лучший способ для кучи.Только не пробуйте это для других двоичных деревьев (если вы не уверены, что они всегда будут полными).