ผู้ใช้:Kacha001/ต้นไม้เอเอ
ต้นไม้เอเอในวิทยาการคอมพิวเตอร์เป็นรูปแบบของต้นไม้สมดุลที่ใช้สำหรับจัดเก็บและเรียกข้อมูลได้อย่างมีประสิทธิภาพ ต้นไม้เอเอมีชื่อมาจาก Arne Andersson, ซึ่งเป็นผู้คิดค้นต้นไม้เอเอขึ้นมา
ต้นไม้เอเอเป็นรูปแบบของต้นไม้ดำแดงมีลักษณะเป็นต้นไม้ค้นหาแบบไบนารีที่สนับสนุนประสิทธิภาพการเพิ่มและการลบรายการ ไม่เหมือนต้นไม้ดำแดงที่โหนดสีแดงบนต้นไม้เอเอจะสามารถเพิ่มเป็นโหนดลูกทางขวาเท่านั้น กล่าวคือไม่มีโหนดสีแดงใดที่สามารถเป็นโหนดลูกได้ ซึ่งส่งผลให้เกิดการจำลองแบบต้นไม้ 2-3 แทนที่จะเป็นโครงสร้างต้นไม้ 2-3-4 ซึ่งช่วยลดความยุ่งยากในการดำเนืนการ อัลกอริธึมการดำเนืนการสำหรับต้นไม้ดำแดงจำเป็นต้องพิจารณารูปทรงที่แตกต่างกันเจ็ดอย่างเพื่อให้ต้นไม้สสมดุล:
ต้นไม้ AA นั้นจะต้องพิจารณาสองรูปร่างเนื่องจากเงื่อนไขที่เข้มงวดที่มีเพียงการเชื่อมโยงทางขวาที่เป็นสีแดงได้:
สมดุลการหมุน[แก้]
ต้นไม้สีแดงดำจะใช้บิตของข้อมูลเป็นสีในการสมดุลต่อโหนด ในขณะที่ต้นไม้เอเอต้องมีบิตของข้อมูลในการรักษาสมดุลต่อโหนดในรูปแบบ"ระดับ":
- ทุกๆระดับของโหนดใบเป็นหนึ่ง
- ทุกๆระดับของโหนดลูกทางซ้ายจะมีค่าน้อยกว่าโหนดพ่อ 1 ระดับ
- ทุกๆระดับของโหนดลูกทางขวาจะมีค่าเท่ากับโหนดพ่อหรือน้อยกว่าโหนดพ่อ 1 ระดับ
- ทุกๆระดับของโหนดหลานทางขวาจะต้องมีค่าน้อยกว่าโหนดปู่
- ทุกๆโหนดที่มีระดับมากกว่าหนึ่งต้องมีโหนดลูกอย่างน้อยสองโหนด
การเชื่องต่อโหนดลูกที่มีระดับเท่ากันจะเรียกว่าการเชื่อมต่อแนวนอน อนุญาตให้ใช้การเชื่อมต่อทางขวาเป็นการเชื่อมต่อแนวนอนได้แต่ไม่สามารถเชื่อมต่อทางซ้ายเป็นการเชื่อมต่อแบบแนวนอนได้ ข้อจำกัดเหล่านี้มีความเข้มงวดมากกว่าต้นไม้ดำแดงซึ่งมีผลทำให้ต้นไม้เอเอมีการปรับสมดุลง่ายกว่าต้นไม้ดำแดง
การเพิ่มและการลบข้อมูลของต้นเอเอจะทำให้ต้นไม้เอเอไม่สมดุลชั่วคราวดังนั้นจะต้องมีการดำเนินงานสองอย่างเพื่อปรับสมดุลของต้นไม้เอเอคือ "การเอียง" และ "การแบ่ง" การเอียงเป็นการหมุนทางขวาให้ต้นไม้ย่อยที่มีการเชื่อมต่อในแนวนอนทางด้านซ้ายไปแทนที่ส่วนที่มีการเชื่อมต่อแนวนอนทางขวา ส่วนการแบ่งคือการหมุนซ้ายและเพิ่มระดับเพื่อแทนที่ต้นไม้ย่อยที่มีการเชื่อมโยงแนวนอนทางขวาตั้งแต่สองโหนดขึ้นไป
การดำเนินการแทรกและการลบจะปรับสมดุลง่ายขึ้นโดยการอาศัยการเอียงและการแยกเพื่อปรับเปลี่ยนโครงสร้างเฉพาะเมื่อจำเป็นโดยให้ผู้ใช้ตัดสินใจเองว่าจะเอียงหรือแยกออก
การเอียง:
function skew is
input: T, a node representing an AA tree that needs to be rebalanced.
output: Another node representing the rebalanced AA tree.
if nil(T) then
return Nil
else if nil(left(T)) then
return T
else if level(left(T)) == level(T) then
Swap 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
Skew: AA Tree Skew2.svgตัวอย่างโค้ด python
def Skew(root):
global null
if root == null:
return null
elif root.left == null:
return root
elif root.left.level == root.level:
save = root.left
root.left = save.right
save.right = root
return save
else:
return root
การแบ่ง:
function split is
input: T, a node representing an AA tree that needs to be rebalanced.
output: Another node representing the rebalanced AA tree.
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ตัวอย่างโค้ด python
def Split(root):
global null
if root == null:
return null
elif root.level == root.right.right.level:
save = root.right
root.right = save.left
save.left = root
save.level += 1
return save
else:
return rootการเพิ่มข้อมูล[แก้]
การแทรกจะเริ่มต้นด้วยการค้นหาและการแทรกทับเหมือนต้นไม้ทวิภาคแบบปกติ หากมีการเชื่อมโยงแนวนอนทางซ้ายเกิดขึ้นจะมีการเอียงและหากมีการเชื่อมโยงแนวนอนทางขวาเกิดขึ้นจะมีการแบ่ง
function insert is
input: X, the value to be inserted, and T, the root of the tree to insert it into.
output: A balanced version T including X.
Do the normal binary tree insertion procedure. Set the result of the
recursive call to the correct child in case a new node was created or the
root of the subtree changes.
if nil(T) then
Create a new leaf node with X.
return node(X, 1, Nil, Nil)
else if X < value(T) then
left(T) := insert(X, left(T))
else if X > value(T) then
right(T) := insert(X, right(T))
end if
Note that the case of X == value(T) is unspecified. As given, an insert
will have no effect. The implementor may desire different behavior.
Perform skew and then split. The conditionals that determine whether or
not a rotation will occur or not are inside of the procedures, as given
above.
T := skew(T)
T := split(T)
return T
end functionตัวอย่างโค้ด pyhton
def Insertion(root,val):
global null
if root == null:
root = AANode(1,null,null,val)
elif(root.val > val):
root.left = Insertion(root.left,val)
elif(root.val < val):
root.right = Insertion(root.right,val)
root = Skew(root)
root = Split(root)
return root
การลบ[แก้]
ในการลบข้อมูลของต้นไม้เอเอก็คล้ายๆกับการลบข้อมูลขอต้นไม้ทวิภาคอื่นๆ คือสามารถเปลี่ยนการลบโหนดภายใน เป็นการลบโหนดใบได้ โดยการสลับข้อมูลของโหนดมันกับโหนดลูกหลานที่มีค่าใกล้เคียงกับโหนดนั้นมากที่สุด
การรักษาสมดุลของต้นไม้นั้นหลังจากที่ทำการกำจัดโหนดที่ต้องการออกไป ต้องทำการปรับต้นไม้กับโหนดที่มีระดับต่างกับลูกมันอยู่สอง หรือโหนดที่เสียลูกมันไป หลังจากนั้นทำการเอียงและการแบ่งค่าระดับ
ขั้นตอน:
- ลดระดับเลยถ้าเป็นไปได้
- ทำการเอียงระดับ
- ทำการแบ่งระดับ
อย่างไรก็ตามเราต้องเอียงและแบ่งระดับทั้งหมดแทนที่จะเป็นแค่โหนดทำให้โค้ดของเรามีความยุ่งยากมากขึ้น
function delete is
input: X, the value to delete, and T, the root of the tree from which it should be deleted.
output: T, balanced, without the value X.
if nil(T) then
return T
else if X > value(T) then
right(T) := delete(X, right(T))
else if X < value(T) then
left(T) := delete(X, left(T))
else
If we're a leaf, easy, otherwise reduce to leaf case.
if leaf(T) then
return Nil
else if nil(left(T)) then
L := successor(T)
right(T) := delete(value(L), right(T))
value(T) := value(L)
else
L := predecessor(T)
left(T) := delete(value(L), left(T))
value(T) := value(L)
end if
end if
Rebalance the tree. Decrease the level of all nodes in this level if
necessary, and then skew and split all nodes in the new level.
T := decrease_level(T)
T := skew(T)
right(T) := skew(right(T))
if not nil(right(T))
right(right(T)) := skew(right(right(T)))
end if
T := split(T)
right(T) := split(right(T))
return T
end functionfunction decrease_level is
input: T, a tree for which we want to remove links that skip levels.
output: T with its level decreased.
should_be = min(level(left(T)), level(right(T))) + 1
if should_be < level(T) then
level(T) := should_be
if should_be < level(right(T)) then
level(right(T)) := should_be
end if
end if
return T
end functionตัวอย่างโค้ด
def Delete(root,val):
global null
if root == null:
return null
else:
if root.val == val:
if root.left != null and root.right != null:
heir = root.left
while heir.right != null:
heir = heir.right
root.val = heir.val
if(root.left == null):
root.left = Delete(null,root.val)
else:
root.left = Delete(root.left,root.val)
elif root.left == null:
root = root.right
else:
root = root.left
elif root.val < val:
root.right = Delete(root.right,val)
else:
root.left = Delete(root.left,val)
should_be = 0
if (root.left.level < root.right.level):
should_be = root.left.level + 1
else:
should_be = root.right.level + 1
if should_be < root.level:
root.level = should_be
if should_be < root.right.level:
root.right.level = should_be
return Skew(Split(root))
ประสิทธิภาพ[แก้]
ประสิทธิภาพของต้นไม้เอเอจะเทียบเท่ากับประสิทธิภาพของต้นไม้สีดำแดง แม้ว่าต้นไม้เอเอจะทำให้การหมุนมากกว่าต้นไม้สีดำแดงเกิดประสิทธิภาพที่คล้ายคลึงกัน ต้นไม้สีแดงดำมีความสม่ำเสมอในการทำงานมากกว่าต้นไม้เอเอแต่ต้นไม้เอเอมีมีเงื่อนไขที่เข้มงวดทำให้เวลาในการค้นหาเร็วขึ้นเล็กน้อย
อ้างอิง[แก้]
- "A Disquisition on The Performance Behavior of Binary Search Tree Data Structures (pages 67-75)"