土法炼钢 · 系统与基础设施

红黑树 vs AVL：Linux 内核为什么选红黑树

2025-07-15 | algorithms | #red-black-tree #avl-tree #linux-kernel #balanced-bst #cfs #2-3-4-tree #llrb

AVL 树的平衡更严格、查找更快，为什么 Linux 内核、Java TreeMap、C++ std::map 全都选了红黑树？这个问题的答案不在教科书里——它藏在旋转次数的精确分析和 cache line 的物理约束中。