Graphics Reference
In-Depth Information
allocating the tree nodes from within an array a 16-bit index value from the start of
the array can be used instead. This will work for both static and dynamic trees. If the
tree is guaranteed to be static, even more range can be had by making the offsets
relative from the parent node.
At the cost of some extra traversal overhead, it is also possible to combine the
pointer and index representation. One extra reserved bit could indicate that the stored
value should instead be used as an index into a separate array of either pointers or
wider offset values.
6.6.4
Cache-friendlier Structures (Nonbinary Trees)
Execution time in modern architectures is often more limited by cache issues related to
fetching data from memory than the number of instructions executed. It can therefore
pay off to use nonconventional structures that although more complicated to traverse
take up less memory and have a more cache-friendly access pattern.
One such possible representation is merging sets of three binary tree nodes (parent
plus left and right child) into a “tri-node,” a fused node containing all three nodes.
The original set of three nodes has two internal links connecting the parent node with
the children and four external links connected to the rest of the tree. The new node
does not need any internal links, just the four external links.
For a four-level (15-node) complete binary tree, 14 internal links are needed. The
corresponding tri-node tree has two levels (four nodes) and just four internal links
(Figure 6.8). A six-level (63-node) binary tree has 62 internal links; the tri-node tree
only 20. In general, the corresponding tri-node tree requires a third of the links of
a complete binary tree, an even better reduction than with the preorder traversal
order representation. In addition, tri-nodes can be output in a breadth-first fashion,
potentially allowing the top
n
levels of the hierarchy to stay in cache.
The drawback is the additional processing required to traverse the tree. In addition,
when a tree is not complete nodes go empty in the tri-node, wasting memory. A flag
is also needed to indicate whether the node is used or empty. For this reason, tri-node
trees are better suited for dense trees. For sparse trees, the preorder traversal order
representation is preferable.
BAC
A
B
C
D
E
F
G
HD I
LFM
H
I
J
K
L
NMO
JEK
NGO
(a)
(b)
Figure 6.8
(a) A four-level binary tree. (b) The corresponding two-level tri-node tree.
