红黑树的基本知识

铺垫

在写之前我们先来点铺垫吧，就当是凑字数，练习打字了，搞起来。回忆一下你学的查找算法有哪些呢？总之我在之前虽然都知道，刷题时只是知道暴力破解...（小声逼逼：丢大家的脸了）。好了，那查找算法除了暴力破解（for 循环）外还有哪些呢？回忆一下大概有：二分查找、哈希、索引、B-Tree、B+Tree、BM 算法、KMP 之类的以及 bfs&dfs（图论中的遍历）等等....

在里面我们简单的二分、效率高的哈希。

敲重点：哈希的时间复杂度 O(1) 在 jdk1.7 中 Hashmap 采用链表 + 数组实现，其中链表引入为了解决 hash 冲突。在 1.8 中引入了红黑树，在 1.8 之前采用头插法会造成死循环，在 1.8 之后采用尾插法不会造成死循环。同时 HashMap 不是线程安全的可以使用 Collections.synchronizedMap(new HashMap(...));实现同步，同 HashTable 与 ConcurrentHashMap 属于线程安全、但是 hashtable 效率较差、基本不用。ConcurrentHashMap 效率较高。除此之外 1.8 的 HashMap 的性能高于 1.7 的性能（网友测试约 15%，在某些 size 区域更加高）。在 1.7 中，Hashmap 有两个重要的参数和三个构造函数，初始容量 16，默认负载因子 0.75，在 put 方法中元素大于等于 table 数组长度 x 负载因子的时候进行 2 的 n 次幂扩容。在 1.8 中当一个链表长度大于 8 的时候，HashMap 会动态的将它替换成一个红黑树（JDK1.8 引入红黑树大程度优化了 HashMap 的性能），这会将时间复杂度从 O(n)降为 O(logn)。

废话好像有点多了，接着说回来。

引入

在说红黑树之前，我们先来复习一个知识点。

二叉搜索树也就二叉查找树或者二叉排序树：

特点

• 如果左子树不为空，则左子树上的节点值都小于根节点
• 如果右子树不为空，则右子树上的节点值都大于根节点
• 子树也要遵顼以上两点规则

但是有没有想过这样的一个问题，要是插入的值依次变大或者变小，然后出现树退化的情况

（贪心算法可以构建哈夫曼树也就是最优二叉树构建不了二叉查找树和红黑树，但是哈夫曼树在某些特殊情况下也会出现单分支情况从而退化成链表。）

在没有退化之前我们查找的复杂度为 lgn，但是上图的情况时间复杂度就变为 n。出现这样算法要怎么办呢？

如何才能让其不退化为链表呢？

这时候出现 AVL 树（平衡二叉树的折中（追求极致平衡、立项状态）< 实际应用中很少有人写 >）以及红黑树**（底层是特殊的二叉查找树）**

红黑树特点：

上面说到红黑树底层是特殊的二叉查找树，所以二叉具有的特点他也得有，其次还有的特点为：

• 每个节点不是红色就是黑色
• 不可能有连在一起的红色节点
• 根节点都是黑色 root
• 每个红色节点的连个子节点都是黑色（叶子节点都是黑色：满足出度为 0，可近似平衡

先来看一个红黑树吧：

你看着上面这个难受，其实你平时看见的是这样的：

好了，图也看了，现在应该知道一下它的颜色是个什么回事。其实就是在二叉的基础上再每个点位增加了存储位表示红色或者黑色（0/1）。至于为什么要叫红黑树，好像是因为发明的那几个人，用马克笔画图，然而马克笔就是红色和黑色，所以就叫红黑树了。

接下来，我们要来学最重要的了：

红黑树的变换

改变颜色：红变黑、黑变红

左（右）旋：针对于点旋，但是点上面的子树也要跟着转

变颜色就不说了，先来简洁明了看看好多人都懵逼的旋转。

左旋：

再来看一个右旋：

旋转和颜色变换规则：所有插入的点默认为红色。

改变颜色：
当前节点的父亲是红色，且他的祖父（父亲的父亲）节点的另一个子节点（叔叔）为红色:

• 父节点设为黑色
• 叔叔节点设置为黑色
• 把祖父节点设置为红色
• 把指针定义到祖父节点，设为当前要操作的点的变换规则

左旋：
当前节点的父节点是红色，祖父节点的另一个子节点（叔叔节点）是黑色的时候，且当前节点是右子树，以父节点左旋。

右旋：

当前节点的父节点是红色，祖父节点的另一个子节点（叔叔节点）是黑色的时候，且当前节点是左子树，以父节点右旋。

• 把父节点变为黑色
• 把祖父节点变为红色
• 以祖父节点旋转

图解：

可能看着文字不理解，直接看图：

颜色变换：

左旋：

右旋：

再一起来看一下整个过程：

红黑树其他知识：

• 时间复杂度： O(lgn)
• 应用： 红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是 O(lgn)，效率非常之高。
  例如，Java 集合中的 TreeSet 和 TreeMap，C++ STL 中的 set、map，以及 Linux 虚拟内存的管理，都是通过红黑树去实现的。
• 定理：一棵含有 n 个节点的红黑树的高度至多为 2log(n+1).
• 黑色完美平衡：左子树和右子树的黑色节点层数相等，既任意一个节点到每个叶子节点的路径都包含数量相同的黑色节点则成红黑树的这种平衡为黑色完美平衡。