20190513面试红黑树

亦凉 2022-02-01 02:31 285阅读 0赞

1.什么是红黑树

红黑树是一种自平衡的二叉树，除了符合二叉树的基本特性外，还有一些附加特性:

*  1.节点是红色或黑色。
 *  2.根节点是黑色。
 *  3.每个叶子节点都是黑色的空节点（NIL节点）。
 *  4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
 *  5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

有了这些限制，才保证了红黑树的自平衡，红黑树从根到叶子的最长路径不会超过最短路径的2倍。

当插入或者删除节点的时候，红黑树的规则就有可能被打破，就需要做一些调整，调整有2种方式：变色和旋转，旋转又分为两种形式：左旋转和右旋转；

左旋转：逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子

右旋转：顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子

2.红黑树应用场景

红黑树的应用有很多，其中JDK的集合类TreeMap和TreeSet底层就是红黑树实现的，在java8中，连HashMap也用到了红黑树。

3.红黑树特点

3.1主要特征

*  1.每个节点不是红色就是黑色的；
 *  2.根节点总是黑色的；
 *  3.如果节点是红色的，则它的子节点必须是黑色的（反之不一定）；
 *  4.从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）

3.2为什么数据库索引不用红黑树而用B+树

红黑树当插入删除元素的时候会进行频繁的变色与旋转（左旋，右旋），来保证红黑树的性质，浪费时间。  
但是当数据量较小，数据完全可以放入内存中，不需要进行磁盘IO，这时候，红黑树时间复杂度比B+树低。  
比如TreeSet TreeMap 和HashMap （jdk1.8）就是使用红黑树作为底层数据结构。

3.3为什么不用二叉查找树作为数据库索引

二叉查找树，查找到指定数据，效率其实很高logn。但是数据库索引文件有可能很大，关系型数据存储了上亿条数据，索引文件大则上G，不可能全部放入内存中，  
而是需要的时候换入内存，方式是磁盘页。一般来说树的一个节点就是一个磁盘页。如果使用二叉查找树，那么每个节点存储一个元素，查找到指定元素，需要进行大量的磁盘IO，效率很低。  
而B树解决了这个问题，通过单一节点包含多个data，大大降低了树的高度，大大减少了磁盘IO次数。

\----------------

详细介绍

## 二叉树 ##

由于红黑树本质上就是一棵二叉查找树，所以在了解红黑树之前，咱们先来看下二叉查找树。

二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

*  若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 *  若任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
 *  任意结点的左、右子树也分别为二叉查找树。
 *  没有键值相等的结点（no duplicate nodes）。

因为，一棵由n个结点，随机构造的二叉查找树的高度为lgn，所以顺理成章，一般操作的执行时间为O（lgn）.（至于n个结点的二叉树高度为lgn的证明，可参考算法导论 第12章 二叉查找树 第12.4节）。

但二叉树若退化成了一棵具有n个结点的线性链后，则此些操作最坏情况运行时间为O（n）。后面我们会看到一种基于二叉查找树-红黑树，它通过一些性质使得树相对平衡，使得最终查找、插入、删除的时间复杂度最坏情况下依然为O（lgn）。

优势：二分查找的思想：查找所需的最大次数等同于二叉树的高度；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70][]

缺陷: 插入新节点的时候，二叉树若退化成了一棵具有n个结点的线性链后，则此些操作最坏情况运行时间为O（n）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 1][]

## 红黑树 ##

前面我们已经说过，红黑树，本质上来说就是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

但它是如何保证一棵n个结点的红黑树的高度始终保持在h = logn的呢？这就引出了红黑树的5条性质：

1）每个结点要么是红的，要么是黑的。  
    2）根结点是黑的。  
    3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。  
    4）如果一个结点是红的，那么它的俩个儿子都是黑的。  
    5）对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

正是红黑树的这5条性质，使得一棵n个结点是红黑树始终保持了logn的高度，从而也就解释了上面我们所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论的原因。

如下图所示，即是一颗红黑树(下图引自wikipedia：[http://t.cn/hgvH1l][http_t.cn_hgvH1l])：

![red-black-tree][]

上文中我们所说的 "叶结点" 或"NULL结点"，它不包含数据而只充当树在此结束的指示，这些结点以及它们的父结点，在绘图中都会经常被省略。

## 树的旋转知识 ##

当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。

为了继续保持红黑树的性质，我们可以通过对结点进行重新着色，以及对树进行相关的旋转操作，即修改树中某些结点的颜色及指针结构，来达到对红黑树进行插入或删除结点等操作后，继续保持它的性质或平衡。

例如：向原红黑树插入值为21的新节点，由于父节点22是红色节点，因此这种情况打破了红黑树的规则4（每个红色节点的两个子节点都是黑色），必须进行调整，使之重新符合红黑树的规则。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 2][]

## 树的操作 ##

红-黑树是对二叉搜索树的改进，所以其节点与二叉搜索树是差不多的，只不过在它基础上增加了一个boolean型变量来表示节点的颜色，具体看RBNode类：

public class RBNode<T extends Comparable<T>>{
        boolean color; //颜色
        T key; //关键字(键值)
        RBNode<T> left; //左子节点
        RBNode<T> right; //右子节点
        RBNode<T> parent; //父节点
    
        public RBNode(T key, boolean color, RBNode<T> parent, RBNode<T> left, RBNode<T> right) {
            this.key = key;
            this.color = color;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }
    
        public T getKey() {
            return key;
        }
    
        public String toString() {
            return "" + key + (this.color == RED? "R" : "B");
        }
    }

/*************对红黑树节点x进行左旋操作 ******************/
    /*
     * 左旋示意图：对节点x进行左旋
     *     p                       p
     *    /                       /
     *   x                       y
     *  / \                     / \
     * lx  y      ----->       x  ry
     *    / \                 / \
     *   ly ry               lx ly
     * 左旋做了三件事：
     * 1. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时)
     * 2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
     * 3. 将y的左子节点设为x，将x的父节点设为y
     */
    private void leftRotate(RBNode<T> x) {
        //1. 将y的左子节点赋给x的右子节点，并将x赋给y左子节点的父节点(y左子节点非空时)
        RBNode<T> y = x.right;
        x.right = y.left;
    
        if(y.left != null) 
            y.left.parent = x;
    
        //2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
        y.parent = x.parent;
    
        if(x.parent == null) {
            this.root = y; //如果x的父节点为空，则将y设为父节点
        } else {
            if(x == x.parent.left) //如果x是左子节点
                x.parent.left = y; //则也将y设为左子节点
            else
                x.parent.right = y;//否则将y设为右子节点
        }
    
        //3. 将y的左子节点设为x，将x的父节点设为y
        y.left = x;
        x.parent = y;       
    }

/*************对红黑树节点y进行右旋操作 ******************/
    /*
     * 左旋示意图：对节点y进行右旋
     *        p                   p
     *       /                   /
     *      y                   x
     *     / \                 / \
     *    x  ry   ----->      lx  y
     *   / \                     / \
     * lx  rx                   rx ry
     * 右旋做了三件事：
     * 1. 将x的右子节点赋给y的左子节点,并将y赋给x右子节点的父节点(x右子节点非空时)
     * 2. 将y的父节点p(非空时)赋给x的父节点，同时更新p的子节点为x(左或右)
     * 3. 将x的右子节点设为y，将y的父节点设为x
     */
    private void rightRotate(RBNode<T> y) {
        //1. 将y的左子节点赋给x的右子节点，并将x赋给y左子节点的父节点(y左子节点非空时)
        RBNode<T> x = y.left;
        y.left = x.right;
    
        if(x.right != null) 
            x.right.parent = y;
    
        //2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
        x.parent = y.parent;
    
        if(y.parent == null) {
            this.root = x; //如果x的父节点为空，则将y设为父节点
        } else {
            if(y == y.parent.right) //如果x是左子节点
                y.parent.right = x; //则也将y设为左子节点
            else
                y.parent.left = x;//否则将y设为右子节点
        }
    
        //3. 将y的左子节点设为x，将x的父节点设为y
        x.right = y;
        y.parent = x;       
    }

/*********************** 向红黑树中插入节点 **********************/
    public void insert(T key) {
        RBNode<T> node = new RBNode<T>(key, RED, null, null, null);
        if(node != null) 
            insert(node);
    }
    
    //将节点插入到红黑树中，这个过程与二叉搜索树是一样的
    private void insert(RBNode<T> node) {
        RBNode<T> current = null; //表示最后node的父节点
        RBNode<T> x = this.root; //用来向下搜索用的
    
        //1. 找到插入的位置
        while(x != null) {
            current = x;
            int cmp = node.key.compareTo(x.key);
            if(cmp < 0) 
                x = x.left;
            else
                x = x.right;
        }
        node.parent = current; //找到了位置，将当前current作为node的父节点
    
        //2. 接下来判断node是插在左子节点还是右子节点
        if(current != null) {
            int cmp = node.key.compareTo(current.key);
            if(cmp < 0)
                current.left = node;
            else
                current.right = node;
        } else {
            this.root = node;
        }
    
        //3. 将它重新修整为一颗红黑树
        insertFixUp(node);
    }

1.参考

[https://blog.csdn.net/qq\_36610462/article/details/83277524][https_blog.csdn.net_qq_36610462_article_details_83277524]

[https://cloud.tencent.com/developer/article/1368454][https_cloud.tencent.com_developer_article_1368454]

[https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md][https_github.com_julycoding_The-Art-Of-Programming-By-July_blob_master_ebook_zh_03.01.md]

[https://blog.csdn.net/silangquan/article/details/18655795?spm=a2c4e.11153940.blogcont297000.7.2b865734uYpB7n][https_blog.csdn.net_silangquan_article_details_18655795_spm_a2c4e.11153940.blogcont297000.7.2b865734uYpB7n]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70]: /images/20220201/d706135ef17b4112bec41bd1b122d622.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 1]: /images/20220201/b8a46be8b82a4d1dbf055f442da6a2f6.png
[http_t.cn_hgvH1l]: http://t.cn/hgvH1l
[red-black-tree]: /images/20220201/a2f4c8f5a46f4c54b33c910e55e3d8df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 2]: /images/20220201/3e7b238917ce4e699a669c2ac54a7f5f.png
[https_blog.csdn.net_qq_36610462_article_details_83277524]: https://blog.csdn.net/qq_36610462/article/details/83277524
[https_cloud.tencent.com_developer_article_1368454]: https://cloud.tencent.com/developer/article/1368454
[https_github.com_julycoding_The-Art-Of-Programming-By-July_blob_master_ebook_zh_03.01.md]: https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md
[https_blog.csdn.net_silangquan_article_details_18655795_spm_a2c4e.11153940.blogcont297000.7.2b865734uYpB7n]: https://blog.csdn.net/silangquan/article/details/18655795?spm=a2c4e.11153940.blogcont297000.7.2b865734uYpB7n