红黑树

定义

红黑树是一种自平衡二叉搜索树，通过给节点染红或黑并遵守一组规则来保证树的近似平衡，从而让最长路径不超过最短路径的两倍。

原理

红黑树满足五条性质：节点非红即黑；根为黑；红节点的子节点必为黑（不能有连续红节点）；从任一节点到其所有叶子的路径包含相同数目的黑节点；叶子（空节点）为黑。插入删除后通过变色和旋转修复违反的性质。相比 AVL 树，红黑树平衡约束更宽松，旋转更少，增删更快，因此在工程中应用更广。

复杂度

• 查找：O(log n)
• 插入：O(log n)
• 删除：O(log n)
• 空间复杂度：O(n)

应用场景

• Java 的 TreeMap、TreeSet 与 HashMap 桶内树化
• C++ STL 的 map 与 set
• Linux 内核进程调度与内存管理