AVL树中的一些疑惑

[Wonderchn]

老师您好，我对这里AVL树的LL和RR的判断产生了一些疑惑

// 向以node为根的二分搜索树中插入元素(key, value)，递归算法
// 返回插入新节点后二分搜索树的根
private Node add(Node node, K key, V value) {

    if (node == null) {
        size++;
        return new Node(key, value);
    }

    if (key.compareTo(node.key) < 0)
        node.left = add(node.left, key, value);
    else if (key.compareTo(node.key) > 0)
        node.right = add(node.right, key, value);
    else // key.compareTo(node.key) == 0
        node.value = value;

    //更新node值
    node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));

    //计算平衡因子
    int balanceFactor = getBalanceFactor(node);
    if (Math.abs(balanceFactor) > 1) {
        System.out.println("unbalanced :" + balanceFactor);
    }


    // 平衡维护
    //LL getBalanceFactor(node.left)>0 主要是为了证明avl树是插入进左侧的左侧
    if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
        return rightRotate(node);

    }
    //RR
    if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
        return leftRotate(node);
    }

    //LR 首先对子函数进行坐旋转
    //然后在对当前节点进行右旋转
    //getBalanceFactor(node.left) <0 证明当前节点的左子树下的节点，这个节点的左子树比右子树的高度低
    if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }


    //RL
    if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    return node;

}

我们拿这段代码举例

 // 平衡维护
    //LL getBalanceFactor(node.left)>0 主要是为了证明avl树是插入进左侧的左侧
    if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
        return rightRotate(node);

    }

如果执行到这段代码，证明我们当前节点的

balanceFactor是大于1的，根据逻辑我们需要判断当前节点的左右孩子节点，判断是否是LL还是RR...

getBalanceFactor(node.left) >= 0

在这里我比较疑惑的是，为什么这里的条件中需要包含判断=0的情况,举例：

假设我们有一个二叉平衡树：

	15

	/

10

添加元素5:

				15(2)         

				/

		10(1)			

		/

	5(0)			

我们从底部的5开始递归，递归至顶部的15的平衡因子为2

再看

balanceFactor > 1 && getBalanceFactor(node.left) >= 0)

我们需要进行树的调整，让树成为平衡二叉树，我们满足了balanceFactor > 1的条件，然后我们看第二个条件， getBalanceFactor(node.left) >= 0,这个逻辑也很简单，我们获取当前15节点的左孩子节点，判断它的平衡因子(左右子树节点的差)，如果>0，证明左子树比右子树高。但是=0是什么情况呢？我做了这个一个假设

			15(2)

			/

		10(0)

	/		\

5(0)			11(0)

需要这样的一颗树，我们才可能需要=0的情况

但我们不可能出现这种情况，我们添加元素是递归的，每次只添加一个节点，从底至上，判断平衡因子是否相符，如果遍历到不相符的进行右/左旋转的操作。返回的是平衡二叉树的根节点，到最后整棵树都是相符平衡二叉树的。

				15   ->          15		-> 		15    ->		10		

						/				/			/		\

					10				10			  5		           15

								/

							5

可以看到我们的元素经过这样的调整已经满足平衡二叉树的定义

插入11

				10

			/		\

		5			11

						\

							15

所以，这里的getBalanceFactor(node.left) >= 0要改成getBalanceFactor(node.left) > 0

可能大家说我小题大做，实属是今晚卡在这里思考了许久。