平衡二叉树的插入与实现
平衡二叉树的定义
在谈平衡二叉树之前，首先了解一下二叉排序树。空树或者具有以下特性的二叉树就是二叉排序树：
若左子树非空，则左子树上所有结点关键字的值均小于根节点的关键字的值。
若右子树非空，则右子树上所有结点关键字的值均大于根节点的关键字的值。
-
左右子树本身也分别是一棵二叉排序树。
平衡二叉树的插入
-
LL平衡旋转(右单旋转)：在结点A的左孩子的左子树上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转。将A的左孩子B向右上旋转代替A成为根节点，将A结点向右下旋转称为B的右子树的根节点，而B的原右子树作为A结点的左子树。如下图所示，结点旁的数字表示平衡因子，方块是对应子树，H表示子树高度。
-
RR平衡旋转(左单旋转)：在结点A的右孩子的右子树上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向右的旋转。将A的右孩子B向左上旋转代替A称为根节点，将A结点向左下旋转称为B的左子树的根结点，而B的原左子树则作为A结点的右子树。
-
LR平衡旋转(先左后右双旋转)：在结点A的左孩子的右子树上掺入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先向左旋转后向右旋转。先将A结点的左孩子B的右子树的根节点C向左上旋转提升到B结点的位置，然后再把C结点向右上旋转提升到A结点。
-
RL平衡旋转(先右后左双旋转)：在结点A的右孩子的左子树上插入新结点，A的平衡因子由-1减至-2，导致以A为跟的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A结点的右孩子B的左子树的根节点C向右上旋转提升至B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置。
public class Node {
public Node parent ; // 指向父节点
public Node left ; // 指向左子树
public Node right ; // 指向右子树
public int data ; // 节点数据
public int depth ; // 节点深度
public int balance ; // 是否平衡
public Node( int data){
this. data=data ;
depth= 1 ;
balance= 0 ;
left= null;
right= null;
parent= null;
}
}
public int calcBalance(Node p) {
int left_depth ;
int right_depth ;
// 左子树的深度
if(p. left != null){
left_depth = p. left. depth ;
} else{
left_depth = 0 ;
}
// 右子树的深度
if(p. right != null){
right_depth = p. right. depth ;
} else{
right_depth = 0 ;
}
return left_depth-right_depth ;
}
public int calcDepth(Node p) {
int depth = 0 ;
if(p. left != null){
depth = p. left. depth ;
}
if(p. right != null && depth < p. right. depth){
depth = p. right. depth ;
}
depth++ ;
return depth ;
}
public void right_rotate(Node p) {
Node pParent = p. parent ;
Node pLeftSon = p. left ;
Node pRightGrandSon = pLeftSon. right ;
pLeftSon. parent = pParent ;
if(pParent != null){
if(p == pParent. left){
pParent. left = pLeftSon ;
} else if(p == pParent. right){
pParent. right = pLeftSon ;
}
}
pLeftSon. right = p ;
p. parent = pLeftSon ;
p. left = pRightGrandSon ;
if(pRightGrandSon != null){
pRightGrandSon. parent = p ;
}
p. depth = calcDepth(p) ;
p. balance = calcBalance(p) ;
pLeftSon. depth = calcDepth(pLeftSon) ;
pLeftSon. balance = calcBalance(pLeftSon) ;
}
public void left_rotate(Node p) {
Node pParent = p. parent ;
Node pRightSon = p. right ;
Node pLeftGrandSon = pRightSon. left ;
pRightSon. parent = pParent ;
if(pParent != null){
if(p == pParent. right){
pParent. right = pRightSon ;
} else if(p == pParent. left){
pParent. left = pRightSon ;
}
}
pRightSon. left = p ;
p. parent = pRightSon ;
p. right = pLeftGrandSon ;
if(pLeftGrandSon != null){
pLeftGrandSon. parent = p ;
}
p. depth = calcDepth(p) ;
p. balance = calcBalance(p) ;
pRightSon. depth = calcDepth(pRightSon) ;
pRightSon. balance = calcBalance(pRightSon) ;
}
public void insert(Node root , int data){
// 数据小于根结点，左递归插入
if(data < root. data){
if(root. left != null){
insert(root. left , data) ;
} else{
root. left = new Node(data) ;
root. left. parent=root ;
}
} else{ // 数据大于根结点，右递归插入
if(root. right != null){
insert(root. right , data) ;
} else{
root. right = new Node(data) ;
root. right. parent = root ;
}
}
// 插入之后计算平衡因子
root. balance = calcBalance(root) ;
// 左子树高则右旋
if(root. balance >= 2){
// 右孙高先左旋
if(root. left. balance == - 1){
left_rotate(root. left) ;
}
right_rotate(root) ;
}
// 右子树高则左旋
if(root. balance <= - 2){
// 左孙高则先右旋
if(root. right. balance == 1){
right_rotate(root. right) ;
}
left_rotate(root) ;
}
// 调整之后重新计算平衡因子和树的高度
root. balance = calcBalance(root) ;
root. depth = calcDepth(root) ;
}