簡介
2-3樹
“2-3樹”是由Aho, Hopcroft和Ullman提出, 它是這樣的樹:在樹中每個結點都有2個或3個子樹, 而且從根到葉的每條路徑都是等長的;由單個節點組成的樹也是“2-3樹”。如圖《2-3樹》所示, 是具有六片葉子的“2-3樹”, 這裡每個葉結點存放一個關鍵字值, 每一個非葉結點存放兩個值, 這兩個值分别是第一個 (最左) 子樹中最大關鍵字值, 和該結點第二個 (中) 子樹最大關鍵字值。非葉結點這兩個值能從樹的根出發, 用類似于二分搜索的方式來搜索樹中某一元素。
通過對“2-3樹”的改造, 形成一種新的數據結構，即平衡樹 (BT) 。BT解決了“2-3樹”實現集合表示的存儲空間利用率低問題。同時可以實現求集合的并、交、差、測集合包含關系操作。
性質與基本算法
性質：高為h的BT, 其結點的數目在2^(h+1)-1和1/2(3^(h+1)−1)之間, 葉的數目在2^h和3^h之間。
證明：BT退化為每個結點 (非葉) 隻有兩棵子樹時, 結點的數目最少, 葉子也最少。設層号為i則各層結點數為2^(i-1)個, 那麼高為h的BT最大層号是j時, 有h=j-1。整個樹的結點數為s=2^0+2^1+2^2+…+2^h, 故s=2^(h+1)-1。其葉子的個數是2^h。同理, 當BT每個非葉結點都有三棵子數時, 結點數目最多。此時結點數為：
s=3^0+3^1+3^2+⋯+3^h‚s=1/2(3^(h+1)−1)，其葉子的個數是3^h。
中根遍曆算法:
中根遍曆的結果是:1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13。
先根遍曆算法：
先根遍曆的結果是:9, 3, 1, 2, 4, 7, 5, 6, 8, 12, 10, 11, 13。
後根遍曆算法：
後根遍曆的結果是:1, 2, 4, 3, 5, 6, 8, 7, 10, 11, 13, 12, 9。
應用
在智能電網中，與傳統路由協議不同，突發性擁塞不再是數據采集的主要風險，風險的新來源是數據流過度集中在網絡的關鍵節點而導緻的擁塞。為此,提出了一種能夠實現數據平衡的數據采集路由機制用以克服網絡擁塞。該機制抽象出配用通信網絡的數學模型;其次,針對無線網狀網絡(WMNs)路由協議,以節點排隊隊列長度作為決策參數建立路由度量模型(數據平衡度量模型,DBMM),并以度量值最小作為決策條件,設計了基于平衡樹的路由算法(基于DBMM的路由算法,RA-DBMM)。有效地改善數據擁塞問題,提高系統可靠性和吞吐量。
