红黑树与 AVL：旋转次数、树高与 Linux 内核的选择
用可复现的计数实验（红黑树部分与 Linux v6.12 lib/rbtree.c 逐操作一致）比较 AVL、红黑树与左倾红黑树的树高、旋转、平衡标记写入和比较次数：AVL 与红黑树平均差距很小，差在删除的最坏情形；并核对内核从 AVL 换到红黑树、再把 VMA 交给 maple tree 的史实。
maple-tree 标签归档
共 2 篇文章 · 返回首页
【操作系统百科】mm_struct 与 VMA
进程地址空间在内核里靠 mm_struct + VMA 链表/树描述。本文讲 mm_struct 核心字段、VMA 从红黑树到 maple tree 的改造、anon_vma 反向映射、mmap_lock 争抢。