複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/平衡樹/7641279
複製
複製成功

平衡樹

鎖定
平衡樹(Balance Tree，BT) 指的是，任意節點的子樹的高度差都小於等於1。常見的符合平衡樹的有，B樹（多路平衡搜索樹）、AVL樹（二叉平衡搜索樹）等。平衡樹可以完成集合的一系列操作, 時間複雜度和空間複雜度相對於“2-3樹”要低，在完成集合的一系列操作中始終保持平衡，為大型數據庫的組織、索引提供了一條新的途徑。 [1] 
設“2-3 樹”的每個結點存放一組與應用問題有關的數據, 且有一個關鍵字 (>0的整數) 作為標識。關鍵字的存放規則如下:對於結點X, 設左、中、右子樹均不空, 則左子樹任一結點的關鍵字小於中子樹中任一結點的關鍵字;中子樹中任一結點的關鍵字小於結點X的關鍵字;而X的關鍵字又小於右子樹中任一結點的關鍵字, 稱這樣的“2-3樹”為平衡樹。 [1] 
中文名
平衡樹
外文名
Balance Tree，BT [1] 
提    升
存儲空間利用率 [1] 
領    域
通信
由    來
對“2-3樹”的改造 [1] 

目錄

  1. 1 簡介
  2. 2 性質與基本算法
  3. 3 應用

平衡樹簡介

2-3樹 2-3樹
“2-3樹”是由Aho, Hopcroft和Ullman提出, 它是這樣的樹:在樹中每個結點都有2個或3個子樹, 而且從根到葉的每條路徑都是等長的;由單個節點組成的樹也是“2-3樹”。如圖《2-3樹》所示, 是具有六片葉子的“2-3樹”, 這裏每個葉結點存放一個關鍵字值, 每一個非葉結點存放兩個值, 這兩個值分別是第一個 (最左) 子樹中最大關鍵字值, 和該結點第二個 (中) 子樹最大關鍵字值。非葉結點這兩個值能從樹的根出發, 用類似於二分搜索的方式來搜索樹中某一元素。 [1] 
通過對“2-3樹”的改造, 形成一種新的數據結構，即平衡樹 (BT) 。BT解決了“2-3樹”實現集合表示的存儲空間利用率低問題。同時可以實現求集合的並、交、差、測集合包含關係操作。 [1] 

平衡樹性質與基本算法

性質：高為h的BT, 其結點的數目在2^(h+1)-1和1/2(3^(h+1)−1)之間, 葉的數目在2^h和3^h之間。 [2] 
證明：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每個非葉結點都有三棵子數時, 結點數目最多。此時結點數為： [2] 
s=3^0+3^1+3^2+⋯+3^h‚s=1/2(3^(h+1)−1)，其葉子的個數是3^h。 [2] 
中根遍歷算法:
中根歷遍算法 中根歷遍算法
中根遍歷的結果是:1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13。 [2] 
先根歷遍算法 先根歷遍算法
先根遍歷算法：
先根遍歷的結果是:9, 3, 1, 2, 4, 7, 5, 6, 8, 12, 10, 11, 13。 [2] 
後根遍歷算法：
後根歷遍算法 後根歷遍算法
後根遍歷的結果是:1, 2, 4, 3, 5, 6, 8, 7, 10, 11, 13, 12, 9。 [2] 

平衡樹應用

在智能電網中，與傳統路由協議不同，突發性擁塞不再是數據採集的主要風險，風險的新來源是數據流過度集中在網絡的關鍵節點而導致的擁塞。為此,提出了一種能夠實現數據平衡的數據採集路由機制用以克服網絡擁塞。該機制抽象出配用通信網絡的數學模型;其次,針對無線網狀網絡(WMNs)路由協議,以節點排隊隊列長度作為決策參數建立路由度量模型(數據平衡度量模型,DBMM),並以度量值最小作為決策條件,設計了基於平衡樹的路由算法(基於DBMM的路由算法,RA-DBMM)。有效地改善數據擁塞問題,提高系統可靠性和吞吐量。 [3] 
參考資料