土法炼钢兴趣小组的算法知识备份

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

2026-04-17 | algorithms | #red-black-tree #avl-tree #linux-kernel #balanced-bst #cfs

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