Fibonacci tree
The Fibonacci tree is the subject of graph theory , but above all a data structure in computer science . It represents a special case of the AVL tree , namely the AVL tree with the smallest number of nodes for a given height . The name suggests that Fibonacci trees, similar to Fibonacci numbers , can be defined recursively .
If you remove any node of a Fibonacci tree, from the third level onwards a tree is created that is no longer a Fibonacci tree. In the example below, it is no longer an AVL tree, if z. B. a 1 that is not the left one is removed.
As with the Fibonacci numbers, the number of the golden section is a kind of "base of the logarithm" . The ideal basis for a binary tree would of course be to maintain more stringent balance criteria, e.g. B. the height balance in a fully balanced binary tree , but is so complex after modifications to the tree that on average the total costs of such trees are higher, unless the application is extremely dominated by searching. The AVL criterion appears to be an attractive compromise.
Fibonacci trees are used as extreme cases and objects of comparison when considering the efficiency of height-balanced trees , especially AVL trees.
Recursive definition
The recursive definition is done like this:
- The level 0 Fibonacci tree is the empty tree .
- The level 1 Fibonacci tree is a tree that consists of only one node .
- A Fibonacci tree of level (with ) consists of a root whose left child is a Fibonacci tree of level and whose right child is a Fibonacci tree of level .
properties
- All internal nodes (nodes that are not leaves) have a balance factor of –1.
- The Fibonacci tree of level (with ) has the height .
- If the number of nodes in the Fibonacci tree is the level , then
- For
- If the number of leaf nodes of the Fibonacci tree is the level , then applies
- For
- If the number of insertion points ( half leaves ; 1 leaf = 2 half leaves) of the Fibonacci tree is the level , then applies
- For
- With the help of the designation for the -th Fibonacci number , these quantities can also be expressed as follows:
- (For every directed binary tree .)
- At a given height, a Fibonacci tree corresponds to an AVL tree with the minimum number of nodes, so it is the worst balanced.
- According to Moivre-Binet's formula is the number of nodes
for and for .
- This allows the height to be estimated depending on the number of nodes
- with , and .
Other thinnest AVL trees
If you swap the left child with the right child at a node, a thinnest AVL tree is created again. This gives the number of thinnest AVL trees the height
a 0 = 1 a 1 = 1 a h = ( a h –1 • a h –2 ) • 2 (for h ≥ 2) ( h –1 left & h –2 right) + vice versa
That is in closed form , which is great for function
with approximates.
The number of all AVL trees of the height can be calculated as follows:
A 0 = 1 A 1 = 1 A h = ( A h –1 • A h –2 ) • 2 + ( A h –1 • A h –1 ) (for h ≥ 2) ( h –1 left & h –2 right) + vice versa + ( h -1 left & h -1 right)
It is the sequence A029758 in OEIS , which is for the function
with or approximates.
Both sequences are double exponential, but with different exponents - with the result that the thinnest trees with increasing tree height are proportionally rapidly (double exponential) rare.
It follows that the number of nodes for the left and right subtree can be very different. For example, an AVL tree of height 32-4 = 28 can in the extreme case have a branch with 2 27 -1 = 134217727 ( complete binary tree of height 27) on the left and one with (Fibonacci tree of height 26) node on the right, which is a node ratio from 134217727/514227 ≈ 261 results. At a height of 64-5 = 59, we arrive with 2 58 -1 = 288230376151711743 and n 57 = 1548008755918 to a ratio of about 186,194th
Search depth
The search depth of a node is the number of edges from the root to the node. For an external node in a binary search tree , it corresponds to the number of comparisons required; for internal nodes, the latter is 1 higher.
Maximum and minimum search depth of an external node
The maximum search depth of an external node in a Fibonacci tree is with as the height.
The minimum search depth of an external node in a Fibonacci tree is . Proof:
The two external leaves of a tree of height 1 have search depth 1.
The right external leaf of a Fibonacci tree of height 2 has search depth 1.
In the recursive composition of a Fibonacci tree of height from one of height and one of height is found the minimum search depth in the subtree of the height . Hence the claim follows. ■
Since the relationship between the maximum and minimum search depth is in red-black trees , the Fibonacci trees can be colored with the colors red and black according to the rules of the red-black tree.
Path length sum and mean search depth
The sum of the search depths over all internal nodes of the Fibonacci tree of the level , in the notation of the section Search depths and path length sums , can be recursively calculated as follows:
(empty search tree) (only root) (new root) (left child) (right child) for h ≥ 2.
This is satisfied by
- .
Proof:
- . ■
The external path length , i.e. i. the sum of the search depths over all external nodes with the Fibonacci tree of the level is then
Thus, the sequence A067331 in OEIS .
Using Moivre-Binet's formula, we can derive from this for Fibonacci trees via the mean search depth of the limit of efficiency to find existing keys for :
The same value results for the limit of efficiency to determine the absence of keys.
Proportion of unbalanced nodes in AVL trees
A somewhat more differentiated recursion allows insight into the inner asymmetries of the AVL trees. Let U h , u , g be the number of AVL trees of height h with u unbalanced (right or left- heavy ) and g balanced nodes (with children of the same height). Then after considerations is analogous to above
has empty tree h = 0, u = 0, g = 0 has only root h = 1, u = 0, g = 1 ,
because with children of different heights there is a u-knot and with children of the same height a g-knot. The proportion of unbalanced nodes at all nodes is , and this has the multiplicity , so that the proportion averaged over all AVL trees of height h
results. Because the number of all AVL trees of the height is the same as above .
Table 2 shows numerical values for small .
Average search depth for AVL trees
Estimation using recursion over the height
Average search depths can be calculated using the same scheme. For the sake of comparability, we choose the search depth of the external nodes (leaves), i. i. the external path length . Let the number of AVL trees be the height with external leaves and the external path length . Then
the empty tree of height 0 with 1 external leaf and external path length 0 the tree of height 1 (root only) with 2 external leaves and external path length 2 ,
because with the recursive composition of two AVL trees, the number of external leaves increases from
n l and n r on n l + n r =: n
and the external path length of
p l and p r on p l + p r + n =: p ,
since the path to the root is increased by 1 for each leaf. The number of all AVL trees of the height is
- .
It's the same as above .
height | Number of trees |
Share bad design weighed |
Number of external sheets |
external path length |
average lengthened delay |
|||||||
node | root |
|
||||||||||
1 | 1 | 0.000 | 0.00000 | 2 | 2.0000 | 2 | 2 | 2.0000 | 2 | 1.0000 | ||
2 | 3 | 0.333 | 0.66667 | 3 | 3.3333 | 4th | 5 | 6.0000 | 8th | 1.0344 | ||
3 | 15th | 0.311 | 0.40000 | 5 | 6.1333 | 8th | 12 | 16,533 | 24 | 1.0263 | ||
4th | 315 | 0.303 | 0.28571 | 8th | 11.467 | 16 | 25th | 41,524 | 64 | 1.0260 | ||
5 | 108675 | 0.285 | 0.08696 | 13 | 22,470 | 32 | 50 | 103.34 | 160 | 1.0228 | ||
6th | 11878720875 | 0.274 | 5.76e-3 | 21st | 44.876 | 64 | 96 | 251.21 | 384 | 1.0194 | ||
7th | 141106591 466142946875 |
0.269 | 1.83e-5 | 34 | 89.751 | 128 | 180 | 592.16 | 896 | 1.0167 | ||
8th | 19911 070158545297 149037891328 865229296875 |
0.267 | 1,7e-10 | 55 | 179.50 | 256 | 331 | 1363.8 | 2048 | 1.0146 | ||
Table 2: Unbalanced Nodes and External Path Length by Height |
The column Proportion of unbalanced nodes contains that of the section #Part of unbalanced nodes in AVL trees , while the column Proportion of unbalanced roots means the percentage of trees with unbalanced roots within the total of AVL trees of height .
In the column v h , the external path length is compared with the ideal (minimum) external path length , which depends on the number of nodes (see Table 3), and the height is then averaged over all AVL trees .
Exact calculation
The assumption of equal probabilities for all AVL tree forms is a simplification. It is true that every possible form of a binary tree can be built up through specific insertions, but there are preferred forms of the AVL trees that arise more frequently than others after rotations. If all sequences (permutations) of the insertion are considered to be equally probable, then z. For example, for the 17 AVL trees with node number 7 (see Table 3) for the balanced tree (a complete binary tree of height 3) a frequency of 2160 and for the remaining 16 (which are all Fibonacci trees of height 4) for one half had a frequency of 144 and for the other half a frequency of 216.
Bone surfactant- paid |
average height |
Number of trees |
Share bad design -weighed |
frequency | external path length |
average lengthened delay |
||||
node | root |
|
||||||||
1 | 1.00 | 1 | 0.000 | 0.000 | 1 | 1 | 2 | 2.00 | 2 | 1.0000 |
2 | 2.00 | 2 | 0.500 | 1,000 | 1 | 1 | 5 | 5.00 | 5 | 1.0000 |
3 | 2.00 | 1 | 0.000 | 0.000 | 6th | 6th | 8th | 8.00 | 8th | 1.0000 |
4th | 3.00 | 4th | 0.500 | 1,000 | 6th | 6th | 12 | 12.00 | 12 | 1.0000 |
5 | 3.00 | 6th | 0.280 | 0.600 | 12 | 36 | 16 | 16.00 | 16 | 1.0000 |
6th | 3.00 | 4th | 0.167 | 0.000 | 144 | 216 | 20th | 20.00 | 20th | 1.0000 |
7th | 3.57 | 17th | 0.327 | 0.571 | 144 | 2160 | 24 | 24.57 | 25th | 1.0238 |
8th | 4.00 | 32 | 0.393 | 1,000 | 288 | 3240 | 29 | 29.36 | 30th | 1.0123 |
9 | 4.00 | 44 | 0.333 | 0.714 | 3456 | 25920 | 34 | 34.24 | 35 | 1.0070 |
10 | 4.00 | 60 | 0.286 | 0.429 | 25056 | 194400 | 39 | 39.07 | 40 | 1.0018 |
11 | 4.00 | 70 | 0.249 | 0.117 | 114048 | 2332800 | 44 | 44.00 | 44 | 1.0000 |
12 | 4.19 | 184 | 0.267 | 0.193 | 466560 | 17418240 | 49 | 49.19 | 50 | 1.0039 |
13 | 4.51 | 476 | 0.311 | 0.509 | 933120 | 242611200 | 54 | 54.58 | 56 | 1.0108 |
14th | 4.79 | 872 | 0.342 | 0.790 | 8823168 | 2774865600 | 59 | 60.10 | 62 | 1.0187 |
15th | 4.96 | 1553 | 0.351 | 0.888 | 116173440 | 54979430400 | 64 | 65.72 | 68 | 1.0268 |
16 | 5.00 | 2720 | 0.340 | 0.776 | 519747840 | 149860238400 | 70 | 71.41 | 73 | 1.0201 |
17th | 5.00 | 4288 | 0.324 | 0.609 | 2769500160 | 1978587648000 | 76 | 77.13 | 79 | 1.0149 |
18th | 5.00 | 6312 | 0.309 | 0.453 | 60134731776 | 22812754464000 | 82 | 82.88 | 85 | 1.0107 |
19th | 5.00 | 9004 | 0.296 | 0.295 | 904805406720 | 398794586112000 | 88 | 88.66 | 91 | 1.0075 |
20th | 5.02 | 16088 | 0.287 | 0.179 | 5394695644800 | 3968960489625600 | 94 | 94.52 | 97 | 1.0056 |
21st | 5.10 | 36900 | 0.287 | 0.159 | 10789391289600 | 74716118765568000 | 100 | 100.49 | 103 | 1.0049 |
22nd | 5.22 | 82984 | 0.293 | 0.237 | 97480461657600 | 1134885141276480000 | 106 | 106.55 | 110 | 1.0052 |
23 | 5.38 | 174374 | 0.304 | 0.380 | 1362760719022080 | 28970685819518976000 | 112 | 112.71 | 117 | 1.0064 |
24 | 5.54 | 346048 | 0.315 | 0.543 | 7172727971696640 | 337716405039775104000 | 118 | 118.95 | 123 | 1.0080 |
25th | 5.70 | 653096 | 0.325 | 0.691 | 70893673900600320 | 7478785384139059200000 | 124 | 125.26 | 130 | 1.0101 |
26th | 5.82 | 1199384 | 0.331 | 0.795 | 990569400644966400 | 134732114837823140352000 | 130 | 131.63 | 137 | 1.0125 |
Table 3: Unbalanced nodes and external path length by insertion order |
When drawing up Table 3, all sequences of insertion according to the AVL insertion algorithm were given the same weight for each node number . (Therefore the frequencies add up to n ! ). The big difference between minimum and maximum frequency resp. shows that the tree shapes that arise are very different in frequency, with the most common also having minimal external path lengths . The latter is also the reference point for the mean extension of the external path length v n . Fibonacci trees are quite rare, but they do not necessarily have maximum external path lengths .
These frequencies are much more difficult to calculate than the above numbers of trees and extensions of the path length v h , for which the AVL trees of a fixed height are assumed to be equally likely. For small trees, however, v n and v h differ only slightly. R. W. Floyd estimates the mean effort to determine the absence of a -th among keys , which asymptotically corresponds to a value of for v n .
The columns , and are the sequences A006265, A001855, respectively. A228155 in OEIS .
Flank depth
The left and right flank depth is the length of the path from the root to the minimum, respectively. designated to the maximum. Since an AVL tree of the same height is obtained by mirroring an AVL tree left-right, the left and right flank depths have the same set of values. For an AVL tree of height it is at most and at least
- ,
in accordance with the considerations for the minimum search depth of Fibonacci trees.
In a similar way as above, the left and right flank depth can be averaged over all AVL trees of the height . Let the number of AVL trees be the height with left flank depth and right flank depth . Then
because with the recursive composition of two AVL trees the flank depth increases by 1 on both sides and in each of the groups “left higher”, “right higher” and “equal high” all options on the left can be combined with all options on the right and these numbers are totaled up. The following applies as a control: The number of all AVL trees of the height is
- .
It's the same as above .
The mean left and right flank depth for an AVL tree of the height is then
-
dh .
Numerical values for small are in Table 1.
Average depth of descent when deleting
Similarly, an average depth of descent can be calculated which, when deleting a node, has to be descended from its height to the (half) leaves on its left or right in order to find a node that can take the place of the node to be deleted. For a single node at the height , its mean corresponds to the d h just calculated .
The mean value over all nodes of an AVL tree is, however, much lower, since most of the nodes are at a low height. Let the number of AVL trees be the height with nodes, left flank depth and flank depth sum and right flank depth and flank depth sum . Let the flank depth sum be the sum of all left resp. right flank depths of a given tree. Then
AVL tree with 1 node AVL tree with 2 nodes on the left AVL tree with 2 nodes to the right AVL tree with 3 nodes
because with the recursive composition of two AVL trees, the addition of the new root increases the flank depths on both sides by 1, with the left and right flank depth sum, the related flank depth is added to the contribution of the 2 trees and in each of the groups " higher left ”,“ higher right ”and“ equal ”all options on the left are combined with all options on the right and these numbers are totaled.
The number of AVL trees of the height with nodes and the sum of the left flank depth is
- .
These trees therefore have the mean left flank depth per node . The edge depth averaged over all AVL trees of height is therefore
- .
Because we have with the same as above .
Since for reasons of symmetry, the length of a path from the root to a node at a certain height in unit access probabilities does not depend on changes of direction, which is average depth of descent averaged over all the AVL trees of height likewise .
Some numerical values:
1 | 0 | 0 | 0 | 0 |
2 | 0 | 0.6667 | 1 | 0.27778 |
3 | 1 | 1.5333 | 2 | 0.49921 |
4th | 1 | 2.4095 | 3 | 0.66886 |
5 | 2 | 3.3714 | 4th | 0.79391 |
6th | 2 | 4.3687 | 5 | 0.87686 |
7th | 3 | 5.3686 | 6th | 0.92801 |
8th | 3 | 6.3686 | 7th | 0.95865 |
9 | 4th | 7.3686 | 8th | 0.97660 |
10 | 4th | 8.3686 | 9 | 0.98693 |
Table 1 |
The very simple consideration from the Delete section provides
- .
See also
literature
- Donald E. Knuth : The Art of Computer Programming : Volume 3 Sorting and Searching . 2nd Edition. Addison-Wesley, Reading MA 1997, ISBN 0-201-89685-0 , 6.2.3 Balanced Trees.
- Kurt Mehlhorn data structures and efficient algorithms Teubner Stuttgart 1988, ISBN 3-519-12255-3 .
Individual evidence
- ↑ The height as the maximum number of node levels or numerically the same, if there are (keyless) external leaves as with #Knuth , as the maximum number of edges from the external leaf to the root.
- ↑ according to Knuth Theorem A, the formulation of Adelson-Velsky / Landis
- ↑ #Knuth a. a. Cit., P. 467.
- ^ AV Aho and NJA Sloane : Some Doubly Exponential Sequences . In: Fib. Quart., 11, Bell Laboratories Murray Hill, New Jersey . 1970, pp. 429-437.
- ↑ external path length at #Knuth a. a. O. pp. 399-400
- ↑ E.g. the Fibonacci tree has the external path length . The AVL tree with and has the full binary tree with 15 nodes on one side and a Fibonacci tree with 4 nodes on the other.
- ↑ With the proportions of trees with unbalanced roots, however, the different weighting becomes visible in an extreme form.
- ↑ quoted from #Knuth a. a. Cit., P. 468
- ↑ http://oeis.org/A006265
- ↑ http://oeis.org/A001855
- ↑ http://oeis.org/A228155