AVL 树是基于二叉搜索树的。但是它是自动平衡的，意思是，它左子树的深度和右子树的深度差要么是 0,±1 。没有其他可能。这就是 AVL 树，这棵树长的比较对称，不会出现极端的一边倒的情况。这也就意味着 AVL 在创建过程中，根节点也会不断的变换。 AVL 树的目的就是为了解决搜索二叉搜索树的时候可能出现最坏复杂度的情况。 AVL 树极端情况下复杂度也就 log(n) 。

但是 AVL 树的建立有点复杂。网上查找了部分资料，维基百科的 AVL 定义是我主要的参考来源。具体定义可以自行查看。

在实现过程中，最让我头疼的是平衡因子的计算，资料中也没有说明具体的算法，或者说了也没看懂。网上搜索了一些资料，也是极尽坑爹，要么含糊不说，要么一笔带过。始终不知道如何计算。因此本人在程序中使用的是计算出左右子树的最大深度，做减法。由于计算左右子树是一个递归算法，也是相对有些复杂。因此算法的整体复杂度也随之增加。

为了降低程序的复杂度，对于 AVL 树节点的定义信息，也有所增加，比如增加了指向父节点的指针。当指明孩子的时候，自动的也确定父亲。代码如下：

1. public node leftchild

2. {

3. set

4. {

5. _leftchild = value ;

6. if (_leftchild != null )

7. {

8. _leftchild.father = this;// 确定父结点

9.

10. }

11. }

12. get

13. {

14. return _leftchild;

15. }

16. }

17. public node rightchild

18. {

19. set

20. {

21. _rightchild = value ;

22. if (_rightchild != null )

23. {

24. _rightchild.father = this;// 确定父结点

25.

26. }

27. }

28. get

29. {

30. return _rightchild;

31. }

32. }

33.

其中 balance 是平衡因子。实现方式如下：

1. public int balance

2. {

3. get

4. {

5. return maxDepth( this .leftchild) - maxDepth( this .rightchild);

6. }

7. }

AVL 树构建中的关键步骤叫做转换。分成 4 种情况的转换。具体的内容可以参考维基百科。本人参照维基百科的图例写出 4 个转换方式。这四种分别是 LR ， LL ， RL ， RR 。

此处简述一下 LR 转换。首先要匹配哪个结点是哪个结点。要找准了，不然就容易出错。 LR 中，结点 4 转到结点 5 和 3 中间，并且结点 B 成为结点 3 右孩子了。其中 LR 到 LL 的时候结点 5 依然是根结点，没变。那么程序就如下写法，其中 root 是根结点参数，但此处的转换不需要有根结点参与。程序的写法尽量照图，把要转动的点作为 leaf 结点传进来。即 node3 就是 leaf ，然后依次匹配好哪个是 node4 ，哪个是 node5, 哪个是 B ，全都匹配好之后，把图上的动作翻译成代码。此处需要对链表操作有一定的基础。懂的自然懂。当 LR 经过图上的转换后，变成 LL 型了，那么直接调用 LL 的转换方式就可以了。

1. static void LL_To_Balanced( ref node root , node leaf )

2. {

3.

4. node node4 = leaf;

5. node node3 = node4.leftchild;

6. node node5 = node4.father;

7. node C = node4.rightchild;

8. // 以上代码根据图把结点给找准了，下面就开始动作了。

9.

10. if (node5.father != null)// 此处涉及到node4变成根结点了。那么如果node5的father存在的话，要指向node4的。

11. {

12. if (node5.isleftchild)

13. node5.father.leftchild = node4;

14. else if (node5.isrightchild)

15. node5.father.rightchild = node4;

16. }

17. else

18. {

19. root = node4;// 如果node5是整棵树的根结点，那么现在就变成node4了

20. node4.father = null;

21. }

22. node4.rightchild = node5;

23. node5.leftchild = C;

24. }

再看 LL 型的转换，首先，同样的找准结点，匹配好哪个是结点 4 ，哪个是结点 5 ，哪个是结点 3 ，那个结点 C ，因为 LL 的转换也就只涉及到结点 3,4,5,C 这几个结点。代码中，把结点 4 当做 leaf ，因此传值的时候要传对了。由于 LL 转换涉及到树的根结点的变换，根据图中的示例，假设 node5 有个 father ，那么这个 father 现在是把 node4 作为孩子了。至于是左孩子还是右孩子，就看 node5 是左孩子还是右孩子。假设 node5 没有 father ，也就是说 node5 是根节点，那么 node4 就成为根结点了。

1. static void LL_To_Balanced( ref node root , node leaf )

2. {

3.

4. node node4 = leaf;

5. node node3 = node4.leftchild;

6. node node5 = node4.father;

7. node C = node4.rightchild;

8. // 以上代码根据图把结点给找准了，下面就开始动作了。

9.

10. if (node5.father != null)// 此处涉及到node4变成根结点了。那么如果node5的father存在的话，要指向node4的。

11. {

12. if (node5.isleftchild)

13. node5.father.leftchild = node4;

14. else if (node5.isrightchild)

15. node5.father.rightchild = node4;

16. }

17. else

18. {

19. root = node4;// 如果node5是整棵树的根结点，那么现在就变成node4了

20. node4.father = null;

21. }

22. node4.rightchild = node5;

23. node5.leftchild = C;

24. }

RL 和 RR 的转换也是如上面所述的算法。关键要匹配好那些结点。

本人之前写过二叉搜索树的插入，可以参考前面的文章。 AVL 的建立和二叉搜索树是类似的，根据结点的大小插入位子。但是多了一步，就是网站监控要做转型，也就是上面说的 4 种转换方式。

那么代码可以先借用构建二叉搜索树的代码了。插完结点后，调用转型方法不就 OK 了嘛。如下的方法，就是生成了普通的二叉搜索树。然后在对其转换。

1. // 此处算法就是插入二叉搜索树

2. static void InsertIntoAVL( node root, node leaf)

3. {

4. if (root == null)

5. {

6. root = leaf;

7. return ;

8. }

9. if (root.nodevalue == leaf.nodevalue)

10. {

11. return ;

12. }

13. else if (root.nodevalue > leaf.nodevalue)

14. {

15. if (root.hasleftchild == false)

16. {

17. root.leftchild = leaf;

18. }

19. else

20. {

21. InsertIntoAVL(root.leftchild, leaf);

22. }

23. }

24. else if (root.nodevalue < leaf.nodevalue)

25. {

26. if (root.hasrightchild == false)

27. {

28. root.rightchild = leaf;

29. }

30. else

31. {

32. InsertIntoAVL(root.rightchild, leaf);

33. }

34. }

35. }

以上通过代码插入结点，算法同二叉搜索树的结点插入，接下来确定转换问题。转换的时候，要确定，对谁转换，哪种类型的转换。

先第一个问题，对谁转换。那当然是插入了哪个结点，这个结点有可能打破了平衡，因此转换肯定和该节点有关。在我的代码中，以新插入的结点作为参照，依次找它的父节点。（此处就知道为什么要做 node 的定义中增加 father 属性了），一旦找到某个父节点的平衡因子是 ±2 ，可以开始处理第二个问题了。此处再强调的是，平衡因子的算法是左 - 右，因此如果是 +2 ，那么就是说明左边更深，反之亦反。

第二个问题，哪种类型的转换，维基百科上也有现成的说法，拿来照搬就行。简单的说就是如果一个结点的平衡因子是 ±2 了，那么就看它的孩子的平衡因子，是 ±1 ，不同的值代表了不同的类型。具体的逻辑，可以看我的代码反推。此处要注意的是，传进去的 leaf 结点，我都是把平衡因子是 ±2 的子结点作为 leaf 结点的。当然你也可以直接就用平衡因子是 ±2 结点作为参数传递。

代码实现如下，此方法的参数 root 就是表示这颗 AVL 树的根结点，因为很有可能在构建这棵树的时候根结点会变化，所以要时刻记录下，打印树的时候可以从根结点开始。 leaf 参数就是之前你新插入的结点，根据这个 leaf 为基准找 father ，你可以根据代码反推一些逻辑：

1. // 做旋转

2. static void Revolve(ref node root, node leaf)

3. {

4. Console.ForegroundColor = ConsoleColor.Yellow;

5. if (root == null )// 如果一棵树是空树，即没有根结点的情况下，插入一个叶子，那么根结点就是这样叶子，也不需要做旋转了。

6. {

7. root = leaf;

8. Console.ForegroundColor = ConsoleColor.Gray;

9. return;

10. }

11. node itsfather = leaf.father;

12. while (itsfather != null )

13. {

14. if (itsfather.balance == 2 )//LR 或者LL

15. {

16. if (itsfather.leftchild.balance == 1 )

17. {

18. Console.WriteLine( "LL" );

19. LL_To_Balanced(ref root, itsfather.leftchild);

20. }

21. else if (itsfather.leftchild.balance == - 1 )

22. {

23. Console.WriteLine( "LR" );

24. LR_To_Balanced(ref root, itsfather.leftchild);

25.

26. }

27. Console.ForegroundColor = ConsoleColor.Gray;

28. return;

29. }

30. else if (itsfather.balance == - 2 )

31. {

32. if (itsfather.rightchild.balance == - 1 )

33. {

34. Console.WriteLine( "RR" );

35. RR_To_Balanced(ref root, itsfather.rightchild);

36. }

37. else if (itsfather.rightchild.balance == 1 )

38. {

39. RL_To_Balanced(ref root, itsfather.rightchild);

40. Console.WriteLine( "RL" );

41. }

42. Console.ForegroundColor = ConsoleColor.Gray;

43. return;

44. }

45. itsfather = itsfather.father;

46. }

47.

48. Console.WriteLine( "no need to revolve" );

49. Console.ForegroundColor = ConsoleColor.Gray;

50. }

最后，就是调用插入结点的方法。为了让结果直观，本人写了个插入方法，主要打印树的结构。可自行反推逻辑。

1. // 插入结点，打印一些信息

2. private static node InsertNode ( ref node root , node thenode )

3. {

4. InsertIntoAVL(root, thenode);

5. Console.WriteLine( " 插入了" + thenode.nodevalue);

6. printtree(root);

7. Console.WriteLine( " 开始对其旋转" );

8. Revolve( ref root, thenode);

9. Console.ForegroundColor = ConsoleColor.Green;

10. Console.WriteLine( " 旋转后的结构如下" );

11. Console.ForegroundColor = ConsoleColor.Gray;

12. printtree(root);

13. Console.WriteLine( "******END*******" );

14. return root;

15. }

Main 方法中，调用就如下：

1. node node_1 = new node (1 );

2. node node_2 = new node (2 );

3. node node_3 = new node (3 );

4. node node_4 = new node (4 );

5. node node_5 = new node (5 );

6. node node_6 = new node (6 );

7. node node_7 = new node (7 );

8. node node_8 = new node (8 );

9. node node_9 = new node (9 );

10. node node_10 = new node (10 );

11. node node_11 = new node (11 );

12. node node_12 = new node (12 );

13. node node_13 = new node (13 );

14. node node_14 = new node (14 );

15. node node_15 = new node (15 );

16. node node_16 = new node (16 );

17. node node_17 = new node (17 );

18. node node_18 = new node (18 );

19. node node_19 = new node (19 );

20. node node_20 = new node (20 );

21. node node_21 = new node (21 );

22. node node_22 = new node (22 );

23.

24.

25. node root = null;

26. InsertNode( ref root, node_10);

27. InsertNode( ref root, node_8);

28. InsertNode( ref root, node_5);

29. InsertNode( ref root, node_12);

30. InsertNode( ref root, node_17);

31. InsertNode( ref root, node_9);

32. InsertNode( ref root, node_1);

33. InsertNode( ref root, node_4);

34.

结果如下：

具体代码，看附件。

后记：

AVL 树的构建，看起来简单，但是真的写起代码来还是很麻烦。思路清晰是关键。还有很多要改进的地方，比如，平衡因子的计算，本人算法实在不算高明。还有优化的余地，比如回溯法。

ITPub博客

自动平衡二叉树的构建-AVL树

最新文章