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

红黑树与 AVL：旋转次数、树高与 Linux 内核的选择

2025-07-15 | algorithms | #red-black-tree #avl-tree #llrb #wavl #2-3-4-tree #tree-rotation #linux-rbtree #augmented-rbtree #rb-root-cached #maple-tree

用可复现的计数实验（红黑树部分与 Linux v6.12 lib/rbtree.c 逐操作一致）比较 AVL、红黑树与左倾红黑树的树高、旋转、平衡标记写入和比较次数：AVL 与红黑树平均差距很小，差在删除的最坏情形；并核对内核从 AVL 换到红黑树、再把 VMA 交给 maple tree 的史实。