树相关算法

二叉树的常见概念

1. 结点的度：节点所拥有的子树个数称为该节点的度。

2. 叶节点：度为0的节点称为叶子节点，或者终端节点（即是树的最下层）

3. 分枝节点：度部位0的结点称为分枝结点。一棵树的结点除叶结点以外，其余的都是分枝结点。

4. 左孩子、右孩子、双亲：树中一个结点的子树的根节点称为这个结点的孩子，这个结点称为孩子结点的双亲，具有同一个双亲的孩子结点互称为兄弟。

5. 祖先、子孙：在树种如果一条路径是从结点M到结点N，那么M就称为N的祖先。而N是M的子孙。

6. 结点的层数：规定树的根节点层数为1，其余结点的层数等于他的双亲结点的层数+1。

7. 树的深度：树中所有结点的最大层数称为树的深度。

8. 树的度。树中所有节点度的最大值称为树的度，叶子结点的度为0.

9. 满二叉树：在一棵树中，如果所有的分枝结点都存在左子树右子树，并且所有叶子结点都在用一层，这样的一棵二叉树称为满二叉树。

10. ​

    二叉树的基本性质

    1.性质一：一棵非空的二叉树第i层最多有2的i-1次方个结点(i>>1)

2.性质二：一棵深度为k的二叉树中，最多具有2的k次方然后-1个节点。

3.性质三：对于一个非空的二叉树。度为0的结点（即叶子结点）总是比度为2的结点多一个，即如果叶子结点为n_0,度为2的结点为n_2，则有n_0=n_2+1。

​ 性质三证明：用n表示二叉树的总结点树，n_0表示度为0的结点数，n_1表示度为1的结点数，n_2表示度为2的结点数。则有n=n_0+n_1+n_2,而根据二叉树的性质可知n=n1+2*n_2+1(所有结点的度数之和+1=总结点个数)，根据两个等式就可以得出n_0=n_2+1。

性质四：具有n个结点的完全二叉树的深度为log2n+1。

​ 性质四证明：根据性质2，深度为k的二叉树最多有2的k次方减1个结点，且完全二叉树的定义与通深度的满二叉树的前面编号相同，即他的总结点个数位于k层和k-1层的满二叉树容量之间，即2的k-1次方-1<<n<<2的k次方-1,三个同时取对数，于是又k-1<<log2n<<k，又因为k是整数，所以k=log2n+1。

性质5：如果根结点从1开始编号，左孩子编号2i,右孩子2i+1,如果从0开始编号，左孩子编号2i+1，右孩子2i+2。

二叉排序树（二叉查找树）[包含先序、后序、中序、层序]

二叉排序树或者是一个空树，或者是具有下列性质的二叉树：
（1） 如果左子树不空，那么左子树上所有结点的值均小于它的根节点的值。

（2）如果右子树不为空，那么右子树所有结点的值都均大于它的根节点的值。

（3）左右子树也分别为二叉排序树。

/**
 * Created by fangheart on 2017/3/6.
 */
public class Node {
    public int data;
    public Node left;
    public Node right;
    public  Node(int data){
        this.data = data;
        this.left = null;
        this.right = null;
    }
}


/**
 * Created by fangheart on 2017/3/6.
 */
public class BinaryTree {
    private Node root;
    public void BinartTree(){
        root = null;
    }

    public static void main(String[] args){
        BinaryTree binaryTree = new BinaryTree();
        int[] data = {2,8,7,4,9,3,1,6,7,5};
        binaryTree.buildTree(data);
        System.out.println("二叉树的先序遍历：");
        binaryTree.preOrder(binaryTree.root);
        System.out.println();
        System.out.println("二叉树的中序遍历：");
        binaryTree.inOrder(binaryTree.root);
        System.out.println();
        System.out.println("二叉树的后序遍历：");
        binaryTree.postOrder(binaryTree.root);
        System.out.println();
    }

    //将data插入到排序二叉树中
    public void insert(int data){
        Node newNode = new Node(data);

        if(root == null){
            root = newNode;
        }else {
            Node current = root;
            Node parent;
            while(true){//寻找插入位置
                parent = current;
                if (data < current.data){
                    current = current.left;
                if (current==null){
                    parent.left = newNode;
                    return;
                }
                }else {
                    current = current.right;
                    if (current==null){
                        parent.right = newNode;
                        return;
                    }
                }

            }
        }
    }

    //将数值插入构建二叉树
    public void buildTree(int[] data){
        for (int i = 0; i < data.length; i++) {
            insert(data[i]);
        }
    }

    //中序遍历输出
    public void inOrder(Node localRoot){
        if (localRoot != null){
            inOrder(localRoot.left);
            System.out.print(localRoot.data + " ");
            inOrder(localRoot.right);
        }
    }
    //中序遍历非递归版本
    public void inOrder2(Node localRoot){
        Stack<Node> stack = new Stack<Node>();
        while(localRoot!=null||!stack.isEmpty()){
            while (localRoot!=null){
                stack.push(localRoot);
                localRoot = localRoot.left;
            }
            localRoot = stack.pop();
            System.out.print(localRoot.data + " ");
            localRoot = localRoot.right;
        }
    }

    //先序遍历
    public void preOrder(Node localRoot){
        if(localRoot != null ){
            System.out.print(localRoot.data+" ");
            preOrder(localRoot.left);
            preOrder(localRoot.right);
        }
    }

    //先序遍历非递归版本
    public void preOrder2(Node localRoot){
        Stack<Node> stack = new Stack<Node>();
        while(localRoot!=null||!stack.isEmpty()){
            while (localRoot!=null){
                System.out.print(localRoot.data + " ");
                stack.push(localRoot);
                localRoot = localRoot.left;
            }
            localRoot = stack.pop();
            localRoot = localRoot.right;
        }
    }

    //后续遍历
    public void postOrder(Node localRoot){
        if(localRoot != null){
            postOrder(localRoot.left);
            postOrder(localRoot.right);
            System.out.print(localRoot.data + " ");
        }
    }
    //后序遍历非递归版本
    public void postOrder2(Node localRoot){
        Stack<Node> stack = new Stack<Node>();
        Stack<Node> outStack = new Stack<Node>();//后续是左右中 那我们就按中右左的方式先存入栈里
        while(localRoot!=null||!stack.isEmpty()){
            while (localRoot!=null){
                outStack.push(localRoot);
                stack.push(localRoot);
                localRoot = localRoot.right;
            }
            localRoot = stack.pop();
            localRoot = localRoot.left;
        }
        while(!outStack.isEmpty()){
            localRoot = outStack.pop();
            System.out.print(localRoot.data + " ");
        }
    }
	
	//层序遍历
	//层序遍历的主要思路是将根节点放入队列，然后每次都从队列中取出一个节点打印，
	//如这个节点有子节点，则将子节点放入队列，直到队列为空
    public void layerTranverse(){
        if(this.root==null)
            return;
        Queue<Node> q = new LinkedList<Node>();
        q.add(this.root);
        while(!q.isEmpty()){
            Node n = q.poll();
            System.out.print(n.data+" ");
            if (n.left!=null)
                q.add(n.left);
            if(n.right!=null)
                q.add(n.right);
        }
    }
}

已知先序遍历和中序遍历，求后序遍历

（已知中序和后序也可以求先序但已知先序和后序不能求中序，因为先序或者后序可以得知根节点，而中序用来区分左右子树）

/**
 * Created by FangHeart on 2017/3/6.
 */
public class Node {
    public int data;
    public Node left;
    public Node right;
    public Node(){
    }

    public Node(int data){
        this.data = data;
        this.left = null;
        this.right = null;
    }

}

/**
 * Created by FangHeart on 2017/3/6.
 */
public class BinaryTree {
    private Node root;
    public BinaryTree(){
        root = null;
    }

    public static void main(String[] args){
        BinaryTree binaryTree = new BinaryTree();
        int[] preOrder = {1,2,4,8,9,5,10,3,6,7};
        int[] inOrder = {8,4,9,2,10,5,1,6,3,7};
        binaryTree.initTree(preOrder,inOrder);
        System.out.print("二叉树的后序遍历：");
        binaryTree.postOrder(binaryTree.root);
    }

    //后序遍历方法递归实现
    public void postOrder(Node localRoot){
        if(localRoot != null){
            postOrder(localRoot.left);
            postOrder(localRoot.right);
            System.out.print(localRoot.data + " ");
        }
    }

    public void initTree(int[] preOrder,int[] inOrder){
        this.root = this.initTree(preOrder,0,preOrder.length-1,inOrder,0,inOrder.length-1);
    }

    public Node initTree(int[] preOrder,int start1,int end1,int[] inOrder,int start2,int end2){
        if(start1>end1 || start2>end2){
            return null;
        }
        int rootData = preOrder[start1];
        Node head = new Node(rootData);
        //找到根节点所在位置
        int rootIndex = findIndexInArray(inOrder,rootData,start2,end2);
        int offSet = rootIndex - start2 - 1;
        //构建左子树
        Node left = initTree(preOrder,start1+1,start1+1+offSet,inOrder,start2,start2+offSet);
        //构建右子树
        Node right = initTree(preOrder,start1+offSet+2,end1,inOrder,rootIndex+1,end2);

        head.left = left;
        head.right = right;
        return head;
    }

    private int findIndexInArray(int[] a, int rootData, int begin, int end) {
        for (int i = begin; i <= end; i++) {
            if(a[i]==rootData)
                return i;
        }
        return -1;
    }
}

如何求二叉树中节点的最大距离

节点的距离是指着两个节点之间边的个数，写一个程序求一棵二叉树中相距最远的两个节点之间的距离。
一般而言，对二叉树的操作通过递归方法比较容易。求最大距离的主要思想如下：
首先求左子树距根节点的最大距离，记录为leftMaxDistance；其次求右子树距根节点的最大距离，记录为rightMaxDistance。
那么二叉树中节点的最大距离maxDistance = leftMaxDistance + rightMaxDistance;

public class BinaryTree {
    private int maxLen = 0;
    private int max (int a, int b){
        return a > b ? a:b;
    }

    public void FindMaxDistance(Node root){
        if(root == null)
            return;
        if (root.left==null)
            root.leftMaxDistance = 0;
        if (root.right==null)
            root.rightMaxDistance = 0;
        if(root.left!=null)
            FindMaxDistance(root.left);
        if (root.right!=null)
            FindMaxDistance(root.right);

        //计算左子树中距离根节点最大距离
        if(root.left!=null)
            root.leftMaxDistance = max(root.left.leftMaxDistance,root.left.rightMaxDistance)+1;
        //计算右子树距离根节点最大的距离
        if(root.right!=null)
            root.rightMaxDistance = max(root.right.leftMaxDistance,root.right.rightMaxDistance);
        //获取二叉树所有节点的最大距离
        if(root.leftMaxDistance+root.rightMaxDistance>maxLen){
            maxLen = root.leftMaxDistance + root.rightMaxDistance;
        }
    }
}

平衡二叉树

平衡二叉树（Balanced Binary Tree）是二叉查找树的一个进化体，也是第一个引入平衡概念的二叉树。1962年，G.M. Adelson-Velsky 和 E.M. Landis发明了这棵树，所以它又叫AVL树。平衡二叉树要求对于每一个节点来说，它的左右子树的高度之差不能超过1，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

旋转

对于一个平衡的节点，由于任意节点最多有两个儿子，因此高度不平衡时，此节点的两颗子树的高度差2.容易看出，这种不平衡出现在下面四种情况：

1、6节点的左子树3节点高度比右子树7节点大2，左子树3节点的左子树1节点高度大于右子树4节点，这种情况成为左左。

2、6节点的左子树2节点高度比右子树7节点大2，左子树2节点的左子树1节点高度小于右子树4节点，这种情况成为左右。

3、2节点的左子树1节点高度比右子树5节点小2，右子树5节点的左子树3节点高度大于右子树6节点，这种情况成为右左。

4、2节点的左子树1节点高度比右子树4节点小2，右子树4节点的左子树3节点高度小于右子树6节点，这种情况成为右右。

从图2中可以可以看出，1和4两种情况是对称的，这两种情况的旋转算法是一致的，只需要经过一次旋转就可以达到目标，我们称之为单旋转。2和3两种情况也是对称的，这两种情况的旋转算法也是一致的，需要进行两次旋转，我们称之为双旋转。

###：单旋转

单旋转是针对于左左和右右这两种情况的解决方案，这两种情况是对称的，只要解决了左左这种情况，右右就很好办了。图3是左左情况的解决方案，节点k2不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且k1子树中，更深的一层的是k1的左子树X子树，所以属于左左情况。

为使树恢复平衡，我们把k2变成这棵树的根节点，因为k2大于k1，把k2置于k1的右子树上，而原本在k1右子树的Y大于k1，小于k2，就把Y置于k2的左子树上，这样既满足了二叉查找树的性质，又满足了平衡二叉树的性质。

这样的操作只需要一部分指针改变，结果我们得到另外一颗二叉查找树，它是一棵AVL树，因为X向上一移动了一层，Y还停留在原来的层面上，Z向下移动了一层。整棵树的新高度和之前没有在左子树上插入的高度相同，插入操作使得X高度长高了。因此，由于这颗子树高度没有变化，所以通往根节点的路径就不需要继续旋转了。

双旋转

对于左右和右左这两种情况，单旋转不能使它达到一个平衡状态，要经过两次旋转。双旋转是针对于这两种情况的解决方案，同样的，这样两种情况也是对称的，只要解决了左右这种情况，右左就很好办了。图4是左右情况的解决方案，节点k3不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且k1子树中，更深的一层的是k1的右子树k2子树，所以属于左右情况。

为使树恢复平衡，我们需要进行两步，第一步，把k1作为根，进行一次右右旋转，旋转之后就变成了左左情况，所以第二步再进行一次左左旋转，最后得到了一棵以k2为根的平衡二叉树树。

插入

插入的方法和二叉查找树基本一样，区别是，插入完成后需要从插入的节点开始维护一个到根节点的路径，每经过一个节点都要维持树的平衡。维持树的平衡要根据高度差的特点选择不同的旋转算法。

查找

和二叉查找树相比，查找方法没有变法，不过根据存储的特性，AVL树能维持在一个O(logN)的稳定的时间，而二叉查找树则相当不稳定。

删除

删除的方法也和二叉查找树的一致，区别是，删除完成后，需要从删除节点的父亲开始向上维护树的平衡一直到根节点。

效率

此数据结构插入、查找和删除的时间复杂度均为O(logN)，但是插入和删除需要额外的旋转算法需要的时间，有时旋转过多也会影响效率。

package com.utils;  
import java.util.Iterator;  
import java.util.NoSuchElementException;  
/** 
 * 平衡二叉树 
 * 定义:首先它是一种特殊的二叉排序树，其次它的左子树和右子树都是平衡二叉树， 
 * 且左子树和右子树的深度之差不超过1 
 * 平衡因子:可以定义为左子树的深度减去右子树的深度 
 *  
 * 平衡二叉树是对二叉排序树的优化，防止二叉排序树在最坏情况下平均查找时间为n， 
 * 二叉排序树在此时形如一个单链表 
 * 平衡二叉树查找元素的次数不超过树的深度，时间复杂度为logN 
 */  
public class AVLTree<E> {  
    /** 
     * 根节点 
     */  
    private Entry<E> root = null;  
      
    /** 
     * 树中元素个数 
     */  
    private int size = 0;  
      
    public AVLTree(){  
          
    }  
      
    public int size(){  
        return size;  
    }  
  
  
    /** 
     * @param p 最小旋转子树的根节点 
     * 向左旋转之后p移到p的左子树处，p的右子树B变为此最小子树根节点， 
     * B的左子树变为p的右子树 
     * 比如：     A(-2)                   B(1) 
     *              \        左旋转       /   \ 
     *             B(0)     ---->       A(0)   \        
     *             /   \                   \    \ 
     *           BL(0)  BR(0)              BL(0) BR(0)  
     *  旋转之后树的深度之差不超过1 
     */  
    private void rotateLeft(Entry<E> p) {  
        System.out.println("绕"+p.element+"左旋");  
        if(p!=null){  
            Entry<E> r = p.right;  
            p.right = r.left;   //把p右子树的左节点嫁接到p的右节点，如上图，把BL作为A的右子节点  
            if (r.left != null) //如果B的左节点BL不为空，把BL的父节点设为A  
                r.left.parent = p;  
            r.parent = p.parent;  //A的父节点设为B的父节点  
            if (p.parent == null)         //如果p是根节点  
                root = r;                 //r变为父节点，即B为父节点  
            else if (p.parent.left == p)  //如果p是左子节点  
                p.parent.left = r;        //p的父节点的左子树为r  
            else                          //如果p是右子节点  
                p.parent.right = r;       //p的父节点的右子树为r  
            r.left = p;                   //p变为r的左子树，即A为B的左子树  
            p.parent = r;                 //同时更改p的父节点为r，即A的父节点为B  
        }  
    }  
      
    /** 
     * @param p 最小旋转子树的根节点 
     * 向右旋转之后，p移到p的右子节点处，p的左子树B变为最小旋转子树的根节点 
     * B的右子节点变为p的左节点、 
     * 例如:       A(2)                     B(-1) 
     *            /         右旋转          /    \ 
     *          B(0)       ------>         /     A(0) 
     *         /   \                      /      / 
     *       BL(0) BR(0)                BL(0)  BR(0)  
     */  
    private void rotateRight(Entry<E> p){  
        System.out.println("绕"+p.element+"右旋");  
        if(p!=null){  
            Entry<E> l = p.left;    
            p.left = l.right;    //把B的右节点BR作为A的左节点  
            if (l.right != null)   //如果BR不为null，设置BR的父节点为A  
                l.right.parent = p;  
            l.parent = p.parent;  //A的父节点赋给B的父节点  
            if (p.parent == null)   //如果p是根节点  
                root = l;          //B为根节点  
            else if (p.parent.right == p) //如果A是其父节点的左子节点  
                p.parent.right = l;     //B为A的父节点的左子树  
            else                        //如果A是其父节点的右子节点  
                p.parent.left = l;      //B为A的父节点的右子树  
            l.right = p;                //A为B的右子树  
            p.parent = l;               //设置A的父节点为B  
        }  
    }  
  
      
    /** 
     * 平衡而二叉树的插入操作 
     * 基本原理为： 
     * 1.首先如同二叉排序树一般，找到其要插入的节点的位置，并把元素插入其中； 
     * 2.自下向上进行回溯，回溯做两个事情： 
     * (1)其一是修改祖先节点的平衡因子，当插入 一个节点时只有根节点到插入节点 
     * 的路径中的节点的平衡因子会被改变，而且改变的原则是当插入节点在某节点(称为A) 
     * 的左子树 中时，A的平衡因子(称为BF)为BF+1,当插入节点在A的右子树中时A的BF-1， 
     * 而判断插入节点在左子树中还是右子树中只要简单的比较它与A的大小 
     * (2)在改变祖先节点的平衡因子的同时，找到最近一个平衡因子大于2或小于-2的节点， 
     * 从这个节点开始调整最小不平衡树进行旋转调整，关于如何调整见下文。 
     * 由于调整后，最小不平衡子树的高度与插入节点前的高度相同，故不需继续要调整祖先节点。 
     * 这里还有一个特殊情况，如果调整BF时，发现某个节点的BF变为0了，则停止向上继续调整， 
     * 因为这表明此节点中高度小的子树增加了新节点，高度不变，那么祖先节点的BF自然不变。 
     *  
     *  
     */  
    public boolean add(E element){  
        Entry<E> t = root;  
        if(t == null){  
            root = new Entry<E>(element,null);  
            size = 1;  
            return true;  
        }  
        int cmp;  
        Entry<E> parent;  //保存t的父节点  
        Comparable<? super E> e = (Comparable<? super E>) element;  
        //从根节点向下搜索，找到插入位置  
        do {  
            parent = t;       
            cmp = e.compareTo(t.element);  
            if(cmp < 0){  
                t = t.left;  
            }else if(cmp > 0){  
                t = t.right;  
            }else{  
                return false;  
            }  
        } while (t!=null);  
          
        Entry<E> child = new Entry(element,parent);  
        if(cmp < 0){  
            parent.left = child;  
              
        }else{  
            parent.right = child;     
        }  
        //自下向上回溯，查找最近不平衡节点  
        while(parent!=null){  
            cmp = e.compareTo(parent.element);  
            if(cmp < 0){    //插入节点在parent的左子树中  
                parent.balance++;  
            }else{           //插入节点在parent的右子树中  
                parent.balance--;  
            }  
            if(parent.balance == 0){    //此节点的balance为0，不再向上调整BF值，且不需要旋转  
                break;  
            }  
            if(Math.abs(parent.balance) == 2){  //找到最小不平衡子树根节点  
                fixAfterInsertion(parent);  
                break;                  //不用继续向上回溯  
            }  
            parent = parent.parent;  
        }  
        size ++;  
        return true;  
    }  
      
    /** 
     * 调整的方法： 
     * 1.当最小不平衡子树的根(以下简称R)为2时，即左子树高于右子树： 
     * 如果R的左子树的根节点的BF为1时，做右旋； 
     * 如果R的左子树的根节点的BF为-1时，先左旋然后再右旋 
     *  
     * 2.R为-2时，即右子树高于左子树： 
     * 如果R的右子树的根节点的BF为1时，先右旋后左旋 
     * 如果R的右子树的根节点的BF为-1时，做左旋 
     *  
     * 至于调整之后，各节点的BF变化见代码 
     */  
    private void fixAfterInsertion(Entry<E> p){  
        if(p.balance == 2){  
            leftBalance(p);  
        }  
        if(p.balance == -2){  
            rightBalance(p);  
        }  
    }  
      
      
    /** 
     * 做左平衡处理 
     * 平衡因子的调整如图： 
     *         t                       rd 
     *       /   \                   /    \ 
     *      l    tr   左旋后右旋    l       t 
     *    /   \       ------->    /  \    /  \ 
     *  ll    rd                ll   rdl rdr  tr 
     *       /   \ 
     *     rdl  rdr 
     *      
     *   情况2(rd的BF为0) 
     *  
     *    
     *         t                       rd 
     *       /   \                   /    \ 
     *      l    tr   左旋后右旋    l       t 
     *    /   \       ------->    /  \       \ 
     *  ll    rd                ll   rdl     tr 
     *       /    
     *     rdl   
     *      
     *   情况1(rd的BF为1) 
     *   
     *    
     *         t                       rd 
     *       /   \                   /    \ 
     *      l    tr   左旋后右旋    l       t 
     *    /   \       ------->    /       /  \ 
     *  ll    rd                ll       rdr  tr 
     *           \ 
     *          rdr 
     *      
     *   情况3(rd的BF为-1) 
     *  
     *    
     *         t                         l 
     *       /       右旋处理          /    \ 
     *      l        ------>          ll     t 
     *    /   \                             / 
     *   ll   rd                           rd 
     *   情况4(L等高) 
     */  
    private boolean leftBalance(Entry<E> t){  
        boolean heightLower = true;  
        Entry<E> l = t.left;  
        switch (l.balance) {  
        case LH:            //左高，右旋调整,旋转后树的高度减小  
            t.balance = l.balance = EH;  
            rotateRight(t);  
            break;   
        case RH:            //右高，分情况调整                                            
            Entry<E> rd = l.right;  
            switch (rd.balance) {   //调整各个节点的BF  
            case LH:    //情况1  
                t.balance = RH;  
                l.balance = EH;  
                break;  
            case EH:    //情况2  
                t.balance = l.balance = EH;  
                break;  
            case RH:    //情况3  
                t.balance = EH;  
                l.balance = LH;  
                break;  
            }  
            rd.balance = EH;  
            rotateLeft(t.left);  
            rotateRight(t);  
            break;  
        case EH:      //特殊情况4,这种情况在添加时不可能出现，只在移除时可能出现，旋转之后整体树高不变  
            l.balance = RH;  
            t.balance = LH;  
            rotateRight(t);  
            heightLower = false;  
            break;  
        }  
        return heightLower;  
    }  
      
    /** 
     * 做右平衡处理 
     * 平衡因子的调整如图： 
     *           t                               ld 
     *        /     \                          /     \ 
     *      tl       r       先右旋再左旋     t       r 
     *             /   \     -------->      /   \    /  \ 
     *           ld    rr                 tl   ldl  ldr rr 
     *          /  \ 
     *       ldl  ldr 
     *       情况2(ld的BF为0) 
     *        
     *           t                               ld 
     *        /     \                          /     \ 
     *      tl       r       先右旋再左旋     t       r 
     *             /   \     -------->      /   \       \ 
     *           ld    rr                 tl   ldl      rr 
     *          /   
     *       ldl   
     *       情况1(ld的BF为1) 
     *        
     *           t                               ld 
     *        /     \                          /     \ 
     *      tl       r       先右旋再左旋     t       r 
     *             /   \     -------->      /        /  \ 
     *           ld    rr                 tl        ldr rr 
     *             \ 
     *             ldr 
     *       情况3(ld的BF为-1) 
     *        
     *           t                                  r 
     *             \          左旋                /   \ 
     *              r        ------->           t      rr      
     *            /   \                          \ 
     *           ld   rr                         ld 
     *        情况4(r的BF为0)    
     */  
    private boolean rightBalance(Entry<E> t){  
        boolean heightLower = true;  
        Entry<E> r = t.right;  
        switch (r.balance) {  
        case LH:            //左高，分情况调整  
            Entry<E> ld = r.left;  
            switch (ld.balance) {   //调整各个节点的BF  
            case LH:    //情况1  
                t.balance = EH;  
                r.balance = RH;  
                break;  
            case EH:    //情况2  
                t.balance = r.balance = EH;  
                break;  
            case RH:    //情况3  
                t.balance = LH;  
                r.balance = EH;  
                break;  
            }  
            ld.balance = EH;  
            rotateRight(t.right);  
            rotateLeft(t);  
            break;  
        case RH:            //右高，左旋调整  
            t.balance = r.balance = EH;  
            rotateLeft(t);  
            break;  
        case EH:       //特殊情况4  
            r.balance = LH;  
            t.balance = RH;  
            rotateLeft(t);  
            heightLower = false;  
            break;  
        }  
        return heightLower;  
    }  
      
    /** 
     * 查找指定元素，如果找到返回其Entry对象，否则返回null 
     */  
    private Entry<E> getEntry(Object element) {    
        Entry<E> tmp = root;    
        Comparable<? super E> e = (Comparable<? super E>) element;  
        int c;    
        while (tmp != null) {    
            c = e.compareTo(tmp.element);    
            if (c == 0) {    
                return tmp;    
            } else if (c < 0) {    
                tmp = tmp.left;    
            } else {    
                tmp = tmp.right;    
            }    
        }    
        return null;    
    }    
      
    /** 
     * 平衡二叉树的移除元素操作 
     *  
     */  
    public boolean remove(Object o){  
        Entry<E> e = getEntry(o);  
        if(e!=null){  
            deleteEntry(e);  
            return true;  
        }  
        return false;  
    }  
      
    private void deleteEntry(Entry<E> p){  
        size --;  
        //如果p左右子树都不为空，找到其直接后继，替换p，之后p指向s，删除p其实是删除s  
        //所有的删除左右子树不为空的节点都可以调整为删除左右子树有其一不为空，或都为空的情况。  
        if (p.left != null && p.right != null) {  
             Entry<E> s = successor(p);  
             p.element = s.element;  
             p = s;  
        }  
        Entry<E> replacement = (p.left != null ? p.left : p.right);  
  
        if (replacement != null) {      //如果其左右子树有其一不为空  
            replacement.parent = p.parent;  
            if (p.parent == null)   //如果p为root节点  
                root = replacement;  
            else if (p == p.parent.left)    //如果p是左孩子  
                p.parent.left  = replacement;     
            else                            //如果p是右孩子  
                p.parent.right = replacement;  
  
            p.left = p.right = p.parent = null;     //p的指针清空  
              
            //这里更改了replacement的父节点，所以可以直接从它开始向上回溯  
            fixAfterDeletion(replacement);    
  
        } else if (p.parent == null) { // 如果全树只有一个节点  
            root = null;  
        } else {  //左右子树都为空  
            fixAfterDeletion(p);    //这里从p开始回溯  
            if (p.parent != null) {  
                if (p == p.parent.left)  
                    p.parent.left = null;  
                else if (p == p.parent.right)  
                    p.parent.right = null;  
                p.parent = null;  
            }  
        }     
    }  
      
    /** 
     * 返回以中序遍历方式遍历树时，t的直接后继 
     */  
    static <E> Entry<E> successor(Entry<E> t) {  
        if (t == null)  
            return null;  
        else if (t.right != null) { //往右，然后向左直到尽头  
            Entry<E> p = t.right;  
            while (p.left != null)  
                p = p.left;  
            return p;  
        } else {        //right为空，如果t是p的左子树，则p为t的直接后继  
            Entry<E> p = t.parent;  
            Entry<E> ch = t;  
            while (p != null && ch == p.right) {    //如果t是p的右子树，则继续向上搜索其直接后继  
                ch = p;  
                p = p.parent;  
            }  
            return p;  
        }  
    }  
      
    /** 
     * 删除某节点p后的调整方法： 
     * 1.从p开始向上回溯，修改祖先的BF值，这里只要调整从p的父节点到根节点的BF值， 
     * 调整原则为，当p位于某祖先节点(简称A)的左子树中时，A的BF减1，当p位于A的 
     * 右子树中时A的BF加1。当某个祖先节点BF变为1或-1时停止回溯，这里与插入是相反的， 
     * 因为原本这个节点是平衡的，删除它的子树的某个节点并不会改变它的高度 
     *  
     * 2.检查每个节点的BF值，如果为2或-2需要进行旋转调整，调整方法如下文， 
     * 如果调整之后这个最小子树的高度降低了，那么必须继续从这个最小子树的根节点(假设为B)继续 
     * 向上回溯，这里和插入不一样，因为B的父节点的平衡性因为其子树B的高度的改变而发生了改变， 
     * 那么就可能需要调整，所以删除可能进行多次的调整。 
     *  
     */  
    private void fixAfterDeletion(Entry<E> p){  
        boolean heightLower = true;     //看最小子树调整后，它的高度是否发生变化，如果减小，继续回溯  
        Entry<E> t = p.parent;  
        Comparable<? super E> e = (Comparable<? super E>)p.element;  
        int cmp;  
        //自下向上回溯，查找不平衡的节点进行调整  
        while(t!=null && heightLower){  
            cmp = e.compareTo(t.element);  
            /** 
             * 删除的节点是右子树，等于的话，必然是删除的某个节点的左右子树不为空的情况 
             * 例如：     10 
             *          /    \ 
             *         5     15 
             *       /   \ 
             *      3    6  
             * 这里删除5，是把6的值赋给5，然后删除6，这里6是p，p的父节点的值也是6。 
             * 而这也是右子树的一种 
             */   
            if(cmp >= 0 ){     
                t.balance ++;  
            }else{  
                t.balance --;  
            }  
            if(Math.abs(t.balance) == 1){   //父节点经过调整平衡因子后，如果为1或-1，说明调整之前是0，停止回溯。  
                break;  
            }  
            Entry<E> r = t;  
            //这里的调整跟插入一样  
            if(t.balance == 2){  
                heightLower = leftBalance(r);  
            }else if(t.balance==-2){  
                heightLower = rightBalance(r);  
            }  
            t = t.parent;  
        }  
    }  
      
      
      
    private static final int LH = 1;    //左高  
    private static final int EH = 0;    //等高  
    private static final int RH = -1;   //右高  
      
    /** 
     * 树节点，为方便起见不写get，Set方法 
     */  
    static class Entry<E>{  
        E element;  
        Entry<E> parent;  
        Entry<E> left;  
        Entry<E> right;  
        int balance = EH;   //平衡因子，只能为1或0或-1  
          
        public Entry(E element,Entry<E> parent){  
            this.element = element;  
            this.parent = parent;  
        }  
          
        public Entry(){}  
  
        @Override  
        public String toString() {  
            return element+" BF="+balance;  
        }  
              
    }  
      
      
    //返回中序遍历此树的迭代器,返回的是一个有序列表  
    private class BinarySortIterator implements Iterator<E>{  
        Entry<E> next;  
        Entry<E> lastReturned;  
          
        public BinarySortIterator(){  
            Entry<E> s = root;  
            if(s !=null){  
                while(s.left != null){  //找到中序遍历的第一个元素  
                    s = s.left;  
                }  
            }  
            next = s;   //赋给next  
        }  
          
        @Override  
        public boolean hasNext() {  
            return next!=null;  
        }  
  
        @Override  
        public E next() {  
            Entry<E> e = next;  
            if (e == null)  
                throw new NoSuchElementException();  
            next = successor(e);  
            lastReturned = e;  
            return e.element;  
        }  
  
        @Override  
        public void remove() {  
            if (lastReturned == null)  
                throw new IllegalStateException();  
            // deleted entries are replaced by their successors  
            if (lastReturned.left != null && lastReturned.right != null)  
                next = lastReturned;  
            deleteEntry(lastReturned);  
            lastReturned = null;  
        }  
    }  
      
    public Iterator<E> itrator(){  
        return new BinarySortIterator();  
    }  
      
  
      
    private int treeHeight(Entry<E> p){  
        if(p == null){  
            return -1;  
        }  
        return 1 + Math.max(treeHeight(p.left), treeHeight(p.right));  
    }  
      
      
    //测试，你也可以任意测试  
    public static void main(String[] args) {  
        AVLTree<Integer> tree = new AVLTree<Integer>();  
        System.out.println("------添加------");  
        tree.add(50);  
        System.out.print(50+" ");  
        tree.add(66);  
        System.out.print(66+" ");  
        for(int i=0;i<10;i++){  
            int ran = (int)(Math.random() * 100);  
            System.out.print(ran+" ");  
            tree.add(ran);  
        }  
        System.out.println("------删除------");  
        tree.remove(50);  
        tree.remove(66);  
          
        System.out.println();  
        Iterator<Integer> it = tree.itrator();  
        while(it.hasNext()){  
            System.out.print(it.next()+" ");  
        }  
    }  
}

B-树

是一种多路搜索树（并不是二叉的）：
1.定义任意非叶子结点最多只有M个儿子；且M>2；
2.根结点的儿子数为[2, M]；
3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5.非叶子结点的关键字个数=指向儿子的指针个数-1；
6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8.所有叶子结点位于同一层；

如：（M=3）

B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点。

B-树的特性：

1.关键字集合分布在整颗树中；

2.任何一个关键字出现且只出现在一个结点中；

3.搜索有可能在非叶子结点结束；

4.其搜索性能等价于在关键字全集内做一次二分查找；

5.自动层次控制；

由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最底搜索性能为：

其中，M为设定的非叶子结点最多子树个数，N为关键字总数；

所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；

由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并；

B+树

B+树是B-树的变体，也是一种多路搜索树：

1.其定义基本与B-树同，除了：

2.非叶子结点的子树指针与关键字个数相同；

3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；

5.为所有叶子结点增加一个链指针；

6.所有关键字都在叶子结点出现；

如：（M=3）

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在

非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+的特性：

1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

2.不可能在非叶子结点命中；

3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

4.更适合文件索引系统；

B*树

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；

B 树定义了非叶子结点关键字个数至少为(2/3) M，即块的最低使用率为2/3（代替B+树的1/2）；
B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
B 树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；
所以，B树分配新结点的概率比B+树要低，空间使用率更高；

小结

B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；

B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；

所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；

B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；