平衡树在平衡什么

平衡树在平衡什么
隔壁老康难度 ★★★★☆ · 前置:二叉搜索树:理想很均衡,现实很歪 | 一句话结论:平衡树不是让树更矮,是给最坏情况买保险,代价是每次插入多转几圈。
两个计数器我打印在同一张纸上。顺序插入一万个 key,AVL 的树高 14、转了 9986 次,红黑树也是 14 层、转了 9987 次。差一次。
我以为自己抄错了行。
这两份实现是七月底写的。AVL 那边每个节点多存一个 int 高度,红黑树照 CLRS 抄,颜色单独放一位。计数器放在 rotateLeft 和 rotateRight 的入口,单旋记一次,双旋记两次。跑之前我的预期很明确:红黑树的标准松,松就该少转,顺序插入这种最坏情况更该是它赢。
结果是一比一。
朴素 BST 那一行更难看,树高 10000,转 0 次,一条右斜链,跟上一篇里那棵一模一样。三个数并排放,才看得清平衡树在干什么。它没有把树变矮,它把高度从一个由输入顺序决定的随机量,变成了一个有上界的确定量。一万个 key 顺序进来,朴素 BST 的高度是一万,这个数跟对数没有任何关系;AVL 和红黑树都是 14,log₂(10001) 是 13.29,向上取整正好 14,一步不差。价钱写在第三列,九千九百多次旋转,平均每插一个就要转一次。我上个月写 BST 那篇的时候把顺序插入叫最坏情况,现在看,它对平衡树来说也是最坏情况,工作量同样是按最坏那一档收的。
旋转是唯一一种不破坏有序的改形
旋转的图教科书上都画过,我第一次看的时候没抓住重点。左旋把右孩子提上来,原来的根降成它的左孩子,中间那棵子树挂到降下去那个节点的右边。三个指针换位,别的地方不动。
重点在后半句。
中序打出来还是原来那串数。我在纸上验过,3、5、7 按顺序插进去,左旋之后打印,还是 3、5、7。为什么不变,理由很朴素,旋转动的是父子关系,不是大小关系。被挪走的那棵子树里的 key,本来夹在两个节点之间,挪完还夹在中间。所以旋转是 BST 上唯一一种既改了形状、又不破坏查找性质的操作,平衡树的所有花样,归根到底都是在挑一个位置转一下。反过来读也成立:一个操作只要会破坏有序性,平衡树就不能靠它。
所以只能转。
1 | func (t *tree) rotateLeft(x *node) *node { |
这是纯 BST 的三条赋值,父指针和颜色我都省了。没有分配,没有搬运,一次旋转就是三个指针加一个计数器。数组中间插一个元素要挪一整片内存,这边一格都不挪。单次便宜,贵的是频次。
高度差压到一,靠的是插完回头看一眼
AVL 的规矩只有一句:任何节点,左右两棵子树的高度差不超过一。插入是先挂到叶子位置,挂完从它往根走,一路更新高度,遇到第一个不满足这条规矩的节点就转。转完那棵子树的高度回到插入前的值,上面的祖先不用再管,一次插入最多一组旋转,这就是收工的条件。顺序插入一万个 key 的时候,几乎每一步都会把某条路径压长一格,所以几乎每一步都在转,9986 这个数就是这么攒出来的。
它转出来的结果,恰好是最理想的形状。
14 层,log₂(10001) 也是 14 层,AVL 顺序插入长出来的就是一棵几乎填满的树,只有最后一层不满。这不是巧合,是那条规矩逼出来的:哪一层的节点缺得多了,上面就一定有节点两侧差超过一,就一定得转。
所以那 9986 次买的是一个上界。
顺便把教科书上的上界摆出来。AVL 的树高不超过 1.44·log₂(n+2)−0.328,一万个 key 代进去是十八点八,实测 14。上界是对所有 AVL 形状取最坏,我这组输入恰好落在最好的一头。写东西的时候容易把 14 当成 AVL 的常态,它不是,它是顺序插入这个特例的常态,随机插入那组里它变成了 20。
红黑树把标准放宽到两倍,实测只用了 1.08
红黑树的规矩不谈高度,谈颜色。根是黑的,红节点的两个孩子必须是黑的,从任意节点往下走到空指针,路上经过的黑节点个数都一样。三条合起来能推出一个结论:最长的路径不会超过最短路径的两倍,因为红节点不挨红节点,两条路的黑节点数又相等。所以它的高度上界是 2·log₂(n+1),一万个 key 是二十六层多。
实测的比值是 1.08。
最深 14 层,最浅 13 层,黑高 13。它离那个两倍的上界远得很,一万个 key 只差一层。中序遍历打出来前十个是 1 到 10,有序性没丢。
两倍是保证,不是日常。
这两个数各有各的用处。按两倍去估查询代价会估高,按 1.08 去估,别人递给你一段刁钻数据的时候会翻车。上界回答最坏能坏到哪,实测回答通常好到什么程度,混着用就出事。回到标题上那半句话:平衡树在平衡什么。AVL 平衡的是高度,规矩直接压在左右子树的高度差上;红黑树平衡的不是高度,是每条路径上的黑节点个数,高度只是被这个约束推出来的一个结果。两种平衡管的东西不一样,代价也就不一样。AVL 那条更紧,所以它必须更勤快地转;红黑树那条更松,所以它允许自己歪一点,把省下来的余量花在别处。
随机插十万,红黑树转了两倍半
顺序插入这组打完,我又跑了一组随机插入,十万个 key,先洗牌再插,两棵树各建一次。
| 结构 | 树高 | 旋转次数 | 理论下界 |
|---|---|---|---|
| AVL | 20 | 46374 | 17 |
| 红黑树 | 22 | 118813 | 17 |
红黑树转的次数是 AVL 的 2.6 倍,树还高两层。这个结果跟我预期完全相反。我原以为松的标准意味着维护动作更少,事实是它的修正在随机树里更常撞上要转的那一支。AVL 那边 46% 的插入会触发一次旋转,一次插入最多一组,总数就是四万六,跟我估的差不多;红黑树那边平均每次插入要转 1.19 次,等于大部分插入都碰到了要转的分支。
我先怀疑的是计数器。
第一版我把双旋只记了一次,AVL 那边先跑出来是三万出头,跟这张表里的 46374 差了一截。同事路过看了一眼,说你把双旋当单旋记了。改完重跑,两个数才对齐。这件事让我后来每次贴基准数字都把口径写在表底下:单旋记一次,双旋记两次,颜色翻转不算旋转。口径一变,结论就跟着变,所以这两个数只能说明我这两份实现各自干了多少活,不能拿它给红黑树这个家族定罪,换一份自顶向下的写法,这两列数字都会动。
真正分得开的是别的东西。
账单上还有几样东西没被数进去
AVL 转得少,可它每次插入都要沿着新叶子到根的那条路把高度重写一遍,转不转都得写,一层一个 int。二十层就是二十次写,全发生在刚刚走过的那条路上。红黑树这边每个节点只存一位颜色,修正过程走到哪染到哪,最多再转两次就停。这两笔账没法塞进同一个计数器,可它们都落在插入路径上,都得付。
删除那笔更大。
AVL 删一个节点,可能沿路径连着转好几次,最坏到 O(log n);红黑树的删除最多三次旋转。业务里删除不稀有,会话过期、缓存淘汰、索引重建,都是删。纯读的场合 AVL 的矮还能站住,读写混在一起、还得经常删的场合,它就不划算了。
这是我那组数没量到的地方。
基准只数了树高和旋转,没测查找耗时。拿 20 和 22 去推查询差多少是耍赖,多出来的两层值多少,得看节点多大、key 怎么分布、缓存里还剩多少,这三样我一个都没控制。能说的只有一句:高度差两层的代价在比较次数上数得清,在时钟上我手上没有数据。这话说出来不体面,可总比我编一个百分比强。
工程里选红黑树,选的是维护成本
标准库里能见到的有序容器基本是红黑树。C++ 的 map 和 set,Java 的 TreeMap,Linux 内核的 rbtree,nginx 的定时器,epoll 用它管 fd,Java 8 之后 HashMap 树化也是它。这些地方的共同点不是读多,是写也不少,还得长期跑着不出岔子。红黑树的标准松,换来的是每次写要维护的状态少、删除路径短、修正过程的传播距离有界。树高多两层,在这个场合是可以接受的代价。
AVL 不是不好,是场合换了。
建完就不动的索引、纯读的配置表、离线算好再查的东西,AVL 的矮是实打实的好处。我做过一个把配置读进内存按前缀查的小工具,建完一次查一年,那种场合我可以只要矮。但凡它要边跑边增删,我就往红黑树那边偏。
还有一个更现实的原因。
红黑树的标准是局部的,一个节点对不对,看它自己和它的两个孩子就够,出问题能定位到具体某一处。AVL 的高度是全局量,错一位,上面每一层的判断跟着错,而且它不报错,只是慢慢长歪。这是我最怕的一类错,不崩,也不慢得离谱,就是比该有的样子差一点。红黑树也会写错,但它的错更容易当场抓住。
顺便说一句 Go。动笔之前我去标准库里翻了一圈,map 是哈希表,container 下面只有 list 和 heap,前者是双向链表,后者是大顶堆,sort 用的是快排加堆排,一棵有序树都没有。想按 key 有序遍历,要么自己写,要么引第三方。这事说不上谁对谁错,它就是提醒我,容器选型从来不是只看渐近复杂度,还得看这门语言愿不愿意替它付维护代价。我上面举的那串名字全在 C 加加、Java 和内核里,不在 Go 里,不是巧合。
第一句问的是删不删
入职那年那个按时间戳建索引的小工具,当时我最后选的是插入前洗牌,用随机性换平均形状,最坏情况没人兜底。这次我把它翻出来换成红黑树,建完之后打印树高和黑高,两个数对得上才算建对。
旋转次数我没再打。
它是过程噪音,跑一次一个样,还跟计数口径绑在一起。留下的两个数是结果:树高告诉我最坏要走几步,黑高告诉我这棵树有没有按规矩长。
选型我现在只问三句。这份数据删不删,删得多就往红黑树那边走,删得少两家都行。读完还写不写,只读的可以挑矮的,读写混的别为两层高度去背一个全局状态。第三句是标准库里已经有的别自己写,我这两份实现是为了把旋转次数数清楚,不是为了替换谁。
数清楚了,就该用别人写好的。
现在每次建完一棵平衡树,我第一件事还是打印树高,红黑树再加一个黑高。这两个数对了,后面那些 O(log n) 才算数;不对的话,写多少行代码都是在给一个歪掉的形状做优化。
我后来把这条写进了那份组里的库代码注释:如果压测时发现旋转次数比插入次数还多,先别怀疑实现,先把输入的顺序打出来看一遍。












