5.rbtree与234树(2)
在rbtree中,所描述的属性是颜色,运用颜色特征来保障rbtree树的平衡。在234树中所描述的属性的构型(2,3,4节点构型),运用构型的特征来保障234树的平衡。在之前一节中讨论过了234树在其构型的策略上有一个是构型视图的中央永远是根部的构造方法。在这里将接上之前的讨论,从234树的构型属性及其平衡的概念的讨论以迈步向rbtree为目标。
什么是平衡?抛开当下关于树的所有问题不要谈,构成平衡状态的要素是什么?在这个方面上,如果适当借助一些生活实践并从中提取出抽象的要素的话,我觉得有一种类型的平衡是由一个支点和一条准直的线段构成。
可以观察身边的用于度量平衡关系的手秤砣,其中手指抵住砣杆,塑造一个支点;当测量物与定标物重量在竖直方向上大小一致,两侧的连线将呈一条准直的水平线段。而如果测量与标定是等重量的,平衡时支点则会恰巧位于线段的中垂线上。

而对于在树的平衡讨论中,如果树的每个节点都是等权重(同样重要)的,那么就像等重量平衡是一样,支点与准直线的关系满足:支点位于准直线的中垂线上:

而如果进一步拆分线的构成,会得到线由点构成。而具体到在234树中,点是234树的2,3,4节点组成的集合。那么如果在有一个中心支点的前提下要保障从支点出发中间切一刀(连接中点)做截线,左右两侧的点数量均匀平衡(两边面积仍一致),还需要加上另一种要素约束出一种平衡的条件就是:
过支点做准直线(如果是曲线,则取该点切线)的平行线,准直线上所有点到过支点的该直线在垂线方向上的距离是等高的。如果不满足这个平衡条件,那么就像表现为这样:

那这就像随机印花的碎花裙一样,缺乏一种对称与平衡(虽然它也能很美观,也能卖得很好。但是不在234树的美学讨论之内) 。
而由此平衡条件带入到点是234树基本构型组成的集合中,设每个基本构型都具备1个单位的"点高度",那么,由支点出发,到达底部的任意一个层级(甚至也可以具体是最基层)时,若任意二叉分支路径所经历的”点高度“累计都相等,则这种按234树规则衍生的二叉树,在234树讨论的概念范围里对应为平衡二叉树。
rbtree中也有一个相似的由支点遍历二叉树路径的一个计数守恒:
5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
而要解释好它,就需要准备好由rbtree颜色属性到234树构型属性的变换规则。这样经过一层层的拆解,一些问题已经慢慢变得得心应手了,具体的内容那就下回见分晓吧。