# 什么是红黑树？

By [qiannuo社区](https://paragraph.com/@qiannuo) · 2021-10-08

---

红黑树 是 1972 年发明的，称为对称二叉 B 树，1978 年正式命名红黑树。主要特征是在每个节点上增加一个属性表示节点颜色，可以红色或黑色。红黑树和 AVL 树 类似，都是在进行插入和删除时通过旋转保持自身平衡，从而获得较高的查找性能。与 AVL 树 相比，红黑树不追求所有递归子树的高度差不超过 1，保证从根节点到叶尾的最长路径不超过最短路径的 2 倍，所以最差时间复杂度是 O(logn)。红黑树通过重新着色和左右旋转，更加高效地完成了插入和删除之后的自平衡调整。

红黑树在本质上还是二叉查找树，它额外引入了 5 个约束条件： ① 节点只能是红色或黑色。 ② 根节点必须是黑色。 ③ 所有 NIL 节点都是黑色的。 ④ 一条路径上不能出现相邻的两个红色节点。 ⑤ 在任何递归子树中，根节点到叶子节点的所有路径上包含相同数目的黑色节点。

这五个约束条件保证了红黑树的新增、删除、查找的最坏时间复杂度均为 O(logn)。如果一个树的左子节点或右子节点不存在，则均认定为黑色。红黑树的任何旋转在 3 次之内均可完成。

---

*Originally published on [qiannuo社区](https://paragraph.com/@qiannuo/XGHhImq0v5nDYQSoZbe9)*