AVL树的旋转操作详解(3)

/*
* RR：右右对应的情况(右单旋转)。
*
* 返回值：旋转后的根节点
*/
private AVLTreeNode<T> rightRightRotation(AVLTreeNode<T> k1) {
    AVLTreeNode<T> k2;

    k2= k1.right;
    k1.right= k2.left;
    k2.left= k1;

    k1.height= max( height(k1.left), height(k1.right)) + 1;
    k2.height= max( height(k2.right), k1.height) + 1;

   return k2;
}

　　4.3）LR的旋转

　　第一次旋转是围绕"k1"进行的"RR旋转"，第二次是围绕"k3"进行的"LL旋转"。

　　LR的旋转代码：

/*
* LR：左右对应的情况(左双旋转)。
*
* 返回值：旋转后的根节点
*/
private AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> k3) {
    k3.left= rightRightRotation(k3.left);

   return leftLeftRotation(k3);
} 

　　4.4）RL的旋转

　　第一次旋转是围绕"k3"进行的"LL旋转"，第二次是围绕"k1"进行的"RR旋转"。

　　RL的旋转代码：

/* * RL：右左对应的情况(右双旋转)。 * * 返回值：旋转后的根节点 */ private AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> k1) { k1.right = leftLeftRotation(k1.right); return rightRightRotation(k1); }

　 综上，最后的整体插入代码为：

/*
* 将结点插入到AVL树中，并返回根节点
*
* 参数说明：
*    tree AVL树的根结点
*    key 插入的结点的键值
* 返回值：
*    根节点
*/
private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key) {
   if (tree == null) {
       // 新建节点
        tree = new AVLTreeNode<T>(key, null, null);
       if (tree==null) {
            System.out.println("ERROR: create avltree node failed!");
           return null;
        }
    }else {
       int cmp = key.compareTo(tree.key);

          if (cmp < 0) {    // 应该将key插入到"tree的左子树"的情况
            tree.left = insert(tree.left, key);
           // 插入节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.left) - height(tree.right) == 2) {
               if (key.compareTo(tree.left.key) < 0)
                    tree= leftLeftRotation(tree);
               else
                    tree= leftRightRotation(tree);
            }
        }else if (cmp > 0) {    // 应该将key插入到"tree的右子树"的情况
            tree.right = insert(tree.right, key);
           // 插入节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.right) - height(tree.left) == 2) {
               if (key.compareTo(tree.right.key) > 0)
                    tree= rightRightRotation(tree);
               else
                    tree= rightLeftRotation(tree);
            }
        }else {    // cmp==0
            System.out.println("添加失败：不允许添加相同的节点！");
        }
    }

    tree.height= max( height(tree.left), height(tree.right)) + 1;

   return tree;
}

public void insert(T key) {
    mRoot= insert(mRoot, key);
}