AVL树旋转问题

Question

代码地址，包含代码和测试用例：https://github.com/rainzhao/datastruct/blob/master/src/main/java/example/tree/AVLTree.java

bobo老师您好，我在avl树的代码时发现如下问题：
测试用例如下：

AVLTree<Integer, String> avlTree = new AVLTree<>();
// 根节点
avlTree.add(20, "Y");
// 左子树
avlTree.add(18, "X");
avlTree.add(30, "X4");
avlTree.add(16, "Z");
avlTree.add(19, "X3");
avlTree.add(15, "X1");
avlTree.add(17, "X2");
// 右子树
avlTree.add(28, "Q3");
avlTree.add(34, "A");
avlTree.add(32, "Q1");
avlTree.add(36, "Q2");

期望结果如下：

			 18
*          /    \
*        16      30
*       /  \    /   \
*      15  17  20    34
*             /  \   /
*            19  28 32

但是实际调试时发现如下问题：

* 添加32节点前：
*          18
*        /    \
*       16     20
*      /  \   /  \
*     15  17 19  30
*               /  \
*              28  34

这时如果添加节点32，代码在20这个节点时满足了右旋转的条件，其实是应该左旋转而不是右旋转。最终导致程序不能输出最终期望的结果。

请您帮忙看下，代码我对了几遍和您的没有什么差别…,
发现只要把LL和RR的判断条件getBalanceFactor(node.right) > 0 和 getBalanceFactor(node.left)< 0 就没有问题。

Answer 1

liuyubobobo 2019-07-07 02:18:32

我用课程这一小节的代码，基于你的测试用例进行了详细的跟踪，没有你描述的问题的，可以正确进入RR的左旋转过程。所以我怀疑你的实现细节有问题。

从你的截图上，貌似你在第一个if判断，平衡因子前面加了一个绝对值？这个绝对值是不对的。平衡因子的正负是有意义的，不能抹去。表示偏斜的方向。

==========

可以在你的环境下，运行一下课程的官方代码，看看是否有问题？

传送门：https://github.com/liuyubobobo/Play-with-Data-Structures

这一小节代码传送门：https://github.com/liuyubobobo/Play-with-Data-Structures/tree/master/12-AVL-Tree/06-LR-and-RL

如果在你的环境下，没有问题，可以仔细比对调试一下看，看看自己的代码哪里有问题。进步就发生在这个过程中哦：）

继续加油！：）

• 提问者 zhaoyu_0509 #1

  确实是绝对值的问题，这个时候如果加了绝对值，本来应该走到左旋转的缺走到了右旋转，囧 , 非常感谢老师！