加權平衡樹

在電腦科學裏面，加權平衡樹（英語：Weight-balanced tree，縮寫：WBTs）是一種可以用來實現集合、字典（對映）和序列的平衡樹。這些樹結構在20世紀70年代被Nievergelt和Reingold作為有界限的自平衡樹或BB[α]樹提出。讓這些結構普及的是高德納。

就像其他自平衡樹一樣，加權平衡樹儲存的賬簿資訊可以在樹結構被插入和刪除操作打亂時，通過平衡結點和操作樹旋轉來使樹結構重新達到平衡。特別的地方是，加權平衡樹的每個結點儲存這個結點下子樹的大小，並且這個結點左右子樹的大小保持着某種內在聯絡。不同於AVL樹（儲存子樹的高度）和紅黑樹（儲存虛構的「顏色」位），加權平衡樹儲存記賬資訊的方式是對應用真正有用的屬性：一棵樹下元素的數量等於它的根的大小，然而這個根的大小是一個用來實現順序統計樹操作的有用數據，也就是說，可以得到一個大小為n的集合下的最大元素或者決定一個順序結構下一個元素的索引。

加權平衡樹在函數程式語言社區下面非常受歡迎以及被用來實現MIT Scheme的集合和對映結構還有Haskell語言的實現。

描述

加權平衡樹是一種儲存子樹大小的二叉搜尋樹。那就是說，一個結點包含以下欄位：

• 鍵（key），任何可排序的類型
• 值（value，可選，只作對映作用）
• 左子樹（left），右子樹（right），結點的指標
• 大小（size），整數類型

從定義上來說，樹上葉子（沒有子結點的元素）的大小（典型地用一個空指標表示）是0。一個內部結點的大小是它的兩棵子樹的大小，再加一 （size[n] = size[n.left] + size[n.right] + 1）。一個結點的權重取決於它的大小或者等於它的大小，或weight[n] = size[n] + 1。

樹旋轉

修改樹的操作必須使用與AVL樹中相同的操作來保證左子樹和右子樹的大小相互存在某種內在因子α，也就是旋轉和兩次選擇。形式上來說，結點平衡操作如下定義：

如果一個結點滿足weight[n.left] ≥ α·weight[n]以及weight[n.right] ≥ α·weight[n]，那麼就說這個結點是α加權平衡的。

在這裏，α是一個在實現加權平衡樹是用來做決定的數值參數。α的值越小，意味着這棵樹「更加平衡」，但不是所有的α值都是合適的；Nievergelt和Reingold曾經證明過滿足

$\alpha <1-{\frac {1}{\sqrt {2}}}$

是一個平衡演算法成功工作的重要狀態。他們往後的工作展示了α的一個下界是2⁄11，但如果使用一個自訂（更加複雜的）的再平衡演算法，下界還可以更小。

若平衡被正確實現，一棵含有n個元素的加權平衡樹的高度h滿足

$h\leq \log _{\frac {1}{1-\alpha }}n={\frac {\log _{2}n}{\log _{2}\left({\frac {1}{1-\alpha }}\right)}}=O(\log n)$

加權平衡樹n次插入和刪除操作中，平衡的次數是線性的，為n。也就是說，加權平衡樹的平衡操作均攤開銷是恆定的。