红黑树（RBT）基础：5条性质与AVL树对比
红黑树这东西，我第一次接触是在做数据库索引优化的时候。当时项目里用的是一棵AVL树，数据量一上来，频繁的插入删除操作让AVL树不停地旋转，性能肉眼可见地往下掉。后来我换成了红黑树，嗯，世界清净了。
说白了，红黑树是一种自平衡的二叉查找树。它不像AVL树那样追求「绝对平衡」，而是追求一种「近似平衡」。这种设计让它在插入和删除时，旋转次数大大减少，性能更稳定。
红黑树的5条性质
红黑树的每个节点都有一个颜色属性，要么红，要么黑。这5条性质，我建议你背下来，面试常考，实际写代码时也经常要对照着检查。
- 每个节点要么是红色，要么是黑色。 嗯，这是废话，但确实是第一条。
- 根节点是黑色的。 这个好记，根不能是红的。
- 所有叶子节点（NIL）都是黑色的。 这里的叶子节点指的是空节点，不是我们通常说的叶子。
- 红色节点的两个子节点必须是黑色的。 换句话说，不能有两个连续的红色节点。你想想看，如果红节点下面又接红节点，那树就乱套了。
- 从任意节点到其每个叶子节点的所有路径上，黑色节点的数量相同。 这个性质叫「黑高相等」，是红黑树平衡的关键。
核心理解： 第4条和第5条性质共同保证了红黑树的高度不超过 2log₂(n+1)。为什么？因为最短路径全是黑节点，最长路径是红黑交替，长度最多是两倍。所以查找时间复杂度是 O(log n)。
红黑树的结构示意图
我画了一张图，帮你直观理解红黑树的节点结构和5条性质的关系。你看，根是黑的，红节点下面不能有红节点，每条路径的黑节点数量都一样。
我的小技巧： 判断一棵树是不是红黑树，你只需要检查两条：一是有没有连续的红节点，二是从根到每个NIL的黑节点数是否一样。这两条过了，基本就没问题。
红黑树与AVL树的对比
很多初学者会问：有了AVL树，为什么还要红黑树？我当年也有这个疑问。后来在项目中踩过坑才明白，两者各有各的适用场景。
| 对比维度 | 红黑树（RBT） | AVL树 |
|---|---|---|
| 平衡标准 | 近似平衡（黑高相等） | 严格平衡（左右子树高度差≤1） |
| 查找性能 | O(log n)，略慢于AVL | O(log n)，更快 |
| 插入/删除性能 | O(log n)，旋转次数少（平均2-3次） | O(log n)，旋转次数多（可能O(log n)次） |
| 空间开销 | 每个节点多1bit颜色信息 | 每个节点多1-2bit平衡因子 |
| 适用场景 | 插入删除频繁的场景（如Linux内核、STL map） | 查找远多于修改的场景（如数据库索引） |
你看这个表格就清楚了。AVL树查找更快，因为它更平衡。但红黑树在插入删除时更省事，因为它允许一定程度的不平衡。
我曾经踩过的坑： 有一次我在一个高频交易系统里用了AVL树做订单簿。每次订单进来都要插入，AVL树频繁旋转，导致延迟飙升。后来换成红黑树，延迟直接降了40%。所以选哪个，得看你的业务场景是读多写少还是写多读少。
为什么红黑树在实际中更受欢迎？
说白了，真实世界的程序，插入删除操作往往比查找更频繁。你想想看，一个Web服务器的请求队列，数据不断进出，AVL树那种「强迫症」式的平衡反而成了负担。
红黑树的设计哲学是：我不追求完美，但我保证不差。 它的高度最多是2log₂(n+1)，查找性能虽然比AVL树差一点点，但插入删除的代价小得多。这种「够用就好」的思路，在实际工程中非常实用。
我个人的习惯是：如果项目对查找性能要求极高，且数据基本不变，我会用AVL树。但如果数据是动态的，频繁增删，我无脑选红黑树。
红黑树的应用场景
- Linux内核的完全公平调度器（CFS）：用红黑树管理进程，每次调度都要插入和删除，红黑树扛得住。
- C++ STL中的map和set：底层就是红黑树。你想想看，STL要兼顾各种使用场景，红黑树是最稳妥的选择。
- Java中的TreeMap和TreeSet：同样是红黑树。Java的HashMap在哈希冲突严重时也会转成红黑树。
- Nginx的定时器管理：用红黑树管理定时事件，插入删除频繁，红黑树正合适。
避坑指南： 如果你自己实现红黑树，一定要注意插入和删除后的修复操作。我曾经在修复时漏掉了一个case，导致树结构被破坏，查了两天才找到bug。建议你先把5条性质写在纸上，每步操作都对照检查。
好了，红黑树的基础就讲到这里。记住那5条性质，理解它和AVL树的区别，后面我们再看红黑树的插入和删除操作，你就会觉得顺理成章了。
公众号:蓝海资料掘金营，微信deep3321