Cây AA trong C / C ++?

Cây AA trong khoa học máy tính được định nghĩa là một dạng cây cân bằng được thực hiện để lưu trữ và truy xuất dữ liệu có thứ tự một cách hiệu quả. Cây AA được coi là một biến thể của cây đỏ đen, một dạng cây tìm kiếm nhị phân hỗ trợ việc thêm và xóa các mục nhập hiệu quả. Trái ngược với cây đỏ-đen, các nút đỏ trên cây AA chỉ có thể được thêm vào dưới dạng con con bên phải, không có con bên trái. Kết quả của hoạt động này là mô phỏng cây 2-3 thay vì cây 2-3-4, điều này làm đơn giản hóa các hoạt động bảo trì. Các thuật toán duy trì cho một cây đỏ đen yêu cầu giả định hoặc xem xét bảy hình dạng khác nhau để cân bằng cây một cách hợp lý -

Trái ngược với cây đỏ-đen, cây AA chỉ yêu cầu giả định hoặc xem xét hai hình dạng do yêu cầu nghiêm ngặt là chỉ các liên kết đúng mới có thể có màu đỏ -

Xoay cân bằng

Trong khi cây đỏ-đen cần một bit siêu dữ liệu cân bằng cho mỗi nút (màu), cây AA cần O (log (log (N))) bit siêu dữ liệu trên mỗi nút, ở dạng số nguyên "cấp". Các bất biến dưới đây giữ nguyên cho cây AA -

• Mức của mỗi nút lá được coi là một.

• Cấp độ của mỗi con bên trái nhỏ hơn chính xác một cấp độ của cấp độ cha mẹ của nó.

• Cấp độ của mọi đứa trẻ bên phải bằng hoặc nhỏ hơn cấp độ của bố mẹ nó.

• Cấp độ của mỗi đứa cháu bên phải nhỏ hơn cấp độ của ông bà nội của nó.

• Mỗi nút của cấp cao hơn một đều có hai nút con.

Cân bằng lại cây AA về mặt thủ tục dễ dàng hơn hoặc đơn giản hơn nhiều so với việc cân bằng lại cây đỏ đen.

Trong trường hợp cây AA, chỉ cần hai phép toán riêng biệt để khôi phục số dư:"xiên" và "tách". Skew được coi như một vòng quay phải để thay thế một cây con bao gồm một liên kết ngang bên trái bằng một cây con bao gồm một liên kết ngang bên phải. Trong trường hợp Tách, nó là sự xoay trái và tăng cấp để thay thế một cây con bao gồm hai hoặc nhiều liên kết ngang phải liên tiếp bằng một cây chứa ít hơn hai liên kết ngang phải liên tiếp. Các phép toán, "xiên" và "tách", được giải thích bên dưới -

hàm lệch là

   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

chức năng chia nhỏ là

   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

Tách -