## 如何生成最大不平衡的AVL树？内容来源于 Stack Overflow，并遵循CC BY-SA 3.0许可协议进行翻译与使用

• 回答 (3)
• 关注 (0)
• 查看 (142)

AVL树具有这样的优点：如果从空树开始，按升序(或降序)插入节点，则树总是完全平衡的(也就是说，对于给定的节点数，树有其最小高度)。从空树T0开始，为每个节点n生成精确平衡的AVL树TN的整数键序列是简单的。

• K1=0
• Kn+1=kn+1，即kn=n-1

• 最大(K1，...，kn)-min(K1，...，kn)+1≤2n

```insert 0
=> Fibonacci tree of height 1 (1 node):
0
insert 8
=> Fibonacci tree of height 2 (2 nodes):
0
8
insert -8
insert 12
=> Fibonacci tree of height 3 (4 nodes):
0
-8               8
12
insert -4
insert 4
insert 14
=> Fibonacci tree of height 4 (7 nodes):
0
-8               8
-4       4      12
14
insert -12
insert -2
insert 6
insert 10
insert 15
=> Fibonacci tree of height 5 (12 nodes):
0
-8               8
-12      -4       4      12
-2       6  10  14
15```

```void fibonacci_subtree(int root, int height, int child_delta)
{
if (height == 1) {
insert_into_tree(root);
} else if (height == 2) {
insert_into_tree(root + child_delta);
} else if (height >= 3) {
fibonacci_subtree(root - child_delta, height - 2, child_delta >> 1);
fibonacci_subtree(root + child_delta, height - 1, child_delta >> 1);
}
}

...
for (height = 1; height <= max_height; height++) {
fibonacci_subtree(0, height, 1 << (max_height - 2));
}```

```insert 0
=> Fibonacci tree of height 1 (1 node):
0
insert 3
=> Fibonacci tree of height 2 (2 nodes):
0
3
insert -3
insert 5
=> Fibonacci tree of height 3 (4 nodes):
0
-3               3
5
insert -2
insert 1
insert 6
=> Fibonacci tree of height 4 (7 nodes):
0
-3               3
-2       1       5
6
insert -4
insert -1
insert 2
insert 4
insert 7
=> Fibonacci tree of height 5 (12 nodes):
0
-3               3
-4      -2       1       5
-1       2   4   6
7```

```static int fibs[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170 };

void fibonacci_subtree(int root, int height, int *fib)
{
if (height == 1) {
insert_into_tree(root);
} else if (height == 2) {
insert_into_tree(root + *fib);
} else if (height >= 3) {
fibonacci_subtree(root - *fib, height - 2, fib - 2);
fibonacci_subtree(root + *fib, height - 1, fib - 1);
}
}

...
for (height = 1; height <= max_height; height++) {
fibonacci_subtree(0, height, fibs + max_height - 1);
}```