高阶-二叉平衡树

一、AVL树

1.二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过
1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

2.一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
（1）它的左右子树都是AVL树
（2）左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

3.AVL树的实现

class AVTNode {
    
    public int val;
    public int bf;//平衡因子
    public AVTNode left;
    public AVTNode right;
    public AVTNode par;

    public AVTNode() {
    
    }

    public AVTNode(int val) {
    
        this.val = val;
    }
}
public class AVLTest {
    
    public AVTNode root;


    public boolean insert(int val) {
    
        AVTNode node = new AVTNode(val);

        if (root == null) {
    
            root = node;
            return true;
        }
        AVTNode par = null;
        AVTNode cur = root;
        while (cur != null) {
    
            if (cur.val == val) {
    
                return false;
            } else if (cur.val > val) {
    
                par = cur;
                cur = cur.left;
            } else {
    
                par = cur;
                cur = cur.right;
            }
        }
        node.par = par;
        //cur == null
        if (par.val > val) {
    
            par.left = node;
        } else {
    
            par.right = node;
        }
        //判断平衡因子
        adjustBf(par,node);
        return true;
    }

    private void adjustBf(AVTNode par, AVTNode node) {
    
        while (Math.abs(par.bf) <= 1) {
    
            if (par.left == node) {
    
                par.bf++;
            } else if (par.right == node) {
    
                par.bf--;
            }
            //说明子树的高度没有改变
            if (par.bf == 0) {
    
                return;
            }
            if (par.bf == -1 || par.bf == 1) {
    
                //子树的高度改变，判断父节点的父节点的bf有没有改变
                node = par;
                par = par.par;
                if (par == null) {
    
                    //父节点的父节点为空，说明父节点是root
                    return;
                }
            }
            if (par.bf == 2 || par.bf == -2) {
    
                break;
            }
        }
        //出现失衡情况
        if (par.bf == 2) {
    
            if (node.bf == 1) {
    
                //左左失衡
                rightRotate(par);
                par.bf = node.bf = 0;//推导即可
            } else {
    
                //左右失衡
                AVTNode c = node.right;
                int condition;
                if (par.right == null) {
    
                    condition = 1;
                } else if (c.bf == 1) {
    
                    condition = 2;
                } else {
    
                    condition = 3;
                }

                leftRotate(node);
                rightRotate(par);

                if (condition == 1) {
    
                    par.bf = node.bf = c.bf = 0;
                } else if (condition == 2) {
    
                    par.bf = -1;
                    node.bf = c.bf = 0;
                } else {
    
                    node.bf = 1;
                    par.bf = c.bf = 0;
                }
            }
        } else {
    
            if (node.bf == 1) {
    
                //右左失衡
                AVTNode c = node.left;
                int condition;
                if (par.left == null) {
    
                    condition = 1;
                } else if (c.bf == 1) {
    
                    condition = 2;
                } else {
    
                    condition = 3;
                }
                rightRotate(node);
                leftRotate(par);

                if (condition == 1) {
    
                    par.bf = node.bf = c.bf = 0;
                } else if (condition == 2) {
    
                    node.bf = -1;
                    par.bf = c.bf = 0;
                } else {
    
                    par.bf = 1;
                    node.bf = c.bf = 0;
                }
            } else {
    
                //右右失衡
                leftRotate(par);
                par.bf = node.bf = 0;
            }
        }
    }
    //左旋
    /** * 测试用例：6种 * node有父亲，node是父亲的left node有父亲，node是父亲的right * node没有父亲 * right节点的左子树是否为空 * @param node */
    public void leftRotate(AVTNode node) {
    
        AVTNode parent = node.par;//node可能存在的父亲节点
        AVTNode right = node.right;//node.left
        AVTNode rightOfLeft = right.left;

        //进行左旋
        right.par = parent;
        if (parent == null) {
    //parent==null说明node是根节点，交换之后right就是根节点
            root = right;
        } else {
    
            if (node == parent.left) {
    
                parent.left = right;
            } else {
    
                parent.right = right;
            }
        }
        right.left =  node;
        node.par = right;
        node.right = rightOfLeft;
        if (rightOfLeft != null) {
    
            rightOfLeft.par = node;
        }
    }

    //右旋
    public void rightRotate(AVTNode node) {
    
        AVTNode parent = node.par;
        AVTNode left = node.left;
        AVTNode leftOfRight = left.right;

        //进行右旋
        left.par = parent;
        if (parent == null) {
    
            root = left;
        } else {
    
            if (node == parent.left) {
    
                parent.left = left;
            } else {
    
                parent.right = left;
            }
        }
        left.right = node;
        node.par = left;
        node.left = leftOfRight;
        if (leftOfRight != null) {
    
            leftOfRight.par = node;
        }
    }

    public static void main(String[] args) {
    
        AVLTest tree = new  AVLTest();
        AVTNode n1 = new AVTNode(5);
        AVTNode n2 = new AVTNode(6);
        AVTNode n3 = new AVTNode(7);
        n1.right = n2;
        n2.par = n1;
        n2.right = n3;
        n3.par = n2;
        tree.leftRotate(n1);
        System.out.println("hello");//打断点查看
    }
}

4.AVL树的性能分析
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询
时高效的时间复杂度，即 。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要
维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要
一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修
改，就不太适合。

二、红黑树

1.红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

2.红黑树的性质
（1） 每个结点不是红色就是黑色
（2）根节点是黑色的
（3）如果一个节点是红色的，则它的两个孩子结点是黑色的
（4）对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
（5）每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

3.红黑树的实现

public class RBTreeNode {
    
    public long val;

    public RBTreeNode left;
    public RBTreeNode right;
    public RBTreeNode parent;

    public boolean color;
    public static final boolean BLACK = true;
    public static final boolean RED = false;

    public RBTreeNode(long val, RBTreeNode parent, boolean color) {
    
        this.val = val;
        this.left = this.right = null;
        this.parent = parent;
        this.color = color;
    }
}

public class RBTree {
    
    public RBTreeNode root = null;
    //节点的个数
    public int size = 0;

    public boolean insert(long val) {
    
        if (root == null) {
    
            root = new RBTreeNode(val,null,BLACK);
            size++;
            return true;
        }
        RBTreeNode parent = null;
        RBTreeNode cur = root;
        while (cur != null) {
    
            if (val == cur.val) {
    
                return false;
            } else if (val < cur.val) {
    
                parent = cur;
                cur = cur.left;
            } else {
    
                parent = cur;
                cur = cur.right;
            }
        }
        //cur == null,插入的节点一定是红色
        RBTreeNode node = new RBTreeNode(val,parent,RED);
        if (val < parent.val) {
    
            parent.left = node;
        } else {
    
            parent.right = node;
        }
        size++;
        //因为parent节点一定是红色的，所以要进行调整
        adjustBalance(node);
        return true;
    }

    private void adjustBalance(RBTreeNode node) {
    
        while (true) {
    
            RBTreeNode parent = node.parent;
            if (parent == null) {
    
                //是根节点
                break;
            }
            if (parent.color == BLACK) {
    
                break;
            }
            //parent.color = RED,进行调整
            RBTreeNode grandPa = parent.parent;
            if (parent == grandPa.left) {
    
                RBTreeNode uncle = grandPa.right;
                if (uncle != null && uncle.color == RED) {
    
                    parent.color = uncle.color = BLACK;
                    grandPa.color = RED;
                    node = grandPa;
                    continue;
                } else {
    
                    //判断grandPa和parent的关系 ，parent和node的关系
                    if (node == parent.right) {
    
                        //左旋
                        leftRotate(parent);
                        parent = node;
                    }
                    rightRotate(grandPa);
                    parent.color = BLACK;
                    grandPa.color = RED;
                    break;
                }
            } else {
    
                RBTreeNode uncle = grandPa.left;
                if (uncle != null && uncle.color == RED) {
    
                    parent.color = uncle.color = BLACK;
                    grandPa.color = RED;
                    node = grandPa;
                    continue;
                } else {
    
                    if (node == parent.left) {
    
                        rightRotate(parent);
                        parent = node;
                    }
                    leftRotate(grandPa);
                    parent.color = BLACK;
                    grandPa.color = RED;
                    break;
                }
            }
        }
        //不管根节点的颜色是什么，一律改为黑色
        root.color = BLACK;
    }

    private void rightRotate(RBTreeNode m) {
    
        RBTreeNode parent = m.parent;
        RBTreeNode left = m.left;
        RBTreeNode leftOfRight = left.right;

        left.parent = parent;
        if (parent == null) {
    
            root = left;
        } else {
    
            if (m == parent.left) {
    
                parent.left = left;
            } else {
    
                parent.right = left;
            }
        }
        left.right = m;
        m.parent = left;
        m.left = leftOfRight;
        if (leftOfRight != null) {
    
            leftOfRight.parent = m;
        }
    }

    private void leftRotate(RBTreeNode m) {
    
        RBTreeNode parent = m.parent;
        RBTreeNode right = m.right;

        RBTreeNode rightOfLeft = right.left;

        right.parent = parent;
        if (parent == null) {
    
            root = right;
        } else {
    
            if (m == parent.left) {
    
                parent.left = right;
            } else {
    
                parent.right = right;
            }
        }
        right.left = m;
        m.parent = right;
        m.right = rightOfLeft;
        if (rightOfLeft != null) {
    
            rightOfLeft.parent = m;
        }
    }

}