關(guān)于平衡因子的大小

• 葉子節(jié)點(diǎn)的平衡因子 == 0，但平衡因子為0的節(jié)點(diǎn)不一定是葉子節(jié)點(diǎn)，也可能是左右子樹高度相等的節(jié)點(diǎn)；
• 平衡因子 > 0，左子樹的高度 > 右子樹的高度；
• 平衡因子 < 0，左子樹的高度 < 右子樹的高度；

右旋轉(zhuǎn)

• LL(Left's Left)：新插入節(jié)點(diǎn)在不平衡節(jié)點(diǎn)（Y）左孩子的左側(cè)；
• 此時(shí)不平衡節(jié)點(diǎn)（Y）做右旋轉(zhuǎn)；
• 右旋轉(zhuǎn)代碼：

// 這棵樹原來就只有 x，y；z 是新添加的元素，在左孩子的左側(cè)；
// 對節(jié)點(diǎn)y進(jìn)行向右旋轉(zhuǎn)操作，返回旋轉(zhuǎn)后新的根節(jié)點(diǎn)x
//        y                              x
//       / \                           /   \
//      x   T4     向右旋轉(zhuǎn) (y)        z     y
//     / \       - - - - - - - ->    / \   / \
//    z   T3                       T1  T2 T3 T4
//   / \
// T1   T2
private Node rightRotate(Node y) {
    Node x = y.left;
    Node T3 = x.right;

    // 向右旋轉(zhuǎn)過程
    x.right = y;
    y.left = T3;

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

    return x;
}

左旋轉(zhuǎn)

• RR(Right's Right)：新插入節(jié)點(diǎn)在不平衡節(jié)點(diǎn)（Y）右孩子的右側(cè)；
• 此時(shí)不平衡節(jié)點(diǎn)（Y）做左旋轉(zhuǎn)；
• 左旋轉(zhuǎn)代碼：

// 對節(jié)點(diǎn)y進(jìn)行向左旋轉(zhuǎn)操作，返回旋轉(zhuǎn)后新的根節(jié)點(diǎn)x
//    y                             x
//  /  \                          /   \
// T1   x      向左旋轉(zhuǎn) (y)       y     z
//     / \   - - - - - - - ->   / \   / \
//   T2  z                     T1 T2 T3 T4
//      / \
//     T3 T4
private Node leftRotate(Node y) {
    Node x = y.right;
    Node T2 = x.left;

    // 向左旋轉(zhuǎn)過程
    x.left = y;
    y.right = T2;

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

    return x;
}

旋轉(zhuǎn)代碼在添加代碼中的位置

• 左孩子的左側(cè)：
  • balanceFactor > 1 && getBalanceFactor(node.left) >= 0
• 右孩子的右側(cè)：
  • balanceFactor < -1 && getBalanceFactor(node.right) <= 0
• 在旋轉(zhuǎn)完之后，原本遞歸結(jié)束返回給上一層的節(jié)點(diǎn)是Y，現(xiàn)在是X，降了一層；

// 向二分搜索樹中添加新的元素(key, value)
public void add(K key, V value){
    root = add(root, key, value);
}

// 向以node為根的二分搜索樹中插入元素(key, value)，遞歸算法
// 返回插入新節(jié)點(diǎn)后二分搜索樹的根
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;

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

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

    // 平衡維護(hù)
    if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
        return rightRotate(node);

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

    return node;
}