package com.utils;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
 * 平衡二叉樹
 * 定義:首先它是一種特殊的二叉排序樹，其次它的左子樹和右子樹都是平衡二叉樹，
 * 且左子樹和右子樹的深度之差不超過(guò)1
 * 平衡因子:可以定義為左子樹的深度減去右子樹的深度
 * 
 * 平衡二叉樹是對(duì)二叉排序樹的優(yōu)化，防止二叉排序樹在最壞情況下平均查找時(shí)間為n，
 * 二叉排序樹在此時(shí)形如一個(gè)單鏈表
 * 平衡二叉樹查找元素的次數(shù)不超過(guò)樹的深度，時(shí)間復(fù)雜度為logN
 */
public class AVLTree<E> {
    /**
     * 根節(jié)點(diǎn)
     */
    private Entry<E> root = null;
    
    /**
     * 樹中元素個(gè)數(shù)
     */
    private int size = 0;
    
    public AVLTree(){
        
    }
    
    public int size(){
        return size;
    }


    /**
     * @param p 最小旋轉(zhuǎn)子樹的根節(jié)點(diǎn)
     * 向左旋轉(zhuǎn)之后p移到p的左子樹處，p的右子樹B變?yōu)榇俗钚∽訕涓?jié)點(diǎn)，
     * B的左子樹變?yōu)閜的右子樹
     * 比如：     A(-2)                   B(1)
     *              \        左旋轉(zhuǎn)       /   \
     *             B(0)     ---->       A(0)   \       
     *             /   \                   \    \
     *           BL(0)  BR(0)              BL(0) BR(0) 
     *  旋轉(zhuǎn)之后樹的深度之差不超過(guò)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右子樹的左節(jié)點(diǎn)嫁接到p的右節(jié)點(diǎn)，如上圖，把BL作為A的右子節(jié)點(diǎn)
            if (r.left != null) //如果B的左節(jié)點(diǎn)BL不為空，把BL的父節(jié)點(diǎn)設(shè)為A
                r.left.parent = p;
            r.parent = p.parent;  //A的父節(jié)點(diǎn)設(shè)為B的父節(jié)點(diǎn)
            if (p.parent == null)         //如果p是根節(jié)點(diǎn)
                root = r;                 //r變?yōu)楦腹?jié)點(diǎn)，即B為父節(jié)點(diǎn)
            else if (p.parent.left == p)  //如果p是左子節(jié)點(diǎn)
                p.parent.left = r;        //p的父節(jié)點(diǎn)的左子樹為r
            else                          //如果p是右子節(jié)點(diǎn)
                p.parent.right = r;       //p的父節(jié)點(diǎn)的右子樹為r
            r.left = p;                   //p變?yōu)閞的左子樹，即A為B的左子樹
            p.parent = r;                 //同時(shí)更改p的父節(jié)點(diǎn)為r，即A的父節(jié)點(diǎn)為B
        }
    }
    
    /**
     * @param p 最小旋轉(zhuǎn)子樹的根節(jié)點(diǎn)
     * 向右旋轉(zhuǎn)之后，p移到p的右子節(jié)點(diǎn)處，p的左子樹B變?yōu)樽钚⌒D(zhuǎn)子樹的根節(jié)點(diǎn)
     * B的右子節(jié)點(diǎn)變?yōu)閜的左節(jié)點(diǎn)、
     * 例如:       A(2)                     B(-1)
     *            /         右旋轉(zhuǎn)          /    \
     *          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的右節(jié)點(diǎn)BR作為A的左節(jié)點(diǎn)
            if (l.right != null)   //如果BR不為null，設(shè)置BR的父節(jié)點(diǎn)為A
                l.right.parent = p;
            l.parent = p.parent;  //A的父節(jié)點(diǎn)賦給B的父節(jié)點(diǎn)
            if (p.parent == null)   //如果p是根節(jié)點(diǎn)
                root = l;          //B為根節(jié)點(diǎn)
            else if (p.parent.right == p) //如果A是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)
                p.parent.right = l;     //B為A的父節(jié)點(diǎn)的左子樹
            else                        //如果A是其父節(jié)點(diǎn)的右子節(jié)點(diǎn)
                p.parent.left = l;      //B為A的父節(jié)點(diǎn)的右子樹
            l.right = p;                //A為B的右子樹
            p.parent = l;               //設(shè)置A的父節(jié)點(diǎn)為B
        }
    }

    
    /**
     * 平衡而二叉樹的插入操作
     * 基本原理為：
     * 1.首先如同二叉排序樹一般，找到其要插入的節(jié)點(diǎn)的位置，并把元素插入其中；
     * 2.自下向上進(jìn)行回溯，回溯做兩個(gè)事情：
     * (1)其一是修改祖先節(jié)點(diǎn)的平衡因子，當(dāng)插入 一個(gè)節(jié)點(diǎn)時(shí)只有根節(jié)點(diǎn)到插入節(jié)點(diǎn)
     * 的路徑中的節(jié)點(diǎn)的平衡因子會(huì)被改變，而且改變的原則是當(dāng)插入節(jié)點(diǎn)在某節(jié)點(diǎn)(稱為A)
     * 的左子樹 中時(shí)，A的平衡因子(稱為BF)為BF+1,當(dāng)插入節(jié)點(diǎn)在A的右子樹中時(shí)A的BF-1，
     * 而判斷插入節(jié)點(diǎn)在左子樹中還是右子樹中只要簡(jiǎn)單的比較它與A的大小
     * (2)在改變祖先節(jié)點(diǎn)的平衡因子的同時(shí)，找到最近一個(gè)平衡因子大于2或小于-2的節(jié)點(diǎn)，
     * 從這個(gè)節(jié)點(diǎn)開始調(diào)整最小不平衡樹進(jìn)行旋轉(zhuǎn)調(diào)整，關(guān)于如何調(diào)整見下文。
     * 由于調(diào)整后，最小不平衡子樹的高度與插入節(jié)點(diǎn)前的高度相同，故不需繼續(xù)要調(diào)整祖先節(jié)點(diǎn)。
     * 這里還有一個(gè)特殊情況，如果調(diào)整BF時(shí)，發(fā)現(xiàn)某個(gè)節(jié)點(diǎn)的BF變?yōu)?了，則停止向上繼續(xù)調(diào)整，
     * 因?yàn)檫@表明此節(jié)點(diǎn)中高度小的子樹增加了新節(jié)點(diǎn)，高度不變，那么祖先節(jié)點(diǎn)的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的父節(jié)點(diǎn)
        Comparable<? super E> e = (Comparable<? super E>) element;
        //從根節(jié)點(diǎn)向下搜索，找到插入位置
        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;   
        }
        //自下向上回溯，查找最近不平衡節(jié)點(diǎn)
        while(parent!=null){
            cmp = e.compareTo(parent.element);
            if(cmp < 0){    //插入節(jié)點(diǎn)在parent的左子樹中
                parent.balance++;
            }else{           //插入節(jié)點(diǎn)在parent的右子樹中
                parent.balance--;
            }
            if(parent.balance == 0){    //此節(jié)點(diǎn)的balance為0，不再向上調(diào)整BF值，且不需要旋轉(zhuǎn)
                break;
            }
            if(Math.abs(parent.balance) == 2){  //找到最小不平衡子樹根節(jié)點(diǎn)
                fixAfterInsertion(parent);
                break;                  //不用繼續(xù)向上回溯
            }
            parent = parent.parent;
        }
        size ++;
        return true;
    }
    
    /**
     * 調(diào)整的方法：
     * 1.當(dāng)最小不平衡子樹的根(以下簡(jiǎn)稱R)為2時(shí)，即左子樹高于右子樹：
     * 如果R的左子樹的根節(jié)點(diǎn)的BF為1時(shí)，做右旋；
     * 如果R的左子樹的根節(jié)點(diǎn)的BF為-1時(shí)，先左旋然后再右旋
     * 
     * 2.R為-2時(shí)，即右子樹高于左子樹：
     * 如果R的右子樹的根節(jié)點(diǎn)的BF為1時(shí)，先右旋后左旋
     * 如果R的右子樹的根節(jié)點(diǎn)的BF為-1時(shí)，做左旋
     * 
     * 至于調(diào)整之后，各節(jié)點(diǎn)的BF變化見代碼
     */
    private void fixAfterInsertion(Entry<E> p){
        if(p.balance == 2){
            leftBalance(p);
        }
        if(p.balance == -2){
            rightBalance(p);
        }
    }
    
    
    /**
     * 做左平衡處理
     * 平衡因子的調(diào)整如圖：
     *         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:            //左高，右旋調(diào)整,旋轉(zhuǎn)后樹的高度減小
            t.balance = l.balance = EH;
            rotateRight(t);
            break; 
        case RH:            //右高，分情況調(diào)整                                          
            Entry<E> rd = l.right;
            switch (rd.balance) {   //調(diào)整各個(gè)節(jié)點(diǎn)的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,這種情況在添加時(shí)不可能出現(xiàn)，只在移除時(shí)可能出現(xiàn)，旋轉(zhuǎn)之后整體樹高不變
            l.balance = RH;
            t.balance = LH;
            rotateRight(t);
            heightLower = false;
            break;
        }
        return heightLower;
    }
    
    /**
     * 做右平衡處理
     * 平衡因子的調(diào)整如圖：
     *           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:            //左高，分情況調(diào)整
            Entry<E> ld = r.left;
            switch (ld.balance) {   //調(diào)整各個(gè)節(jié)點(diǎn)的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:            //右高，左旋調(diào)整
            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對(duì)象，否則返回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其實(shí)是刪除s
        //所有的刪除左右子樹不為空的節(jié)點(diǎn)都可以調(diào)整為刪除左右子樹有其一不為空，或都為空的情況。
        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節(jié)點(diǎn)
                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的父節(jié)點(diǎn)，所以可以直接從它開始向上回溯
            fixAfterDeletion(replacement);  

        } else if (p.parent == null) { // 如果全樹只有一個(gè)節(jié)點(diǎn)
            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;
            }
        }   
    }
    
    /**
     * 返回以中序遍歷方式遍歷樹時(shí)，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的右子樹，則繼續(xù)向上搜索其直接后繼
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }
    
    /**
     * 刪除某節(jié)點(diǎn)p后的調(diào)整方法：
     * 1.從p開始向上回溯，修改祖先的BF值，這里只要調(diào)整從p的父節(jié)點(diǎn)到根節(jié)點(diǎn)的BF值，
     * 調(diào)整原則為，當(dāng)p位于某祖先節(jié)點(diǎn)(簡(jiǎn)稱A)的左子樹中時(shí)，A的BF減1，當(dāng)p位于A的
     * 右子樹中時(shí)A的BF加1。當(dāng)某個(gè)祖先節(jié)點(diǎn)BF變?yōu)?或-1時(shí)停止回溯，這里與插入是相反的，
     * 因?yàn)樵具@個(gè)節(jié)點(diǎn)是平衡的，刪除它的子樹的某個(gè)節(jié)點(diǎn)并不會(huì)改變它的高度
     * 
     * 2.檢查每個(gè)節(jié)點(diǎn)的BF值，如果為2或-2需要進(jìn)行旋轉(zhuǎn)調(diào)整，調(diào)整方法如下文，
     * 如果調(diào)整之后這個(gè)最小子樹的高度降低了，那么必須繼續(xù)從這個(gè)最小子樹的根節(jié)點(diǎn)(假設(shè)為B)繼續(xù)
     * 向上回溯，這里和插入不一樣，因?yàn)锽的父節(jié)點(diǎn)的平衡性因?yàn)槠渥訕銪的高度的改變而發(fā)生了改變，
     * 那么就可能需要調(diào)整，所以刪除可能進(jìn)行多次的調(diào)整。
     * 
     */
    private void fixAfterDeletion(Entry<E> p){
        boolean heightLower = true;     //看最小子樹調(diào)整后，它的高度是否發(fā)生變化，如果減小，繼續(xù)回溯
        Entry<E> t = p.parent;
        Comparable<? super E> e = (Comparable<? super E>)p.element;
        int cmp;
        //自下向上回溯，查找不平衡的節(jié)點(diǎn)進(jìn)行調(diào)整
        while(t!=null && heightLower){
            cmp = e.compareTo(t.element);
            /**
             * 刪除的節(jié)點(diǎn)是右子樹，等于的話，必然是刪除的某個(gè)節(jié)點(diǎn)的左右子樹不為空的情況
             * 例如：     10
             *          /    \
             *         5     15
             *       /   \
             *      3    6 
             * 這里刪除5，是把6的值賦給5，然后刪除6，這里6是p，p的父節(jié)點(diǎn)的值也是6。
             * 而這也是右子樹的一種
             */ 
            if(cmp >= 0 ){   
                t.balance ++;
            }else{
                t.balance --;
            }
            if(Math.abs(t.balance) == 1){   //父節(jié)點(diǎn)經(jīng)過(guò)調(diào)整平衡因子后，如果為1或-1，說(shuō)明調(diào)整之前是0，停止回溯。
                break;
            }
            Entry<E> r = t;
            //這里的調(diào)整跟插入一樣
            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;   //右高
    
    /**
     * 樹節(jié)點(diǎn)，為方便起見不寫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;
        }
            
    }
    
    
    //返回中序遍歷此樹的迭代器,返回的是一個(gè)有序列表
    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){  //找到中序遍歷的第一個(gè)元素
                    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));
    }
    
    
    //測(cè)試，你也可以任意測(cè)試
    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()+" ");
        }
    }
}