//先右后左旋转
private Node RLRotate(Node node){
//再进行右旋转
RRotate(node.RChild);
//再进行右旋
return LRotate(node);
}
插入操作
插入操作通过递归方式实现，在插入操作完成后需要对访问路径上的每个节点进行判断来确定是否要旋转。
public Node insert(Node node, int i){
//先将节点插入到树中
if(node == null)
return new Node(i, 1, node);
//插入的值与当前节点值进行比较来确定插入的位置
if(i < node.val){
node.LChild= insert(node.LChild, i);//判断是否进行调整
if(height(node.LChild) - height(node.RChild) == 2){
if(i < node.LChild.val)
//插入的节点在左孩子的左子树上，则需要进行右旋
node = RRotate(node);
else
//插入的节点在左孩子的右子树上，则需要先进行左旋后进行右旋
node = LRRotate(node);
}
}
else{
node.RChild= insert(node.RChild, i);
if(height(node.LChild) - height(node.RChild) == -2){
if(i > node.RChild.val)
node= LRotate(node);
else
node= RLRotate(node);
}
}
node.height= Math.max(height(node.LChild), height(node.RChild))+1;
return node;
}
//计算树的高度,主要解决空树高度的问题(空树的高度为0) private int height(Node node){ return node == null ? 0:node.height; }
判断一棵树是否是AVL树判断时通过后续遍历的方式来比较左右子树的高度差
static boolean isBalance(Node node,Depth d){
if(node == null){
d.height=0;
return true;
}
Depth right=new Depth();
Depth left= new Depth();
if(isBalance(node.LChild,left)&&isBalance(node.RChild, right)){
if(Math.abs(left.height - right.height)<2){//绝对值小于等于1
//如果是平衡树，才有必要算深度，然后看上级是不是平衡树
d.height=(left.height>right.height?left.height:right.height)+1;
System.out.println("left="+left.height+" right="+right.height+" height"+d.height+" value="+node.val);
return true;
}
}
System.out.println("left="+left.height+" right="+right.height+" height"+d.height+" value="+node.val);
return false;
}
static class Depth{
int height;
}
完整代码