ต้นไม้ AA ใน C/C++?

ต้นไม้ AA ในวิทยาการคอมพิวเตอร์ถูกกำหนดให้เป็นรูปแบบของต้นไม้ที่สมดุลซึ่งนำมาใช้เพื่อการจัดเก็บและเรียกข้อมูลที่สั่งอย่างมีประสิทธิภาพ ต้นไม้ AA จะถือว่าเป็นรูปแบบหนึ่งของต้นไม้สีแดง-ดำ ซึ่งเป็นรูปแบบของการค้นหาแบบไบนารีซึ่งสนับสนุนการเพิ่มและการลบรายการอย่างมีประสิทธิภาพ ตรงกันข้ามกับต้นไม้สีแดง-ดำ โหนดสีแดงบนทรี AA สามารถเพิ่มได้เฉพาะเป็นชายด์ย่อยด้านขวา ไม่มีชายด์ย่อยด้านซ้าย ผลลัพธ์ของการดำเนินการนี้คือการจำลองทรี 2-3 ทรีแทนทรี 2-3-4 ซึ่งทำให้การดำเนินการบำรุงรักษาง่ายขึ้น อัลกอริธึมการบำรุงรักษาสำหรับต้นไม้สีแดงดำต้องใช้หรือพิจารณารูปร่างที่แตกต่างกันเจ็ดแบบเพื่อให้สมดุลของต้นไม้ -

ตรงกันข้ามกับต้นไม้สีแดง-ดำ ในทางกลับกัน ต้นไม้ AA ต้องการเพียงสมมุติหรือพิจารณาสองรูปร่างเนื่องจากข้อกำหนดที่เข้มงวดซึ่งมีเพียงลิงก์ที่ถูกต้องเท่านั้นที่สามารถเป็นสีแดงได้ -

การหมุนที่สมดุล

ในขณะที่ทรีสีแดง-ดำต้องการข้อมูลเมตาที่สมดุลหนึ่งบิตต่อโหนด (สี) ต้นไม้ AA ต้องการบิตข้อมูลเมตา O(log(N)) ต่อโหนด ในรูปแบบของ "ระดับ" ของจำนวนเต็ม ค่าคงที่ด้านล่างมีไว้สำหรับต้นไม้ AA -

• ระดับของโหนดปลายสุดทุกอันถือเป็นหนึ่งเดียว

• ระดับของลูกทางซ้ายทุกคนนั้นเล็กกว่าระดับผู้ปกครองเพียงหนึ่งระดับเท่านั้น

• ระดับของเด็กที่ถูกต้องทุกคนจะเท่ากับหรือน้อยกว่าระดับของผู้ปกครอง

• ระดับของหลานที่ถูกต้องทุกคนนั้นน้อยกว่าระดับของปู่ย่าตายายอย่างเคร่งครัด

• ทุกโหนดที่มีระดับที่สูงกว่าหนึ่งมีลูกสองคน

การปรับสมดุลต้นไม้ AA ใหม่เป็นขั้นตอนง่ายกว่าหรือง่ายกว่าการปรับสมดุลต้นไม้สีแดง-ดำ

ในกรณีของทรี AA จำเป็นต้องมีการดำเนินการที่แตกต่างกันสองรายการในการกู้คืนยอดคงเหลือ:"เอียง" และ "แยก" การเอียงจะถือเป็นการหมุนทางขวาเพื่อแทนที่แผนผังย่อยที่ประกอบด้วยลิงก์แนวนอนด้านซ้าย ส่วนที่ประกอบด้วยลิงก์แนวนอนด้านขวาแทน ในกรณีของ Split จะเป็นการหมุนด้านซ้ายและการเพิ่มระดับเพื่อแทนที่แผนผังย่อยที่ประกอบด้วยลิงก์แนวนอนด้านขวาที่เรียงกันอย่างน้อย 2 ลิงก์ขึ้นไป โดยมีลิงก์หนึ่งที่มีลิงก์แนวนอนด้านขวาติดต่อกันน้อยกว่า 2 ลิงก์ การดำเนินการ "เอียง" และ "แยก" อธิบายไว้ด้านล่าง −

ฟังก์ชันเอียงคือ

   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

การแบ่งฟังก์ชันคือ

   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

แยก -