Если я храню двоичное дерево в массиве, как мне избежать потерянного пространства? - PullRequest
Новая
       53

Если я храню двоичное дерево в массиве, как мне избежать потерянного пространства?

4 голосов
/ 17 июня 2011

Часто нам нужны деревья в алгоритмах, и я получаю дерево с большим количеством указателей и рекурсией.
Иногда мне нужно больше скорости, и я помещаю дерево в 2D-массив следующим образом: 

Example of a binary tree stored in an array
+-----------------+
|0eeeeeeeeeeeeeeee| //no pointers needed, parent/child, is y dimension,
|11       dddddddd| //sibbling is x dimension of the array.
|2222         cccc|  //The 123 tree is stored root up.
|33333333       bb|  //Notice how the abc-tree is stored upside down 
|4444444444444444a|  //The wasted space in the middle, is offset by the fact 
+-----------------+  //that you do not need up, down, and sibbling pointers.

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

Но обратите внимание, что потраченное впустую пространство посередине ....

Как избавиться от / использовать повторно потраченное впустую пространство?

Требования
Я использую эту структуру, только если мне нужен каждый последний бит скорости, поэтому решение с большим количеством переводов и вычислений адресов, чтобы добраться до этого места, не будет полезным.

1 Ответ

12 голосов
/ 17 июня 2011

Двоичное дерево может храниться в массиве более эффективно, как описано здесь: http://en.wikipedia.org/wiki/Binary_tree#Arrays:

enter image description here

Из Википедии:

В этом компактном расположении, если узел имеет индекс i, его дочерние элементы находятся по индексам (2i + 1) (для левого дочернего элемента) и (2i + 2) (для правого), тогда как его родительский элемент (если есть)) находится по индексу floor((i-1)/2) (при условии, что корень имеет индекс ноль).

Этот метод выигрывает от более компактного хранения и лучшей привязки, особенно во время обхода предварительного заказа.Однако выращивание обходится дорого и тратит пространство, пропорциональное (2H - n) для дерева высотой H с n узлами.

Другими словами, оно будет тратить пространство, если ваше деревоне полное двоичное дерево, но оно все равно будет немного более компактным, чем простой двумерный массив.

...