查找算法总结(4)--平衡二叉树

一、简介

二叉查找树在构建时，当数组是有序时，树的高度达到n，查找效率也为O(n)。平衡二叉树（AVL树）是二叉查找树的改进，不仅有二叉查找树的性质，而且每个节点的左右子树的高度相差不超过1。
平衡二叉树具有以下的性质：
1、是二叉查找树
2、每个节点的左右子树的高度差不超过1

平衡二叉树的查找和二叉查找树一样，找最大值、最小值、指定值、前驱和后继等。

平衡二叉树的插入不仅需要比较插入值和根节点的大小，在插入之后，由于会破坏平衡二叉树的性质，需要旋转来维护。
根据插入节点与最小不平衡子树的根节点（设为A）的位置关系，分为4种情况：
（最小不平衡子树是离插入节点最近，且以平衡因子绝对值大于1的节点为根的子树）
1、LL型：在A的左孩子(L)的左子树(L)上插入节点，使得A的左子树较高而失去平衡。LL型的调整规则为带着左子树向右旋转，选择A的左孩子（设为B）作为新的根节点，B的左子树不变（带着左子树），A作为B的右子树，而B原来的右子树作为A的左子树。
2、RR型：在A的右孩子(R)的右子树(R)上插入节点，使得A的右子树较高而失去平衡。RR的调整规则为带着右子树向左旋转，选择A的右孩子（设为B）作为新的根节点，B的右子树不变（带着右子树），A作为B的左子树。而B原来的左子树作为A的右子树。
3、LR型：在A的左孩子(L)的右子树(R)上插入节点，使得A的左子树较高而失去平衡。LR向的调整规则为先RR调整，再LL调整。首先对A的左子树进行RR型调整，然后再对以A为根节点的树进行LL型调整。
4、RL型：在A的右孩子(R)的左子树(L)上插入节点，使得A的右子树较高而失去平衡。RL型的调整规则为先LL型调整，在RR型调整。首先对A的右子树进行LL型调整，再对以A为根节点的树进行RR型调整。

二、代码实现

/*
 * 平衡二叉树的实现
 * 1、创建二叉平衡树
 * 2、二叉平衡树的操作，查找，最大值，最小值，插入
 * 3、判断一个树是不是二叉平衡树,是否空
 * 4、按顺序打印平衡二叉树
 * */

public class AvlTree<T extends Comparable<? super T>>{
private AvlNode<T> root;

//构造函数
public AvlTree(){
this.root=null;
    }
public AvlTree(T[] array){
for(T x:array){
            insert(x);
        }
    }

//在Avl树中查找数据，和查找二叉树一样
public boolean search(T value){
return search(root,value);
    }

public boolean search(AvlNode<T> node,T value){
while(node!=null){
int c=value.compareTo(node.element);
if(c<0) node=node.left;
else if (c>0) node=node.right;
else return true;
        }
return false;
    }

//在Avl树中找到最大值，和查找二叉树一样
public T findMax(){
if(root==null) System.out.println("数空");
return findMax(root).element;
    }

public AvlNode<T> findMax(AvlNode<T> node){
if(node==null) return node;
while(node.left!=null){
            node=node.left;
        }
return node;
    }

//在Avl树中找到最小值，和查找二叉树一样
public T findMin(){
if(root==null) System.out.println("数空");
return findMin(root).element;
    }

public AvlNode<T> findMin(AvlNode<T> node){
if(node==null) return node;
while(node.right!=null){
            node=node.right;
        }
return node;
    }


//在Avl树中插入数据，重复数据替换
public void insert(T value){
        root=insert(root,value);
    }

public AvlNode<T> insert(AvlNode<T> node,T value){
//如果树空，生成一个节点
if(node==null) return new AvlNode<T>(value,null,null);

int c=value.compareTo(node.element);

if(c<0){
//如果插入的值小于节点的值，插入左子树中
            node.left=insert(node.left,value);
if(hight(node.left)-hight(node.right)==2){//失去平衡
if(value.compareTo(node.left.element)<0){//LL型
                     node= rotateWithLeftChild(node);   
                }else node=doubleWithLeftChild(node);  //LR型
            }
        }
else if(c>0){
//如果插入的值大于节点的值，插入右子树中
            node.right=insert(node.right,value);
if(hight(node.left)-hight(node.right)==-2){
if(value.compareTo(node.right.element)>0){//RR
                    node=rotateWithRightChild(node);
                }else node=doubleWithRightChild(node); //RL
            }
        } 
//如果相等，替换
else if(c==0) node.element=value;


//更新节点高度
        node.height=Math.max(hight(node.left), hight(node.right))+1;
return node;
    }

//LL,带左子树旋转，向右旋转
private AvlNode< T> rotateWithLeftChild( AvlNode< T> node ) {
         AvlNode<T> reNode=node.left;
         node.left=reNode.right;
         reNode.right=node;
         node.height=Math.max(hight(node.left),hight(node.right))+1;
         reNode.height=Math.max(hight(reNode.left), hight(reNode.right))+1;
return reNode;
     }

//带右子树旋转，适用于RR型 ，向左旋转
private AvlNode< T> rotateWithRightChild( AvlNode< T> node ) {
         AvlNode<T> reNode=node.right;
         node.right=reNode.left;
         reNode.left=node;
         node.height=Math.max(hight(node.left), hight(node.right))+1;
         reNode.height=Math.max(hight(reNode.left), hight(reNode.right))+1;
return reNode;
     }

//双旋转，适用于LR型 
private AvlNode< T> doubleWithLeftChild( AvlNode< T> node ) {
         node.left = rotateWithRightChild( node.left );  
return rotateWithLeftChild( node );  
     } 

//双旋转,适用于RL型 
private AvlNode< T> doubleWithRightChild( AvlNode< T> node ) {
         node.right = rotateWithLeftChild( node.right );  
return rotateWithRightChild(node);  
     }

public int hight(AvlNode<T> node){
return node==null ? -1:node.height;
    }
//判断一个树是不是平衡二叉树
public boolean isTree(){
if(root==null) System.out.println("数空");
return isTree(root);
    }

public boolean isTree(AvlNode<T> node){
if(node==null) return true;
return(Math.abs(node.height)<=1 &&
                node.left==null || node.left!=null && node.left.element.compareTo(node.element)<0  
                && node.right==null || node.right!=null && node.right.element.compareTo(node.element)>0); 
    }

//判断一个二叉树是不是空
public boolean isEmpty(){
return root==null;
    }

//打印
public void printTree(){
if(root==null) System.out.println("数空");
else printTree(root);
    }

public void printTree(AvlNode<T> node){
if(node!=null){
            printTree(node.left);
            System.out.println(node.element);
            printTree(node.right);
        }
    }
}