AA tree ใน computer science นิยามว่าเป็นรูปแบบของ balanced tree ใช้เก็บและ retrieve ordered data อย่างมีประสิทธิภาพ AA trees เป็น variation ของ red-black tree ซึ่งเป็น binary search tree ที่รองรับ efficient addition และ deletion of entries ต่างจาก red-black trees red nodes บน AA tree สามารถเพิ่มได้เฉพาะเป็น right subchild ไม่มี left subchild ผลลัพธ์คือ simulation ของ 2-3 tree แทน 2-3-4 tree ทำให้ maintenance operations ง่ายขึ้น Maintenance algorithms สำหรับ red-black tree ต้อง consider 7 รูปทรงต่างๆ เพื่อ balance tree −
ตรงข้ามกับ red-black tree AA tree ต้อง consider แค่ 2 รูปทรง เนื่องจากข้อกำหนดเข้มงวดว่า right links เท่านั้นที่เป็น red −
Balancing rotations
ในขณะที่ red-black trees ต้องการ 1 bit balancing metadata ต่อ node (color) AA trees ต้องการ O(log(log(N))) bits metadata ต่อ node ในรูป integer "level" Invariants ต่อไปนี้ถือสำหรับ AA trees −
Level ของทุก leaf node คือ 1
Level ของทุก left child น้อยกว่า parent อยู่ 1 อย่างแน่นอน
Level ของทุก right child เท่ากับหรือน้อยกว่า parent 1
Level ของทุก right grandchild น้อยกว่า grandparent อย่างเคร่งครัด
ทุก node ที่ level > 1 มี 2 children
Re-balancing AA tree procedurally ง่ายกว่า red-black tree มาก
ใน AA tree ต้องการแค่ 2 distinct operations สำหรับ restore balance: "skew" และ "split" Skew คือ right rotation แทนที่ subtree ที่มี left horizontal link ด้วย right horizontal link Split คือ left rotation และ level increase แทนที่ subtree ที่มี 2 หรือมากกว่า consecutive right horizontal links ด้วยที่มี fewer consecutive right horizontal links 2 ตัว Operations "skew" และ "split" อธิบายด้านล่าง −
function skew is
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
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.
Take the middle node, 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
Split −
