การหมุนต้นไม้ เพื่อให้คงสภาพ Balance Tree (AVL Tree)

การหมุนเพื่อคงสภาพ AVL Tree

สมมุติต้นไม้ Binary Search Tree ขึ้นมา 1 ต้น ที่อยู่ในสภาพ balance และสมมุติโหนด p เป็นโหนดที่อาจจะต้องถูก rebalance เนื่องมีโหนดใหม่ถูกเพิ่มเข้ามาเป็นลูกของ subtree ด้านซ้าย หรือ subtree ด้านขวา

เช่น ถ้าสมมุติ Binary Search Tree ไว้ดังภาพนี้

เราจะต้องทำการ rebalance ก็ต่อเมื่อ Height ด้านซ้ายของ p แตกต่างจาก Height ด้านขวาของ p มากกว่า 2 เช่นแบบนี้

แต่ถ้าความสูง (height) แตกต่างกันน้อยกว่า 2 (เช่น 0 หรือ 1) เราจะไม่ต้องทำการ rebalance

เพราะฉะนั้นกรณีที่จะทำให้เราต้อง rebalance โหนด p มีอยู่ 4 กรณีคือ

กรณี 1 เพิ่มโหนดใหม่เข้าไปที่ subtree ด้านซ้าย ของโหนดลูกด้านซ้ายของ p (สมมุติ n เป็นโหนดใหม่)

กรณี 2 เพิ่มโหนดใหม่เข้าไปที่ subtree ด้านขวา ของโหนดลูกด้านซ้ายของ p

กรณี 3 เพิ่มโหนดใหม่เข้าไปที่ subtree ด้านซ้ายของโหนดลูกด้านขวาของ p

กรณี 4 เพิ่มโหนดใหม่เข้าไปที่ subtree ด้านขวาของโหนดลูกด้านขวาของ p

ทั้ง 4 กรณีนี้อาจจะทำให้ length ด้านซ้ายมีความยาวต่างกับ length ด้านขวาเท่ากับ 2 ก็ได้ แต่กรณีที่ 1 กับ 4 เราเรียกว่าเป็น outside เพราะอยู่ขอบนอก แบบ outside นี้จะ rebalance โดยวิธี single-rotation ส่วนกรณีที่ 2 กับ 3 เราเรียกว่าเป็น inside เพราะอยู่ด้านใน (ตามภาพ) แบบ inside นี้จะ rebalance โดยวิธี double-rotation

1. single-rotation

1.1 การหมุนขวาครั้งเดียว (single right rotation)

การหมุนครั้งเดียว แบบหมุนขวา (right rotate) ทำได้ดังนี้ สมมุติมีสภาพเริ่มต้นอยู่แบบนี้

และ a เป็นโหนดแม่ ที่มี length ด้านซ้ายยาวกว่า length ด้านขวาเท่ากับ 2 (a ไม่จำเป็นต้องเป็น root เสมอไป แต่อยู่ในเส้นทางจาก c ขึ้นไปที่ root) ส่วนโหนด c คือโหนดที่เพิ่มเข้ามาใหม่ ทำตามขั้นตอนต่อไปนี้

A. เอา b ไปแทนที่ a แขนซ้าย a จะว่าง

B. ยกลูกด้านขวาของ b ให้แขนซ้าย a ถือไว้ แขนขวา a จะว่าง

C. เอาแขนขวา b ที่ว่างอยู่จับหัว a เอาไว้

ทั้ง 3 ขั้นตอนสามารถแสดงเป็นรูปภาพได้ดังนี้

A. เอา b ไปแทนที่ a แขนซ้าย a จะว่าง

B. ยกลูกด้านขวาของ b ให้แขนซ้าย a ไปถือไว้

C. เอาแขนขวา b ที่ว่างอยู่จับหัว a ไว้

ตัวอย่างการหมุนขวา เช่น

จากภาพเมื่อนำโหนดใหม่เพิ่มเข้าไป เช่นโหนดมีค่าเป็น 1 เพิ่มเข้าไปดังนี้

เมื่อไล่ length เปรียบเทียบกันระหว่างด้านซ้าย และด้านขวา ขึ้นมาตั้งแต่โหนด 1 ไล่ขึ้นมาเรื่อยๆตามทางพุ่งขึ้นสู่ root จะมาหยุดที่โหนด 10 เพราะ legnth ด้านซ้ายยาว 3 และ length ด้านขวายาว 1 ซึ่งแตกต่างกันเป็น 2 แสดงว่าจุดหมุน (Pivot Node) อยู่ที่โหนด 10 เราจะใช้วิธีการหมุนขวา โดยยึดหลัก A. B. C. ตามขั้นตอนที่กล่าวไว้ข้างต้น แสดงได้ด้วยภาพดังนี้

หรือเขียนแบบสั้นๆ จะได้ภาพโหนดหลังจากหมุนขวาเสร็จแล้วดังนี้

จะเห็นว่าเมื่อหมุนแล้วจะไม่มีโหนดไหนที่ length ด้านซ้าย แตกต่างจาก length ด้านขวาเกิน 1 ซึ่งยังคงความเป็น AVL Tree ไว้ได้

1.2 การหมุนซ้าย (single left rotation)

การหมุนครั้งเดียว (single-rotation) แบบหมุนซ้ายจะเกิดกับกรณีที่ 4 แบบ outside โดยใช้หลักการเดียวกันกับการหมุนขวา

ขั้นตอนการหมุนซ้ายคือ

A. เอา b ไปแทนที่ a แขนขวา a จะว่าง

B. เอาลูกด้านซ้ายของ b ยกให้แขนขวา a ไปถือไว้ แขนซ้าย b จะว่าง

C. เอาแขนซ้าย b ที่ว่างอยู่ไปจับหัว a ไว้

สามารถอธิบายเป็นรูปภาพได้ดังนี้

ตัวอย่างเช่นสมมุติว่าเรามีต้นไม้ที่มีโหนดเรียงกันมาแบบนี้

และเราจะเพิ่มโหนดใหม่เข้าไปมีค่าเป็น 20

ลองไล่ระดับจากโหนดที่เพิ่มเข้าไป ขึ้นไปหา root จะพบว่าโหนดที่มี length ด้านซ้ายต่างจาก length ด้านขวาเป็น 2 คือ โหนด 16 เพราะฉะนั้น Pivot Point คือโหนด 16 และทำให้เราหมุนซ้ายได้แบบนี้

2. double rotation

การหมุน 2 ครั้งจะทำกับการเพิ่มโหนดแบบ inside ที่ลักษณะ left-right หรือ right-left จากโหนดที่เป็น Pivot Point เท่านั้น เช่น แบบนี้

จะเห็นว่าเมื่อเพิ่มโหนด 18 เข้าไปจะทำให้ไม่เป็นต้นไม้ AVL เพราะหนักมาด้านขวามากเกินไป และเมื่อไรความยาวจากโหนด 18 ขึ้นไปถึงโหนด 10 จะพบว่ามีความแตกต่างระหว่าง length ด้านซ้ายกับ length ด้านขวาเป็น 2 ดังนั้นจุดหมุนคือ 10

เป้าหมายก็คือเราจะต้องเอา b ไปแทนที่ a คือเอาโหนด 16 ไปแทนที่ตรงที่โหนด 10 อยู่ให้ได้ ซึ่งจะต้องทำให้เราต้องหมุน 2 ครั้งคือ ครั้งแรกหมุน 16 มาด้านขวา และครั้งที่ 2 หมุน 16 ไปด้านซ้าย เราจะใช้กฏการหมุนแบบ single rotation ตามที่เรียนมาข้างต้น มาหมุนโหนด 16 ให้ขึ้นไปอยู่ที่ตรงตำแหน่งโหนด 10 ให้ได้ตามภาพนี้

และเมื่อหมุนขวาอีกครั้งที่ b เพื่อให้โหนด 16 ไปแทนที่ตำแหน่งของโหนด 10 จะได้ภาพดังนี้

จะเห็นวิธีการ double rotation แบบ ขวา-ซ้าย คือ หมุนขวาก่อน แล้วค่อยมา หมุนซ้าย อีกแบบหนึ่งคือแบบ ซ้าย-ขวา คือหมุนซ้ายก่อนแล้วค่อยมา หมุนขวา สมมุติว่าเรามีข้อมูลอยู่ตามภาพสุดท้ายด้านบน และมีโหนดใหม่ถูกเพิ่มเข้ามาคือโหนด 9 ดังนี้

เมื่อไล่ระดับขึ้นไปตามเส้นทางจากโหนด 9 จนถึงโหนด root จะพบว่าโหนด 10 คือโหนดที่มี length ด้านซ้ายต่างกับ length ด้านขวาเป็น 2 ทำให้เรารู้ว่าโหนด 10 เป็น Pivot Point และถ้าเริ่มหมุนครั้งแรกเราจะหมุนโหนด 9 ไปด้านซ้ายก่อนตามภาพดังนี้