AQS

树结构入门

树（tree）是一种抽象数据类型（ADT），用来模拟具有树状结构性质的数据集合

它是由n（n>0）个有限节点通过连接它们的边组成一个具有层次关系的集合

把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的

• 树有很多种，向上面的一个节点有多余两个的子节点的树，称为多路树
• 而每个节点最多只能有两个子节点的一种形式被称为二叉树

节点：上图的圆圈，比如A，B，C等都是表示节点，在Java面向对象中，节点一般代表对象

边：连接节点的“线”称为边，边表示节点的关联关系，一般从一个节点到另一个节点的唯一方法就是沿着一条顺着有边的道路前进，Java中通常代表对象的引用

路径

顺着节点的边从一个节点走到另一个节点，所经过的节点的顺序排列就称为”路径”
根

树顶端的节点称为根，一棵树只有一个根，如果要把一个节点和边的集合称为树，那么从根到其他任何一个节点都必须有且只有一条路径，A是根节点

父节点

若一个节点含有子节点，则这个节点称为其子节点的父节点
子节点

一个节点含有的子树的节点称为该节点的子节点
叶节点

没有子节点的节点称为叶节点

节点的层次

从根开始定义，根为第一层，根的子节点为第二层，以此类推
深度

对于任意节点n，n的深度为从根到n的唯一路径长，根的深度为0（从上往下看）
高度

对于任意节点n，n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0（从下往上看）

二叉搜索树

二叉树： 树的每个节点最多只能有两个子节点

二叉搜索树的条件

• 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值
• 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
• 它的左、右子树也分别为二叉排序树（子树也满足搜索树条件）

二叉搜索树-查找节点

查找某个节点，我们必须从根节点开始查找

• 查找值比当前节点值大，则搜索右子树
• 查找值等于当前节点值，停止搜索（终止条件）
• 查找值小于当前节点值，则搜索左子树

二叉搜索树-插入节点

要插入节点，必须先找到插入的位置，与查找操作相似，由于二叉树的特殊性，待插入的节点也需要从根节点开始进行比较，小于根节点则与根节点左子树比较，反之则与右子树比较，直到左子树为空，则插入到相应为空的位置

二叉搜索树-遍历节点

遍历树是根据一种特定的顺序访问树的每一个节点，比较常用的有前序遍历，中序遍历和后续遍历，而二叉搜索树最常用的是中序遍历

• 中序遍历：左子树→根节点→右子树
• 前序遍历：根节点→左子树→右子树
• 后序遍历：左子树→右子树→根节点

二叉搜索树-查找最大值最小值

要找最小值，先找根的左节点，然后一直找这个左子树的左节点，直到找到没有左节点的节点，那么这个节点就是最小值

同理要找最大值，一直找根节点的右子树，直到没有右节点，则就是最大值

二叉搜索树-删除节点

删除节点是二叉搜索树中最复杂的操作，删除的节点有三种情况

1、该节点是叶节点（没有子节点）

2、该节点有一个子节点

3、该节点有两个子节点

• 删除没有子节点的节点

要删除叶节点，只需要改变该节点的父节点引用该节点的值，即将其引用改为null即可

• 删除有一个子节点的节点

删除有一个子节点的节点，我们只需要将其父节点原本指向该节点的引用，改为指向该节点子节点即可

• 删除有两个子节点的节点

当删除的节点存在两个节点，那么删除之后，两个节点的位置我们就没办法处理了

既然处理不了，我们就想到一种办法，用另一个节点来代替被删除的节点，那么用哪一个节点来代替呢？

我们知道二叉搜索树中的节点是按照关键字来进行排列的，大于一个节点的最小节点是它的中序遍历后续节点，用后续节点来代替删除的节点，显然该二叉搜索树还是有序的

删除有必要吗？

通过上面的分析，我们发现删除其实挺复杂的，那么其实我们可以不用真正删除该节点，只需要在Node类中添加一个标识字段Delete，当该字段为true时，表示该节点已删除，反之则没有删除

二叉搜索树-时间复杂度分析

1、回顾经典-二分查找算法

[1,2,3,4,5,6,7,8….100]

• 暴力算法：靠前的查找较快，往后的就很慢

• 二分查找算法：每次都会随机挑选与查找数比较，抛弃一半不符合条件的数据，适用条件：有序数组，性能：非常不错，每次迭代查询可以排除一半的结果

public static void main(String[] args) {

    int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};

    System.out.println(binarySearch(arr,15));

}

/**
 * 二分查找算法，查找到数组中某个数的索引值
 */
public static Integer binarySearch(int[] arr,int data){

    //下界
    int low = 0;
    //上界
    int height = arr.length - 1;

    while (low <= height){

        //获得数组的中间位置
        int mid = (height + low) / 2;

        if (arr[mid] < data){
            low = mid + 1;
        } else if (arr[mid] == data){
            return mid;
        }else {
            height = mid - 1;
        }

    }

    //查找不到返回-1
    return -1;

}

缺点：依赖有序数组，性能才能不错

数组的缺陷：没有办法快速插入，也没有办法扩容

那怎么才能拥有二分查找的高性能又能拥有链表一样的灵活性？

二分查找树这一数据结构就符合特点

普通二叉搜索树致命缺陷：

如果数据形成了长链表结构，那么查询效率就会变得低下

怎么解决二叉搜索树退化成线性链表的问题？

如果插入元素时，树可以自动调整两边平衡，会保持不错的性能

AVL树

特点：

1、具有二叉查找树的全部特性

2、每个节点的左子树和右子树的高度差至多等于1

平衡树基于这种特点就可以保证不会出现大量节点偏向于一边的情况了（插入或者删除时，会发生左旋，右旋操作，使这棵树再次左右保持一定平衡）

为什么有了AVL树后还要有红黑树？

虽然平衡树解决了二叉查找树退化为近似链表的缺点，不过却不是最佳的，因为平衡树要求每个节点的左子树和右子树的高度差至多等于这个要求实在是太严了，导致每次进行插入、删除节点的时候，几乎都会破坏平衡树的第二个规则，进而都需要进行左旋和右旋的调整，使之再次称为一颗符合要求的平衡树

• 显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁的进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树

红黑树

性质1：每个节点要么是黑色，要么是红色

性质2： 根节点是黑色

性质3：每个叶子节点（NIL、空节点）是黑色

性质4：每个红色节点的两个子节点一定都是黑色

• 不能有两个红色节点相连

性质5：任意一节点到每个叶子节点的路径都包含数量相同的黑节点

• 如果一个节点存在黑子节点，那么该节点肯定有两个子节点

红黑树并不是一个完美平衡的二叉查找树，但左子树和右子树的黑节点的层数是相等，任意一个节点到每个叶子节点的路径都包含数量相同的黑节点，我们称红黑树这种平衡为黑色完美平衡，这棵树就是趋近于平衡状态的

红黑树能自平衡，它靠的是什么？

三种操作：左旋、右旋和变色

1、变色：节点的颜色由红变黑或由黑变红

2、左旋：以某个节点作为支点（旋转节点），其右子节点变为旋转节点的父节点，右子节点的左子节点，变为旋转节点的右子节点，左子节点保持不变

3、右旋：以某个节点作为支点（旋转节点），其左子节点变为旋转节点的父节点，左子节点的右子节点，变为旋转节点的左子节点，右子节点保持不变

---

左旋

---

右旋

---

红黑树的插入

插入操作包括两部分工作：

1、查找插入的位置

2、插入后自平衡

注意： 插入节点，必须为红色，红色在父节点（如果存在）为黑色节点时，红黑树的平衡没被破坏，不需要做自平衡操作，但如果插入节点是黑色，那么插入位置所在的子树黑色节点总是多1，必须做自平衡

红黑树插入情景分析

情景1：红黑树为空树

• 最简单的一种情景，直接把插入节点作为根节点就行

• 注意：根据红黑树的性质2：根节点是黑色，还需要把插入节点设置为黑色

情景2：插入节点的Key已存在

更新当前节点的value值，为插入节点的值

情景3：插入节点的父节点是黑节点

由于插入的节点是红色的，并不会影响红黑树的完美平衡，直接插入即可，无需做自平衡

情景4：插入节点的**父节点(P)**为红色

如果插入节点的父节点为红色，那么该父节点不可能为根节点，所以插入节点总是存在祖父节点(PP)

• 情景4.1：如果**叔叔节点(U)**存在（和父节点同一级的红色节点）

  • 因为不可以同时存在两个相连的红色节点，那么此时该插入子树的红黑层数的情况是：黑红红，显然最简单的处理方式是把其改为红黑红

  • 处理：

    1、将P节点和U节点改为黑色

    2、将PP节点改为红色

    3、将PP设置为当前节点，进行后续处理

    4、如果PP节点的父节点是黑色，那么无需处理，如果PP节点的父节点是红色，那么还需要继续做插入操作自平衡处理，直到平衡为止

    

• 情景4.2：如果U节点不存在或者为黑节点，并且插入节点的P节点是PP节点的左子节点，注意：单纯从插入前来看，叔叔节点非红即空（NIL节点），否则的话破坏了红黑树的性质5，此路径会比其它路径多一个黑色节点

  • 情景4.2.1：新插入节点，为其父节点的左子节点（LL双红情况）

    • 处理：

      1、将P节点设置为黑色，将PP设置为红色

      2、对PP节点进行右旋

      

  • 情景4.3.2：新插入节点为P节点的右子节点（LR红色情况）

    • 处理：

      1、先对P节点进行左旋

      2、把当前节点变黑，把PP节点变红，进行右旋

    

• 情景4.3：U节点不存在或为黑节点，并且插入节点的P节点是PP节点的右子节点，该情景对应4.2只是方向反转

  • 情景4.3.1：新插入节点，为其父节点的右子节点（RR红色情况）

    • 处理：

      1、将P节点设置为黑色，将PP设置为红色

      2、对PP节点进行左旋

      

    ​

  • 情景4.3.2：新插入节点为P节点的左子节点（RL红色情况）

    • 处理：

      1、先对P节点进行右旋

      2、把当前节点变黑，把PP节点变红，进行左旋

    

Java代码实现红黑树

package com.os467;

public class RedBlackTree<K extends Comparable<K>,V> {

    private static final boolean RED = true;

    private static final boolean BLACK = false;

    //树根的引用
    private RedBlackNode root;

    public RedBlackNode getRoot() {
        return root;
    }

    /**
     * 获取当前节点的父节点
     */
    private RedBlackNode parentOf(RedBlackNode node){

        if (node != null){

            return node.parent;

        }

        return null;
    }

    /**
     * 节点是否为红色
     */

    private boolean isRed(RedBlackNode node){

        if (node != null){

            return node.color == RED;

        }

        return false;

    }

    /**
     * 设置节点为红色
     */
    private void setRed(RedBlackNode node){

        if (node != null){

            node.color = RED;

        }

    }

    /**
     * 节点是否为黑色
     */
    private boolean isBlack(RedBlackNode node){

        if (node != null){

            return node.color == BLACK;

        }

        return false;

    }

    /**
     * 设置节点为黑色
     */
    private void setBlack(RedBlackNode node){

        if (node != null){

            node.color = BLACK;

        }

    }

    /**
     * 左旋
     *
     *      P                   P
     *      |                   |
     *      x                   y
     *    /  \       ---->    /  \
     *   lx   y              x   ry
     *      /  \           /  \
     *     ly   ry        lx  ly
     */
    private void leftRotate(RedBlackNode x){

        RedBlackNode y = x.right;

        //将x的右子节点设置为y的左子节点
        x.right = y.left;

        if (y.left != null){
            y.left.parent = x;
        }

        //将y旋转到x的位置
        if (x.parent != null){

            y.parent = x.parent;

            if (x == x.parent.left){

                x.parent.left = y;

            }else {

                x.parent.right = y;

            }

        }else {
            
            //x为根节点的时候，此时需要更新y为根节点引用
            this.root = y;
            //使得y的父节点丢失
            y.parent = null;

        }

        //将x的父节点设置为y
        x.parent = y;
        //将y的左子节点设置为x
        y.left = x;

    }



    /**
     * 右旋
     *
     *            P                P
     *            |                |
     *            x     ---->      y
     *          /  \             /  \
     *         y    rx         ly    x
     *       /  \                   / \
     *     ly   ry                ry   rx
     *
     */
    private void rightRotate(RedBlackNode x){

        RedBlackNode y = x.left;

        //将x的左字节点设置为y的右子节点
        x.left = y.right;

        //设置父节点
        if (y.right != null){

            y.right.parent = x;

        }

        //将y的右子节点设置为x
        y.right = x;

        //如果x的父节点不为空，非根
        if (x.parent != null){

            y.parent = x.parent;

            //如果x为其父节点的右子节点，将其父节点的右子节点设置为y
            if (x == x.parent.right){

                x.parent.right = y;

            }else {

                x.parent.left = y;

            }

        }else {

            //设置根节点为y

            this.root = y;
            y.parent = null;

        }

        //设置x的父节点为y
        x.parent = y;


    }



    /**
     * 中序打印二叉树
     */
    public void inOrderPrint(){

        inOrderPrint(this.root);

    }

    /**
     * 中序打印
     */
    private void inOrderPrint(RedBlackNode node){

        if (node != null){

            inOrderPrint(node.left);

            inOrderPrint(node.right);
        }
    }

    /**
     * 公开的插入方法
     */
    public void insert(K key,V value){

        RedBlackNode node = new RedBlackNode();

        node.setKey(key);

        node.setValue(value);

        //新节点一定是红色
        node.setColor(RED);

        //调用私有的insert方法
        insert(node);

    }

    /**
     * 私有的插入方法
     * @param node
     */
    private void insert(RedBlackNode node){

        //第一步，查找当前node的父节点
        RedBlackNode parent = null;
        //x作为遍历查询的对象
        RedBlackNode x = this.root;

        //查找到合适的插入位置，应该挂在哪个节点下
        while (x != null){
            parent = x;

            //cmp > 0 说明node的key大于x的key需要到x的右子树查找
            //cmp == 0 说明node的key等于x的key，说明需要进行替换操作
            //cmp < 0 说明node的key小于x的key，需要到x的左子树查找
            int cmp = node.key.compareTo(x.key);

            if (cmp > 0){

                x = x.right;

            }else if (cmp == 0){

                x.setValue(node.getValue());
                return;

            }else {

                x = x.left;

            }

        }

        //此时的parent已经为适合的插入位置
        node.parent = parent;

        //判断应该挂在左边还是右边
        if (parent != null){

            //判断node与parent的key谁大
            int cmp = node.key.compareTo(parent.key);

            if (cmp > 0){

                parent.right = node;

            }else {

                parent.left = node;

            }

        }else {

            //当前为根
            this.root = node;

        }

        //需要调用修复红黑树的平衡方法
        insertFixUp(node);

    }

    /**
     * 修复红黑树平衡的方法
     *
     * 情景1：红黑树为空树，设置插入节点为根节点为黑色
     * 情景2：插入节点key已经存在，不需要修改
     * 情景3：插入节点的父节点为黑色，因为插入的默认为红色节点，所以没有破坏红黑树平衡
     *
     * 情景4：需要调整平衡
     *  插入的父节点为红色
     *      4.1：叔叔节点存在并且为红色，将爸爸和叔叔染色为黑色，将爷爷染色为红色，将爷爷节点为当前节点进行下一轮处理
     *      4.2：叔叔节点不存在或者为黑色，并且插入系欸但为父节点的左子节点
     *          4.2.1：新插入节点，为其父节点的左子节点（LL双红情况）
     *          4.3.2：新插入节点为父节点的右子节点（LR红色情况）
     *      4.3：叔叔节点不存在或为黑节点，并且插入节点的父节点是祖父节点的右子节点
     *          4.3.1：新插入节点，为其父节点的右子节点（RR红色情况）
     *          4.3.2：新插入节点为父节点的左子节点（RL红色情况）
     *
     */

    private void insertFixUp(RedBlackNode node){

        this.root.setColor(BLACK);

        RedBlackNode parent = parentOf(node);
        RedBlackNode grandpa = parentOf(parent);

        //情景4：父节点为红
        if (parent != null && isRed(parent)){

            //如果父节点为红则一定存在爷爷节点，根不可能为红
            RedBlackNode uncle = null;

            if (parent == grandpa.left){

                uncle = grandpa.right;

                //4.1：父-叔双红（左子树情况）
                if (uncle != null && isRed(uncle)){

                    //将爸爸节点叔叔节点变为黑色，爷爷节点变为红色
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(grandpa);

                    //以爷爷节点为当前节点开始调节
                    insertFixUp(grandpa);
                    return;

                }

                //4.2：叔叔节点不存在，或者为黑色
                if (uncle == null || isBlack(uncle)){

                    //4.2.1：当前节点为父节点右子节点，将父亲节点变黑，将祖父节点变红，右旋祖父节点
                    if (node == parent.left){

                        setBlack(parent);
                        setRed(grandpa);
                        rightRotate(grandpa);
                        return;
                    }

                    //4.2.2：插入节点为其父节点的右子节点（LR情况）
                    //以爸爸节点进行一次左旋，得到LL情况（4.2.1），然后指定爸爸节点为当前节点进行下一轮处理
                    if (node == parent.right){

                        leftRotate(parent);
                        insertFixUp(parent);
                        return;
                    }

                }

            }else {//父节点为爷爷节点的右子树

                uncle = grandpa.left;

                //4.1：叔-父双红（右子树情况）
                if (uncle != null && isRed(uncle)){

                    //将爸爸节点叔叔节点变为黑色，爷爷节点变为红色
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(grandpa);

                    //以爷爷节点为当前节点开始调节
                    insertFixUp(grandpa);
                    return;

                }

                uncle = grandpa.left;
                //情景4.3：叔叔节点不存在，或者为黑色
                if (uncle == null || isBlack(uncle)){

                    //4.3.1：插入节点为父节点右子节点（RR情况）
                    //将父节点变黑，爷爷节点变红，左旋爷爷节点
                    if (node == parent.right){

                        setBlack(parent);
                        setRed(grandpa);
                        leftRotate(grandpa);
                    }

                    //4.3.2：插入节点为父节点左子节点（RL情况）
                    //右旋爸爸节点，得到RR双红情况（4.3.1），然后指定爸爸节点为当前节点进行下一轮处理
                    if (node == parent.left){

                        rightRotate(parent);
                        insertFixUp(parent);
                        return;

                    }

                }

            }

        }

    }

    /**
     * 红黑树节点
     * @param <K>
     * @param <V>
     */
    static class RedBlackNode<K extends Comparable<K>,V>{

        //该节点的父节点
        private RedBlackNode parent;

        //该节点的左节点
        private RedBlackNode left;

        //该节点的右节点
        private RedBlackNode right;

        //该节点的key
        private K key;

        //该节点的value
        private V value;

        //该节点的颜色
        private boolean color;

        public RedBlackNode() {
        }

        public RedBlackNode(RedBlackNode parent, RedBlackNode left, RedBlackNode right, K key, V value, boolean color) {
            this.parent = parent;
            this.left = left;
            this.right = right;
            this.key = key;
            this.value = value;
            this.color = color;
        }

        public RedBlackNode getParent() {
            return parent;
        }

        public void setParent(RedBlackNode parent) {
            this.parent = parent;
        }

        public RedBlackNode getLeft() {
            return left;
        }

        public void setLeft(RedBlackNode left) {
            this.left = left;
        }

        public RedBlackNode getRight() {
            return right;
        }

        public void setRight(RedBlackNode right) {
            this.right = right;
        }

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }

        public boolean isColor() {
            return color;
        }

        public void setColor(boolean color) {
            this.color = color;
        }
    }

}

显示红黑树的函数（引用）

package com.os467;


public class TreeOperation {

    public static int getTreeDepth(RedBlackTree.RedBlackNode root) {
        return root == null ? 0 : (1 + Math.max(getTreeDepth(root.getLeft()), getTreeDepth(root.getRight())));

    }

    private static void writeArray(RedBlackTree.RedBlackNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
        // 保证输入的树不为空

        if (currNode == null) return;

        // 先将当前节点保存到二维数组中

        res[rowIndex][columnIndex] = String.valueOf(currNode.getKey()+"-"+(currNode.isColor()? "R":"B")+"");

        // 计算当前位于树的第几层

        int currLevel = ((rowIndex + 1) / 2);

        // 若到了最后一层，则返回

        if (currLevel == treeDepth) return;

        // 计算当前行到下一行，每个元素之间的间隔(下一行的列索引与当前元素的列索引之间的间隔)

        int gap = treeDepth - currLevel - 1;

        // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值

        if (currNode.getLeft() != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";

            writeArray(currNode.getLeft(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);

        }

        // 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值

        if (currNode.getRight() != null) {
            res[rowIndex + 1][columnIndex + gap] = "\\";

            writeArray(currNode.getRight(), rowIndex + 2, columnIndex + gap * 2, res, treeDepth);

        }

    }

    public static void show(RedBlackTree.RedBlackNode root) {
        System.out.println("当前root"+root.getKey());
        if (root == null) System.out.println("EMPTY!");

        // 得到树的深度
        int treeDepth = getTreeDepth(root);
        // 最后一行的宽度为2的(n - 1)次方乘3，再加1
        // 作为整个二维数组的宽度
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
        // 用一个字符串数组来存储每个位置应显示的元素
        String[][] res = new String[arrayHeight][arrayWidth];
        // 对数组进行初始化，默认为一个空格
        for (int i = 0; i < arrayHeight; i ++) {
            for (int j = 0; j < arrayWidth; j ++) {
                res[i][j] = " ";
            }
        }

        // 从根节点开始，递归处理整个树
        // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
        writeArray(root, 0, arrayWidth/ 2, res, treeDepth);
        // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即
        for (String[] line: res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < line.length; i ++) {
                sb.append(line[i]);
                if (line[i].length() > 1 && i <= line.length - 1) {
                    i += line[i].length() > 4 ? 2: line[i].length() - 1;
                }
            }
            System.out.println(sb.toString());
        }
    }
}

测试

package com.os467;

import java.util.Scanner;

public class RedBlackTreeDemo {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        RedBlackTree<String,Object> redBlackTree = new RedBlackTree<>();

        while (true){
            System.out.println("请输入key");
            String key = scanner.next();
            System.out.println();
            redBlackTree.insert(key,null);

            TreeOperation.show(redBlackTree.getRoot());
        }

    }

}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 1300452403@qq.com