红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找树，即没办法保证任意一个节点左右子树高度相差不超过 1。

• 红黑树中利用一个bit 来表示是红色还是黑色;
• 根节点是黑色的；
• 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
• 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
• 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

红黑数的时间复杂度推导

如上图，对一个红黑树，如果我们将红色节点从红黑树中去掉，有些节点就没有父节点了，它们会直接拿这些节点的祖父节点（父节点的父节点）作为父节点。所以，之前的二叉树就变成了 N 叉树。

而红黑树的定义里有这么一条：从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点。我们从 N 叉树中取出某些节点，放到叶节点位置，N 叉树就变成了完全二叉树。所以，仅包含黑色节点的 N 叉树的高度，比包含相同节点个数的完全二叉树的高度还要小。

完全二叉树的高度近似 log2n，这里的 N 叉“黑树”的高度要低于完全二叉树，所以去掉红色节点的“黑树”的高度也不会超过 log2n。

然后我们再把红色节点加回去。由于红色节点不能相邻，也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开。红黑树中包含最多黑色节点的路径不会超过 log2n，所以加入红色节点之后，最长路径不会超过 2log2n，也就是说，红黑树的高度近似 2log2n。

所以，红黑树的高度只比高度平衡的 AVL 树的高度（log2n）仅仅大了一倍，在性能上，下降得并不多。

<aside> 💡 在实际工程中，由于 AVL 树对于插入、删除要频繁的维护树，所以 AVL 实际性能不如红黑树。

</aside>

左旋与右旋

插入的平衡调整

<aside> 💡 红黑数由 2-3 树推导而来。可以看《算法》

</aside>