重学数据结构（六、树和二叉树） (8)

(3) LR型：由千在A的左子树根结点的右子树上插入结点， A的平衡因子由1增至2,致使以A为根结点的子树失去平衡， 则需进行两次旋转操作。 第一次对B及其右子树进行逆时针旋转， C转上去成为B的根， 这时变成了LL型， 所以第二次进行LL型的顺时针旋转即可恢复平衡。 如果C原来有左子树， 则洞整C的左子树为B的右子树， 如图25所示。

图25：LR型调整操作示意图

LR型旋转前后A、 B、C三个结点平衡因子的变化分为3种情况， 图 26 所示为3种 LR型调整的实例。

图26：LR型调整示例

(4) RL 型：由千在 A 的右子树根结点的左子树上插入结点， A 的平衡因子由 -1 变为-2,致使以 A 为根结点的子树失去平衡， 则旋转方法和 LR 型相对称， 也需进行两次旋转， 先顺时针右旋， 再逆时针左旋， 如图 27 所示。

图27：RL型调整操作示意图

同 LR 型旋转类似， RL 型旋转前后 A 、 B 、 C 三个结点的平衡因子的变化也分为 3 种情况，图 28 所示为 3 种 RL 型调整的实例。

图28：RL型调整示例

上述 4 种情况中，(1) 和 (2) 对称，进行的是单旋转的操作；(3) 和 (4) 对称，进行的是双旋转的操作。

旋转操作的正确性容易由 “保持二叉排序树的特性：中序遍历所得关键字序列自小至大有序” 证明之。 同时， 无论哪一种情况， 在经过平衡旋转处理之后，以 B 或 C 为根的新子树为平衡二叉树，而且它们的深度和插入之前以 A为根的子树相同。

因此， 当平衡的二叉排序树因插入结点而失去平衡时， 仅需对最小不平衡子树进行平衡旋转处理即可。 因为经过旋转处理之后的子树深度和插入之前相同，因而不影响插入路径上所有祖先结点的平衡度。

5.1.3、AVL树的插入

在平衡的二叉排序树BBST上插入一个新的数据元素e的递归算法可描述如下。

在上面我们看到插入节点，如果破坏了AVL树的平衡，则需要进行旋转，即上面的四种情况：

LL
执行一次右旋转

RR
执行一次左旋转

LR
先左旋，后右旋

RL
先右旋后左旋

5.1.3、AVL树删除

前面已经看过二叉树的删除操作，AVL树的删除操作同样分为三种情况：

删除节点为叶子节点

删除节点有左子树或右子树

删除节点有左子树和右子树

只不过 AVL 树在删除节点后需要重新检查平衡性并修正，同时，删除操作与插入操作后的平衡修正区别在于，插入操作后只需要对插入栈中的弹出的第一个非平衡节点进行修正，而删除操作需要修正栈中的所有非平衡节点。

具体代码实现：

public class AVLBinaryTree { public int size; //节点 class Node{ public int val; public Node left,right; public int height; public Node(int val){ this.val=val; left=null; right=null; height=1; } } //添加一个节点 public Node add(Node node,int val){ if (node==null){ size++; return new Node(val); } if (node.val<val) node.right=add(node.right,val); if (node.val>val) node.left=add(node.left,val); //更新高度 node.height=Math.max(getHeight(node.left),getHeight(node.right))+1; //计算平衡因子 int balanceFactor=getBlalanceFactor(node); //维护平衡 //LL if (balanceFactor>1&&getBlalanceFactor(node.left)>=0){ return rightRotate(node); } //RR if (balanceFactor<-1&&getBlalanceFactor(node.right)<=0){ return leftRotate(node); } //LR if (balanceFactor>1&&getBlalanceFactor(node.left)<0){ node.left=leftRotate(node.left); return rightRotate(node); } //RL if (balanceFactor<-1&&getBlalanceFactor(node.right)>0){ node.right=rightRotate(node.right); return leftRotate(node); } return node; } /** * 对根节点x进行向左旋转操作，更新height后返回新的根节点y * @param x * @return */ public Node leftRotate(Node x){ Node y=x.right; Node T3=y.left; y.left=x; x.right=T3; //更新height x.height=Math.max(getHeight(x.left),getHeight(x.right))+1; y.height=Math.max(getHeight(y.left),getHeight(y.right))+1; return y; } /** * 对根节点进行右旋转操作，更新height后返回新的根节点y * @param x * @return */ public Node rightRotate(Node x){ Node y=x.left; Node T3=y.right; y.right=x; x.left=T3; //更新height x.height=Math.max(getHeight(x.left),getHeight(x.right))+1; y.height=Math.max(getHeight(y.left),getHeight(y.right))+1; return y; } //获得节点Node的高度 public int getHeight(Node node){ if (node==null){ return 0; } return node.height; } //获取节点的平衡因子 private int getBlalanceFactor(Node node){ if (node==null){ return 0; } return getHeight(node.left)-getHeight(node.right); } /** * 删除节点 * @param node * @param val * @return */ public Node remove(Node node,int val){ if (node==null) return null; Node retNode; //递归查找要删除的节点 if (node.val<val){ node.left=remove(node.left,val); retNode=node; }else if(node.val>val){ node.right=remove(node.right,val); retNode=node; }else{ //找到了要删除的节点 //情形1：被删除节点为叶子节点 if (node.right==null){ Node leftNode=node.left; node.left=null; size--; retNode=leftNode; } //情形2.1:被删除节点只有右孩子 if (node.left==null){ Node leftNode=node.left; node.left=null; size--; retNode=leftNode; } //情形2.2：被删除节点只有左孩子 if (node.right==null){ Node rightNode=node.right; node.right=null; size--; retNode=rightNode; }else{ //情形3:被删除节点有左、右孩子 Node minNode=minimum(node); minNode.right=remove(node.right,minNode.val); node.left=node.right=null; retNode=minNode; } } if (retNode==null) return retNode; //删除完成，开始进行二叉树的平衡 //更新高度 retNode.height= Math.max(getHeight(retNode.left),getHeight(retNode.right)+1); //计算平衡因子 int balanceFactor=getBlalanceFactor(retNode); //维护平衡 //维护平衡 //LL if (balanceFactor>1&&getBlalanceFactor(retNode.left)>=0){ return rightRotate(retNode); } //RR if (balanceFactor<-1&&getBlalanceFactor(retNode.right)<=0){ return leftRotate(retNode); } //LR if (balanceFactor>1&&getBlalanceFactor(retNode.left)<0){ retNode.left=leftRotate(retNode.left); return rightRotate(retNode); } //RL if (balanceFactor<-1&&getBlalanceFactor(retNode.right)>0){ retNode.right=rightRotate(retNode.right); return leftRotate(retNode); } return retNode; } //获取该节点的整个子树的最小值 public Node minimum(Node node){ if (node.left==null){ return node; } return minimum(node.left); } }
5.2、红黑树