AA樹在C/C++中是什麼？

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

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

平衡旋轉

#紅黑樹每個節點需要一個平衡元資料位元（顏色） ，而AA樹每個節點需要O(log(log(N)))個元資料位，以整數「level」的形式。以下不變式適用於AA樹：

• 每個葉節點的層級被視為1。

• 每個左子節點的層級比其父節點小1。

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

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

• 等級大於1的每個節點都有兩個子節點。

重新平衡AA樹比重新平衡紅黑樹要簡單得多。

在AA樹中，只需要兩個不同的操作來恢復平衡：「skew」和「split」。 Skew被視為右旋，用右水平連結取代一個由左水平連結組成的子樹。在Split的情況下，是左旋和等級增加，用兩個或更多連續的右水平連結替換一個包含兩個較少連續的右水平連結的子樹。下面解釋了“skew”和“split”這兩個操作。

函數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

#function split is

的翻譯為：

函數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

分割-

以上是AA樹在C/C++中是什麼？的詳細內容。更多資訊請關注PHP中文網其他相關文章！