C/C++ 中的 AA 樹？

在計算機科學中，AA 樹被定義為一種平衡樹，用於高效地儲存和檢索有序資料。AA 樹被認為是紅黑樹的一種變體，紅黑樹是一種支援高效新增和刪除條目的二叉搜尋樹。與紅黑樹不同的是，AA 樹上的紅色節點只能作為右子節點新增，不能作為左子節點新增。此操作的結果是模擬 2-3 樹而不是 2-3-4 樹，這簡化了維護操作。紅黑樹的維護演算法需要假設或考慮七種不同的形狀才能正確地平衡樹。

與紅黑樹相反，AA 樹只需要假設或考慮兩種形狀，因為只有右連結可以是紅色的。

平衡旋轉

紅黑樹每個節點需要一位平衡元資料（顏色），而 AA 樹每個節點需要 O(log(log(N))) 位元資料，以整數“級別”的形式表示。AA 樹具有以下不變性：

• 每個葉子節點的級別都被視為 1。

• 每個左子節點的級別正好比其父節點的級別小 1。

• 每個右子節點的級別等於或比其父節點的級別小 1。

• 每個右孫子節點的級別嚴格小於其祖父節點的級別。

• 每個級別高於 1 的節點都有兩個子節點。

重新平衡 AA 樹在程式上比重新平衡紅黑樹容易得多。

對於 AA 樹，只需要兩種不同的操作來恢復平衡：“傾斜”和“分裂”。“傾斜”被視為右旋轉，以用由右水平連結組成的子樹替換由左水平連結組成的子樹。對於“分裂”，它是一個左旋轉和級別增加，以用包含少兩個連續右水平連結的子樹替換包含兩個或多個連續右水平連結的子樹。“傾斜”和“分裂”操作解釋如下：

skew 函式是

   input: An AA tree that needs to be rebalanced is represented by a node, t.
   output: The rebalanced AA tree is represented by another node.
if nil(t) then
return nil
else if nil(left(t)) then
return t
else if level(left(t)) == level(t) then
   Exchange the pointers of horizontal left links.
   l = left(t)
left(t) := right(l)
right(l) := t
return l
else
return t
end if
end function

split 函式是

   input: An AA tree that needs to be rebalanced is represented by a node, t.
   output: The rebalanced AA tree is represented by another node.
if nil(t) then
return nil
else if nil(right(t)) or nil(right(right(t))) then
return t
else if level(t) == level(right(right(t))) then
We have two horizontal right links. The middle node is taken, elevate it, and return it.
      r = right(t)
right(t) := left(r)
left(r) := t
level(r) := level(r) + 1
return r
else
return t
end if
end function

分裂 -

Arnab Chakraborty

更新於：2020年1月29日

1K+ 瀏覽量

開啟您的職業生涯

完成課程獲得認證

開始學習