为什么不用 AVL 树作为底层实现？

那是因为 AVL 树是高度平衡的树, 而每一次对树的修改, 都要 rebalance, 这里的开销会比红黑树大. 红黑树插入只要两次旋转, 删除至多三次旋转. 但不可否认的是, AVL 树搜索的效率是非常稳定的. 选取红黑树, 我认为是一种折中的方案.
对AVL插一个node或者删一个node，显然不需要每次都做rotation来维持balance。且AVL插入最多也只需要2次旋转。
下面是我的回答：

如果插入一个node引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度。
其次，AVL的结构相较RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。
map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说，RB-tree的统计性能是高于AVL的。

一、特性

1.节点是红色或黑色。

2.根节点是黑色。

3.每个叶子节点都是黑色的空节点（NIL节点）。红黑树的叶子节点和我们平时在二叉树上使用的叶子节点的概念是不一样的。

4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树的5条特性确保了从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，使得整棵树大致上是平衡的。树上的增删改查操作的最坏情况时间都与树的高度成正比，所以红黑树在最坏情况下也是高效的。
为什么最长路径不能多余最短路径的两倍，因为任意节点到每一个叶子节点的黑色node个数是一样的，因此最长的路径也就是包含了很多的红色node，而红色node的子节点必须为黑色node，因此最长的情况也就是一个红色一个黑色，所以最长只能是最短的两倍。

二、红黑树介绍

红黑树例子

什么情况下会破坏红黑树的规则，什么情况下不会破坏规则呢？我们举两个简单的栗子：
1.向原红黑树插入值为14的新节点：

由于父节点15是黑色节点，因此这种情况并不会破坏红黑树的规则，无需做任何调整。

2.向原红黑树插入值为21的新节点：

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

2.1 变色：

为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。
下图所表示的是红黑树的一部分，需要注意节点25并非根节点。因为节点21和节点22连续出现了红色，不符合规则4，所以把节点22从红色变成黑色：

但这样并不算完，因为凭空多出的黑色节点打破了规则5，所以发生连锁反应，需要继续把节点25从黑色变成红色：

此时仍然没有结束，因为节点25和节点27又形成了两个连续的红色节点，需要继续把节点27从红色变成黑色：

2.2 左旋转

逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。说起来很怪异，大家看下图：

图中，身为右孩子的Y取代了X的位置，而X变成了自己的左孩子。此为左旋转。

2.3 右旋转

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

图中，身为左孩子的Y取代了X的位置，而X变成了自己的右孩子。此为右旋转。

三、红黑树是如何插入节点并保持平衡的？

首先，我们将插入的节点初始为红色（为了不违反第五条规则），并当做子节点按照二叉树的方法插入该节点。) 由于第四条规则规定（红色节点的子节点必须是黑色），所以我们根据被插入的父节点的不同情况分为以下三种情况来处理：
(1)父节点是根节点（root），把节点变成黑色？
(2)父节点是黑色节点，无需改变，插入后任是红黑树
(3)父节点是红色节点，特殊处理
下面专门讲解第三种情况

父节点为红色的调整：

这种情况下，父节点必然存在一个祖父节点（父节点的父节点），也一定存在叔叔节点（父节点的兄弟节点）。即使叔叔节点为空，我们也认定他存在，空节点算是一个黑色节点，当前父节点为红色，根据当前父节点的兄弟节点又分为以下三种情况：
RB Tree插入操作参考网站

情况1 ：当前节点的父节点是红色，且祖父节点的另一个子节点（叔叔节点）也是红色

此时，我们只考虑当前节点是父节点的左儿子，因为当前节点和父节点都是红色，不满足红黑树的特性4 （如果一个节点是红的，他的两个儿子节点都是黑的）。

对策 :把父节点和叔叔节点变黑，爷爷节点涂红，然后把当前节点指针给到爷爷，让爷爷节点那层继续循环，接受红黑树特性检测。

情况2：当前节点的父节点是红的，叔叔节点是黑的，当前节点是父节点的右子树。

对策：当前节点的父节点作为新的当前节点，以新当前指点为支点左旋

接着上面的情况1，在情况1的操作之后，当前节点为4，但是4的父节点3还是红的，仍然不满足红黑树的特性4，由于叔叔节点7是黑的，且4为3的右儿子，所以满足情况2，这时候把当前节点转移到3，以3为支点左旋。4变为爷爷5的新左儿子，而原来的3下去了，成为4的左儿子。4原有的左儿子（2-1分支）给3做了右儿子。

情况3：当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左儿子

对策：父节点变黑，祖父变红，以祖父节点为支点右旋

接着上面的情况2，当前节点变成了3，由于父节点4为红，叔叔节点7 为黑，且4为5的左儿子，所以满足情况3，所以需要将父节点4变黑，祖父5变红，并且右旋，右旋后，4 的右儿子6跟了5做了左儿子，5成了4的右儿子。如图所示：

红黑树（Red Black Tree）