CoE KKU

AVL (Adelson-Velskii and Landis) tree เป็น binary search tree กำกับด้วยเงื่อนไขของการสมดุล โดยเงื่อนไขการสมดุลจะต้องสามารถจัดการได้ง่ายและต้องประกันได้ว่าความลึกของทรีจะเป็น $O(log\ n)$ รูปแบบอย่างง่ายที่สุดคือการกำหนดให้ทรีย่อยซ้ายและทรีย่อยขวาของรากมีความสูง (height) เท่ากันดังรูปที่ 4.28 ซึ่งไม่ทำให้ทรีตามข้อกำหนดนี้ตื้นได้

เงื่อนไขการสมดุลที่เป็นไปได้อีกอย่าง คือ กำหนดให้ทุก ๆ โนดในทรีจะต้องมีทรีย่อยซ้ายและทรีย่อยขวามีความสูงเท่ากัน ถ้ากำหนดให้ความสูงของทรีย่อยว่างใด ๆ (empty subtree) มีค่าเป็น -1 (ซึ่งใช้กันทั่วไป) แล้ว นั่นหมายความว่าจะมีก็แต่ เฉพาะทรีที่เป็น perfect balanced ซึ่งมีจำนวนโนดทั้งสิ้น 2k - 1 โนดเท่านั้นที่เป็นไปตามข้อกำหนดนี้ เงื่อนไขการสมดุลแบบนี้เข้มงวดเกินไปจนอาจใช้ประโยชน์ได้ไม่ดี ดังนั้นจึงมีการผ่อนคลายเงื่อนไขความสมดุลลงบ้าง

AVL tree เหมือนกับ binary search tree ยกเว้นมีข้อกำหนดเพิ่มเติมว่าทุก ๆ โนดในทรีจะต้องมีความสูงของทรีย่อยซ้ายและทรีย่อยขวาแตกต่างกันไม่เกิน 1 (กำหนดให้ความสูงของ empty tree มีค่าเป็น -1) รูปที่ 4.29 แสดงทรีที่ภาพด้านซ้ายเป็น AVL แต่ภาพทางขวาไม่เป็น

ด้วยข้อกำหนดเรื่องความสูงของโนดในทรีนี้ทำให้เราต้องจัดเก็บค่าความสูงของแต่ละโนดไว้ในโครงสร้างของโนดเองด้วย ได้มีการแสดงให้เห็นว่าความสูงที่มากที่สุดของ AVL มีค่าประมาณ $1.44\ log\ (N+2) – 0.328 $ แต่ในทางปฏิบัติมันจะมีค่ามากกว่า $log\ N$ อยู่เล็กน้อยเท่านั้น เช่น AVL ที่มีความสูงเท่ากับ 9 ที่ประกอบด้วยโนดจำนวนน้อยที่สุด (143) แสดงในรูปที่ 4.30 ทรีนี้มีทรีย่อยซ้ายเป็น AVL ขนาดเล็กสุดที่มีความสูงเท่ากับ 7 และมีทรีย่อยขวาที่มีขนาดเล็กสุดที่มีความสูง 8 นั่นหมายความว่า AVL ขนาดเล็กสุด (มีโนดจำนวนน้อยที่สุด) ที่มีความสูงเป็น $h$ คือ $S(h)$ นั้น คือ $$S(h) = S(h – 1) + S(h – 2) + 1 \text{โนด}$$

สำหรับ $h = 0$, มี $S(h) = 1$ และ $h = 1$, มี $S(h) = 2$

ดังนั้น จากที่กล่าวมาการดำเนินการทั้งหมดของทรีจึงใช้เวลาเป็น $O(log\ N)$ ยกเว้นการบรรจุค่า (เรากำหนดให้การลบเป็นแบบ lazy deletion) เมื่อมีการทำงานการบรรจุค่า เราจำเป็นจะต้องปรับปรุงสารสนเทศที่เกี่ยวกับความสมดุลของโนดทุกโนดตามเส้นทางย้อยกลับไปถึงโนดรากของทรี แต่สาเหตุที่เกิดความยุ่งยากในการบรรจุค่าลงในทรีเกิดขึ้นเพราะมันอาจจะไปทำลายคุณสมบัติความเป็น AVL-tree ได้ (เช่นเมื่อมีการบรรจุ 6 ลงใน AVL-tree รูปที่ 4.29 จะทำให้เงื่อนไขความสมดุลเสียหายที่โนด 8) ซึ่งจะต้องจัดการให้กลับสู่สภาพความเป็น AVL และสามารถทำได้ด้วยการดำเนินการที่เรียกว่า rotation

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

ถ้าให้โนดที่ต้องการปรับสมดุลใหม่ชื่อโนด a เนื่องจากว่าโนดใด ๆ ในทรีมีโนดลูกได้มากที่สุดเพียงสองโนดเท่านั้นดังนั้นความไม่สมดุลของความสูงคือเมื่อทรีย่อย 2 ทรีย่อยของ a แตกต่างกัน 2 ระดับ นอกจากนี้เราจะเห็นได้ว่าการเสียสมดุลดังกล่าวนี้อาจจะเกิดขึ้นได้ไม่กรณีใดก็กรณีหนึ่งจาก 4 กรณี คือเกิดจากการบบรจุค่าใหม่ลงในตำแหน่ง ดังนี้: 1. การบรรจุเกิดขึ้นใน left subtree ของ left child ของ a 2. การบรรจุเกิดขึ้นใน right subtree ของ left child ของ a 3. การบรรจุเกิดขึ้นใน left subtree ของ right child ของ a 4. การบรรจุเกิดขึ้นใน right subtree ของ right child ของ a

กรณี 1 และ 4 เป็นกรณีสมมาตร mirror image symmetries กันเมื่อเทียบกับ a, เช่นเดียวกับกรณี 2 และ 3 –ดังนั้นโดยพื้นฐานแล้วจึงกล่าวได้ว่ามีกรณีที่จะเกิดขึ้นได้เพียง 2 กรณีเท่านั้น อย่างไรก็ตามในแง่ของโปรแกรมแล้วก็ยังคงต้องพิจารณาเป็น 4 กรณีอยู่ดี

กรณีที่ 1 เกิดขึ้นเมื่อมีการบรรจุโนดของค่าใหม่ลงทางด้านนอก (“outside”) (กล่าวคือเป็นการบรรจุที่เรียกว่า left-left หรือ right-right), ซึ่งสามารถจัดการแก้ไขได้ด้วยการหมุนโนดของทรีที่เรียกว่า single rotation กรณีที่ 2 เกิดขึ้นเมื่อมีการบรรจุโนดของค่าใหม่ลงทางด้านใน (“inside”) (กล่าวคือเป็นการบรรจุที่เรียกว่า left-right หรือ right-left) ซึ่งสามารถจัดการแก้ไขได้ด้วยการหมุนโนดของทรีที่เรียกว่า double rotation การดำเนินการหมุนโนดในทรีเป็นการดำเนินการพื้นฐานสำหรับอัลกอริทึมที่ใช้เพื่อการปรับสมดุลของทรีที่พบเห็นได้บ่อย

4.4.1 Single Rotation

รูปที่ 4.31 แสดงรูปแบบการหมุนโนดแบบ single rotation ที่ใช้แก้ไขการเสียสมดุลในกรณีที่ 1 โดยภาพด้านซ้ายเป็นภาพแสดงสภาวะก่อนการหมุนโนดและภาพด้านขวาเป็นภาพหลังการหมุนโนด จากภาพซ้ายจะเห็นว่าโนด k2 ผิดเงื่อนไขความสมดุลของ AVL เนื่องจากทรีย่อยซ้ายของมันมีความสูง (หรือมีความลึก) มากกว่าของทรีย่อยขวาของมันอยู่ 2 ระดับ (ดูจากเส้นแสดงระดับที่แสดงด้วยเส้นประในรูปหมายถึงระดับ) ภาพด้านซ้ายเป็นภาพที่เกิดขึ้นหลังจากมีการบรรจุโนดใหม่ลงในทรีย่อย X ซึ่งทำให้ทรีย่อยนี้ขยายลงไปอีกหนึ่งระดับและจะมีความลึกมากกว่าทรีย่อย Z อยู่ 2 ระดับ

ด้วยคุณสมบัติที่มันเป็น binary search tree หมายความว่า k2 > k1 ดังนั้นหลังการหมุนโนดแล้ว k2 ต้องกลายมาเป็นลูกทางขวาของ k1 ของทรีใหม่ซึ่งทำให้ k1 กลายเป็นรากของทรีใหม่ ทรีย่อย X ยังคงเป็นทรีย่อยซ้ายของ k1 และทรีย่อย Z ยังคงเป็นทรีย่อยขวาของ k2 เช่นเดิม ส่วนทรีย่อย Y ซึ่งประกอบด้วยโนดที่มีค่าอยู่ระหว่าง k1 และ k2 ในทรีเดิมก็จะสามารถจัดให้เป็นทรีย่อยซ้ายของ k2 ในทรีใหม่ได้ จะเห็นได้ว่าการทำการหมุนโนดที่กล่าวมานั้นความจริงแล้วเป็นเพียงการปรับเปลี่ยน pointer สองถึงสามครั้งเท่านั้น และทำให้โครงสร้างของทรีนั้น ๆ เปลี่ยนไปโดยยังคงรักษาคุณสมบัติการเป็น search tree ไว้ รูปที่ 4.32 แสดงการบรรจุค่า 6 ลงในทรี AVL ของภาพด้านซ้ายซึ่งทำให้โนด 8 เสียความสมดุล เราสามารถแก้ไขได้ด้วยการทำ single rotation ระหว่างโนด 7 และ 8 และจะได้ทรีใหม่ตามภาพทางขวามือซึ่งเป็นทรี AVL ดังที่ได้กล่าวมาก่อนหน้านี้แล้วว่ากรณี 4 เป็นกรณีสมมาตรของกรณี 1 ดังนั้นในกรณี 4 นี้ก็ทำการหมุนโนดด้วย single rotation เช่นเดียวกับกรณี 1 รูปที่ 4.33 แสดง single rotation ของกรณี 4

ถ้าเริ่มต้นด้วย AVL tree ว่างและดำเนินการบรรจุค่า 3, 2, 1 และ 4 ถึง 7 เรียงตามลำดับ ปํญหาเกิดขึ้นครั้งแรกเมื่อมีการบรรจุค่า 1 เพราะจะทำให้เสียสมดุลที่โนดราก เราต้องทำ single rotation ระหว่างโนดรากกับโนดลูกตัวซ้ายของมัน ดังรูปก่อนและหลังการหมุนดังนี้

จากนั้นบรรจุ 4 และตามด้วยการบรรจุ 5 ซึ่งทำให้เสียสมดุลที่โนด 3 และจะต้องแก้ไขด้วย single rotation นอกจากการเปลี่ยนแปลงจะเกิดขึ้นในส่วนของโนดที่มีการหมุดแล้ว เราต้องไม่ลืมว่าในโปรแกรมที่ใช้ในการทำงานจริงนั้นต้องมีการเปลี่ยนแปลงส่วนอื่น ๆ ของทรีเกิดขึ้นด้วย ในกรณีของทรีนี้ต้องมีการเปลี่ยนโนดลูกตัวขวาของ 2 จากเดิมคือ 3 เป็นโนดใหม่คือ 4 ด้วย ดังรูปข้างล่างนี้

ต่อไปเป็นการบรรจุ 6 ทำให้เสียสมดุลที่โนดราก เนื่องจากทรีย่อยซ้าย (มีโนด 1 เป็นรากของทรีย่อย) มีความสูง 0 ส่วนทรีย่อยขวามีสูง 2 ดังนั้นเราต้องทำ single rotation ที่รากระหว่างโนด 2 และโนด 4

จากนั้นบรรจุ 7 ซึ่งต้องหมุนอีกครั้ง ดังรูปข้างล่าง

4.4.2. Double Rotation

อัลกอริทึมที่กล่าวมาแล้วนั้นมีปัญหาอย่างหนึ่ง กล่าวคือ พิจารณาจากรูปที่ 4.34 ซึ่งไม่สามารถใช้ในการแก้ปัญหาสำหรับกรณีที่ 2 หรือ กรณีที่ 3 ปัญหาที่เกิดคือ ทรีย่อย Y อยู่ในระดับลึกเกินไป และการหมุนโนดแบบ single rotation ไม่ได้ช่วยลดระดับความลึกลงไปได้ ในกรณีนี้จะต้องแก้ปัญหาด้วยการหมุนโนดแบบ double rotation ดังรูปที่ 4.35

การที่สามารถบรรจุค่าลงในทรีย่อย Y ของทรีในรูปที่ 4.34 ได้ก็หมายความว่ามันมีหน่วยข้อมูล (โนด) อยู่แล้วคือไม่เป็นทรีย่อยว่าง ดังนั้นเราจึงอนุมานได้ว่ามันต้องประกอบด้วยโนดรากและทรีย่อย 2 ทรีย่อย ซึ่งก็หมายความว่าเราสามารถพิจารณาทรีในรูป 4.34 นี้ได้ว่าเป็นทรีที่ประกอบด้วย 4 ทรีย่อยที่เชื่อมต่อด้วยโนด 3 โนด (ดูรูปที่ 4.35) จากรูป 4.35 จะเห็นว่าทรีย่อย B และ C อยู่ในระดับที่ลึกกว่าทรีย่อย D อยู่ 2 ระดับ เพียงแต่ไม่สามารถระบุให้แน่นอนได้จะเป็นทรีย่อยไหนแต่ก็ไม่มีความสำคัญว่าจะเป็นทรีย่อยไหน ดังนั้นในรูปที่ 4.35 จะแสดงให้ทั้งทรีย่อย B และ C อยู่ลึกว่าทรีย่อย D อยู่ 2 ระดับ

เพื่อปรับสภาพความสมดุลของทรี เราไม่สามารถให้ k3 เป็นรากของทรีได้และการหมุนโนดระหว่าง k3 และ k1 แก้ปัญหาไม่ได้ดังที่แสดงในรูป 4.34 ดังนั้นจึงเหลือทางเลือกเดียวคือจัดให้ k2 เป็นโนดรากใหม่ นี่จะทำให้ k1 กลายเป็นโนดลูกซ้ายของ k2 และจัดให้ k3 เป็นโนดลูกขวาของ k2 ซึ่งจะเป็นตัวที่จะกำหนดตำแหน่งของทรีย่อยทั้งสี่ ทรีผลลัพธ์ที่ได้จะเป็นไปตามคุณสมบัติของ AVL รูปที่ 4.36 แสดงทรีของกรณี 3 ซึ่งแก้ไขได้ด้วย double rotation

ถ้าต้องบรรจุค่า 16, 15, .., 10 และตามด้วยค่า 8 และ 9 ตามลำดับลงใน AVL ต่อเนื่องจากตัวอย่าง AVL ที่ได้แสดงมาข้างบนนั้น เริ่มด้วยบรรจุ 16 ซึ่งไม่ทำให้คุณสมบัติความเป็น AVL เปลี่ยนแปลงไป ตามด้วยการบรรจุ 15 ซึ่งทำให้เสียสมดุลที่โนด 7 ในกรณีนี้คือกรณี 3 ซึ่งแก้ไขได้ด้วย right-left double rotation มีโนด 7, 16 และ 15 ในกรณีนี้โนด k1 ก็คือโนด 7, k3 คือโนด 16 และ k2 คือโนด 15 มีทรีย่อย A, B, C และ D เป็นทรีว่าง ดังนี้

จากนั้นบรรจุค่า 14 ซึ่งทำให้ต้องใช้ right-left double rotation ของโนด 6, 15, และ7 และในกรณีนี้โนด 6 จะเป็น k1 โนด 7 เป็น k2 และโนด 15 เป็นโนด k3 มีทรีย่อย A ที่มีโนดรากเป็นโนด 5 มีทรีย่อย B เป็นทรีย่อยว่างซึ่งเดิมก็คือลูกทางซ้ายของโนด 7 นั่นเอง ทรีย่อย C คือทรีที่มีโนดรากเป็นโนด 14 และสุดท้ายคือทรีย่อย D คือทรีที่มีโนดรากเป็นโนด 10 ดังรูปต่อไปนี้

เมื่อบรรจุ 13 จะทำให้เสียสมดุลที่รากของทรี จะเห็นว่าเนื่องจากค่า 13 ที่บบรจุใหม่นี้ไม่ใช่เป็นค่าที่อยู่ระหว่าง 4 กับ 7 ทำให้เรารู้ได้ว่าการหมุนโนดที่จะใช้คือการหมุนแบบ single rotation เท่านั้น ดังนี้

การบรรจุ 12 ต้องหมุนโนดด้วย single rotation ดังนี้

เมื่อบรรจุ 11 ต้องใช้ single rotation และหลังจากบรรจุ 10 ตามมาก็จะต้องทำ single rotation เช่นเดียวกัน จากนั้นบรรจุค่า 8 โดยไม่ต้องทำการหมุนโนดซึ่งจะได้ทรีดังนี้

สุดท้ายเป็นการบรรจุค่า 9 ซึ่งจะทำให้โนด 10 เสียสภาพสมดุล และจะเห็นว่าค่า 9 นี้เป็นค่าที่อยู่ระหว่างโนด 10 และ 8 ดังนั้นจึงต้องใช้ double rotation ระหว่างโนด 10, 8 และ 9 ซึ่งทำให้ได้ทรีดังนี้

การเขียนโปรแกรมค่อนข้างจะตรงไปตรงมาไม่ซับซ้อนเพียงแต่มีกรณีการเลือกหลายทางเลือกเท่านั้น ในการบรรจุโนดใหม่ที่มีค่า X เข้าใน AVL tree T เราจะทำงานในแบบ recursive เพื่อการบรรจุค่าใหม่นี้ลงใน subtree ของ T (ต่อไปเรียกว่า TLR) ถ้าความสูง (height) ของ TLR ไม่มีการเปลี่ยนแปลงก็เป็นอันเสร็จสิ้นการทำงาน แต่หากเกิดความไม่สมดุลของความสูงขึ้นใน T เราก็จะทำการ single หรือ double rotation แล้วแต่กรณีขึ้นอยู่กับค่า X และข้อมูลใน T และ TLR, จากนั้นจะทำการปรับปรุงค่าความสูงและจบสิ้นการทำงาน เนื่องจากโดยปกติแล้วการหมุนโนดเพียงครั้งเดียวก็เป็นการเพียงพอแล้ว ดังนั้นการเขียนโปรแกรมโดยไม่ต้องใช้รูปแบบ recursive ก็ทำงานได้เร็วกว่าโปรแกรมในแบบ recursive แต่ก็เขียนโปรแกรมได้ยากกว่าแบบ recursive

รูปที่ 4.37 แสดงโครงสร้างของโนดของ AVL ชื่อ AvlNode รูปที่ 4.38 แสดงฟังก์ชันเพื่อคำนวณค่าความสูงของโนด และรูปที่ 4.39 แสดงฟังก์ชันการบรรจุโนดของค่าใหม่ลงในทรี (ส่วนของโปรแกรมส่วนอื่น ๆ ของ AVLที่ไม่ได้กล่าวถึงในที่นี้ได้แสดงไว้ท้ายบทนี้)

class AvlNode 
    {   AvlNode( Comparable theElement )  {   this( theElement, null, null );  }
        AvlNode( Comparable theElement, AvlNode lt, AvlNode rt ) 
    {  element  = theElement;  left     = lt; right    = rt;  height   = 0;  }
        Comparable element;      	// The data in the node
        AvlNode    	left;         	// Left child
        AvlNode    	right;        	// Right child
        int        	height;       	// Height
    }

รูปที่ 4.37 การประกาศโนดของ AVL trees

private static int height( AvlNode t )
{   return t == null ? -1 : t.height;   } 

รูปที่ 4.38 Method สำหรับคำนวณความสูงของ AVL tree

private AvlNode insert( Comparable x, AvlNode t )
{   if  ( t == null )  
        t = new AvlNode( x, null, null );
    else  if ( x.compareTo( t.element ) < 0 )
    {   t.left = insert( x, t.left );
            if	(height(t.left) - height( t.right ) == 2 )
                if (x.compareTo(t.left.element) < 0 ) 
                    t = rotateWithLeftChild( t );
                else
                    t = doubleWithLeftChild( t );     
    }
    else  if ( x.compareTo( t.element ) > 0 ) 
    { t.right = insert( x, t.right );
        if (height(t.right) - height(t.left) == 2 )
            if (x.compareTo(t.right.element) >0)
                t = rotateWithRightChild( t );
            else
                t = doubleWithRightChild( t ); 
    }
    else
       ;  // Duplicate; do nothing
   t.height =  max( height( t.left ),
   height( t.right ) ) + 1;
   return t;
} 

รูปที่ 4.39 การบรรจุค่าลงใน AVL tree

/*       * For AVL trees, this is a single rotation for case 4.
         * Update heights, then return new root.     */
        private static AvlNode rotateWithRightChild( AvlNode k1 )
        {
            AvlNode k2 = k1.right;
            k1.right = k2.left;
            k2.left = k1;
            k1.height = max( height( k1.left ), height( k1.right ) ) + 1;
            k2.height = max( height( k2.right ), k1.height ) + 1;
            return k2;
        } 

รูปที่ 4.41 ฟังก์ชันการหมุนโนด single rotation

รูปที่ 4.41 แสดงฟังก์ชันการหมุนโนด rotateWithLeftChild() ซึ่งจะเปลี่ยนทรีของรูปที่ 4.40 จากทรีซ้ายมือไปเป็นทรีในภาพขวามือและให้ค่ากลับเป็น reference ของรากของทรีใหม่

/** For AVL trees, this is a double rotation for case 2.
* Update heights, then return new root.  */
 
private static  AvlNode doubleWithLeftChild ( AvlNode k3 )
{   k3.left = rotateWithRightChild( k3.left );
    return rotateWithLeftChild( k3 );
} 

รูปที่ 4.43 ฟังก์ชันการหมุนโนดแบบ double rotation

รูปที่ 4.43 แสดงฟังก์ชันการหมุนโนดแบบ double rotation ซึ่งจะเปลี่ยนทรีของรูปที่ 4.42 จากทรีซ้ายมือไปเป็นทรีในภาพขวามือและให้ค่ากลับเป็น reference ของรากของทรีใหม่