5.rbtree與234樹(2)
在rbtree中,所描述的屬性是顏色,運(yùn)用顏色特征來保障rbtree樹的平衡。在234樹中所描述的屬性的構(gòu)型(2,3,4節(jié)點(diǎn)構(gòu)型),運(yùn)用構(gòu)型的特征來保障234樹的平衡。在之前一節(jié)中討論過了234樹在其構(gòu)型的策略上有一個(gè)是構(gòu)型視圖的中央永遠(yuǎn)是根部的構(gòu)造方法。在這里將接上之前的討論,從234樹的構(gòu)型屬性及其平衡的概念的討論以邁步向rbtree為目標(biāo)。
什么是平衡?拋開當(dāng)下關(guān)于樹的所有問題不要談,構(gòu)成平衡狀態(tài)的要素是什么?在這個(gè)方面上,如果適當(dāng)借助一些生活實(shí)踐并從中提取出抽象的要素的話,我覺得有一種類型的平衡是由一個(gè)支點(diǎn)和一條準(zhǔn)直的線段構(gòu)成。
可以觀察身邊的用于度量平衡關(guān)系的手秤砣,其中手指抵住砣桿,塑造一個(gè)支點(diǎn);當(dāng)測量物與定標(biāo)物重量在豎直方向上大小一致,兩側(cè)的連線將呈一條準(zhǔn)直的水平線段。而如果測量與標(biāo)定是等重量的,平衡時(shí)支點(diǎn)則會(huì)恰巧位于線段的中垂線上。

而對于在樹的平衡討論中,如果樹的每個(gè)節(jié)點(diǎn)都是等權(quán)重(同樣重要)的,那么就像等重量平衡是一樣,支點(diǎn)與準(zhǔn)直線的關(guān)系滿足:支點(diǎn)位于準(zhǔn)直線的中垂線上:

而如果進(jìn)一步拆分線的構(gòu)成,會(huì)得到線由點(diǎn)構(gòu)成。而具體到在234樹中,點(diǎn)是234樹的2,3,4節(jié)點(diǎn)組成的集合。那么如果在有一個(gè)中心支點(diǎn)的前提下要保障從支點(diǎn)出發(fā)中間切一刀(連接中點(diǎn))做截線,左右兩側(cè)的點(diǎn)數(shù)量均勻平衡(兩邊面積仍一致),還需要加上另一種要素約束出一種平衡的條件就是:
過支點(diǎn)做準(zhǔn)直線(如果是曲線,則取該點(diǎn)切線)的平行線,準(zhǔn)直線上所有點(diǎn)到過支點(diǎn)的該直線在垂線方向上的距離是等高的。如果不滿足這個(gè)平衡條件,那么就像表現(xiàn)為這樣:

那這就像隨機(jī)印花的碎花裙一樣,缺乏一種對稱與平衡(雖然它也能很美觀,也能賣得很好。但是不在234樹的美學(xué)討論之內(nèi)) 。
而由此平衡條件帶入到點(diǎn)是234樹基本構(gòu)型組成的集合中,設(shè)每個(gè)基本構(gòu)型都具備1個(gè)單位的"點(diǎn)高度",那么,由支點(diǎn)出發(fā),到達(dá)底部的任意一個(gè)層級(jí)(甚至也可以具體是最基層)時(shí),若任意二叉分支路徑所經(jīng)歷的”點(diǎn)高度“累計(jì)都相等,則這種按234樹規(guī)則衍生的二叉樹,在234樹討論的概念范圍里對應(yīng)為平衡二叉樹。
rbtree中也有一個(gè)相似的由支點(diǎn)遍歷二叉樹路徑的一個(gè)計(jì)數(shù)守恒:
5)從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。
而要解釋好它,就需要準(zhǔn)備好由rbtree顏色屬性到234樹構(gòu)型屬性的變換規(guī)則。這樣經(jīng)過一層層的拆解,一些問題已經(jīng)慢慢變得得心應(yīng)手了,具體的內(nèi)容那就下回見分曉吧。