CoE KKU

ในหัวข้อนี้จะกล่าวถึงโครงสร้างข้อมูลที่ค่อนข้างจะไม่ซับซ้อนเรียกว่า splay tree ซึ่งเป็นโครงสร้างที่ประกันว่าการดำเนินการใด ๆ ที่กระทำต่อเนื่องกัน M ครั้งโดยเริ่มต้นการทำงานจากทรีว่างจะใช้เวลาสูงสุดเป็น $O(M\ log\ N)$ ถึงแม้ว่าที่เป็นเช่นนี้จะไม่ได้รับประกันว่าการดำเนินการเดี่ยว ๆ จะใช้เวลาทำงานเป็น $O(N)$ ปกติแล้วถ้ามีการดำเนินการใด ๆ ที่ต่อเนื่องกัน M ครั้งแล้วมี worst-case running time รวมเป็น $O(M\ f(N))$ เราจะเรียกว่ามันมี amortized running time เป็น $O(f(N))$ ดังนั้น splay tree มี amortized cost per operation เป็น $O(log\ N)$ การดำเนินการที่ต่อเนื่องกันนาน ๆ อาจจะใช้เวลามากหรือน้อยกว่าที่กล่าวนี้ได้

กล่าวสำหรับ binary search tree แล้ว การดำเนินการใด ๆ ที่มี worst-case time ต่อครั้งเป็น $O(N)$ เป็นสิ่งที่ยอมรับได้ถ้ามันเป็นการดำเนินการที่เกิดขึ้นไม่บ่อยนัก แต่ปัญหาของ binary search tree คือ ลำดับการดำเนินการที่มี running time ไม่ดีมักจะเกิดขึ้นเสมอ นั่นหมายความว่าเวลาที่ใช้โดยรวมก็จะมีผลให้การทำงานช้าลงได้ ดังนั้นโครงสร้างข้อมูลของ search tree ที่มี worst-case time เป็น $O(N)$ แต่ทว่าสามารถประกันได้ว่าจะใช้เวลาเป็น $O(M\ log\ N)$ เมื่อมีการดำเนินการต่อเนื่องกัน $M$ ครั้ง จึงเป็นที่ต้องการได้มากกว่า

ถ้ายินยอมให้มีการดำเนินการใด ๆ มี worst-case time bound เป็น $O(N)$ และเรายังต้องการให้ได้ amortized time bound เป็น $O(log\ N)$ แล้วละก็ หมายความว่าเมื่อมีการเข้าถึงโนดใด ๆ แล้วเราจะต้องทำการเคลื่อนย้ายโนดนั้นด้วย มิฉะนั้นแล้วถ้าเป็นโนดที่อยู่ในระดับลึก ๆ ที่เราเข้าถึงแล้วเราก็ยังต้องใช้เวลาในการเข้าถึงโนดนั้น (ที่อยู่ในระดับลึก) สำหรับการดำเนินการครั้งต่อ ๆ มาเสมอ นั่นคือ ถ้าไม่มีการเคลื่อนย้ายตำแหน่งแล้วการเข้าถึงแต่ละครั้งต้องใช้ $O(N)$ และถ้าต้องการเข้าถึงอย่างต่อเนื่อง $M$ ครั้ง ก็จะต้องใช้เวลาเป็น $O(M × N)$

แนวคิดพื้นฐานของ splay tree คือ หลังจากการเข้าถึงโนดใด ๆ แล้ว ก็จะเคลื่อนย้ายโนดนั้นให้มาอยู่ในตำแหน่งรากด้วยวิธี rotations ของ AVL tree หลาย ๆ ครั้ง ซึ่งจะพบว่าถ้าโนดนั้นอยู่ในระดับลึกลงไปในทรีก็หมายความว่าตามเส้นทางเข้าถึงโนดนั้นจะมีโนดอยู่จำนวนมากที่อยู่ในระดับลึกด้วยเช่นเดียวกัน และการจัดโครงสร้างใหม่ที่จะทำก็จะทำให้การเข้าถึงโนดในเส้นทางที่กล่าวนี้ในคราวถัดไปจะใช้เวลาน้อยลงด้วย ดังนั้นในการจัดโครงสร้างใหม่ที่จะเกิดขึ้นนี้จะต้องมีผลข้างเคียงต่อสมดุลของ tree ด้วย ในทางปฏิบัติมักจะพบว่า เมื่อการเข้าถึงโนดใดโนดหนึ่งแล้วก็มักจะต้องเข้าถึงโนดนั้นอีกในเวลาไม่นานนัก อย่างไรก็ตาม splay trees ไม่จำเป็นต้องใช้ข้อมูลของค่าความสูงหรือข้อมูลการสมดุล ดังนั้นจึงประหยัดเนื้อที่และทำให้การเขียนโปรแกรมง่ายขึ้น

วิธีการหนึ่งที่จัดโครงสร้างใหม่ให้แก่ทรีตามที่กล่าวข้างบนนั้นก็คือการทำการหมุนโนดด้วย single rotation จากระดับล่างขึ้นไประดับบน กล่าวคือจะทำการหมุนโนดทุก ๆ โนดตามเส้นทางการเข้าถึงโนดกับโนดแม่ของมัน พิจารณาสิ่งที่เกิดขึ้นเมื่อเข้า (ด้วยฟังก์ชัน find) ถึง k1 ในรูปข้างล่าง

เส้นทางการเข้าถึงโนดแสดงด้วเส้นประ เริ่มต้นด้วยการหมุน single rotation ระหว่างโนด k1 กับโนดแม่ของมัน จะได้ดังรูปข้างล่าง

จากนี้ทำการหมุนระหว่างโนด k1 และ k3 จะได้ทรีดังนี้

จากนั้นมีการหมุนอีก 2 ครั้งจนถึงโนดรากจะได้ดังนี้

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

จากที่กล่าวมานี้ ถึงแม้นว่าจะทำให้การเข้าถึงโนด k1 ในคราวถัดไปทำได้ด้วยค่าใช้จ่ายที่ถูกลง แต่มันก็ไม่ได้ทำให้สถานการณ์สำหรับโนดอื่น ๆ ตามเส้นทางการเข้าถึงมันดีขึ้นแต่อย่างใด จะเห็นว่าทรีที่เกิดจากการบรรจุค่า 1, 2, 3, . . . , N เข้าในทรีว่างก็จะทำให้ได้ทรีที่มีเฉพาะโนดลูกที่เป็นโนดทางด้านขวาเท่านั้น การสร้างนี้ไม่ใช่สิ่งเลวร้าย เนื่องจากใช้เวลาทั้งสิ้นเพียง $O(N)$ เท่านั้น สิ่งที่ไม่ดีคือ การจะเข้าถึงโนดที่มีค่า 1 ใช้เวลา N -1 หน่วยเวลา และหลังจากการหมุนโนดแล้ว การจะเข้าถึงโนดที่มีค่า 2 จะต้องใช้เวลาเป็น N - 2 หน่วยเวลา นั่นคือเวลาทั้งหมดที่ต้องใช้ในการเข้าถึงทุก ๆ โนดในทรี คือ $∑_{i=1}^{N-1}\ i=Ω(N^2)$

กรรมวิธีของ splaying คล้ายกันกับการหมุนโนดที่กล่าวมาข้างบนนั้น โดยยังคงใช้การหมุนโนดจากระดับข้างล่างของทรีขึ้นมาตามเส้นการเข้าถึงโนด ให้ X เป็นโนด (ที่ไม่ใช่โนดราก) บนเส้นทางการเข้าถึงที่เราจะทำการหมุน

ถ้าโนดที่เป็นโนดแม่ (parent) ของโนด X เป็นโนดรากของทรีก็ให้ทำการหมุนโนด X และโนดรากและนี่ก็จะเป็นการหมุนสุดท้ายที่เกิดขึ้นบนเส้นทางการเข้าถึงโนดดังกล่าว

ถ้าโนดแม่ของ X ไม่ใช่โนดราก ก็หมายความว่าโนด X มีทั้ง parent (P) และ grandparent (G) ทำให้เกิดกรณีที่ต้องพิจารณาเพื่อการหมุนโนดขึ้น 2 กรณี (รวมกับกรณีสมมาตรของมันด้วย)

• กรณีแรก คือ กรณี zig-zag (ดูรูปที่ 4.44) กรณีนี้โนด X เป็นโนดลูกตัวขวา (right child) และโนด P เป็นโนดลูกตัวซ้าย (left child) (หรือเป็นในทางตรงข้ามกัน) เราจะทำการหมุนโนดด้วยวิธี double rotation เช่นเดียวกับที่ทำ double rotation ใน AVL
• มิฉะนั้นก็จะเป็นกรณีที่สอง คือ กรณี zig-zig: ในกรณีนี้ ทั้งโนด X และโนด P เป็นโนดลูกตัวซ้ายหรือโนดลูกตัวขวาเหมือน ๆ กันทั้งสองโนด กรณีนี้เราก็จะทำการปรับเปลี่ยนทรีที่อยู่ด้านซ้ายมือของรูปที่ 4.45 ไปเป็นทรีที่อยู่ด้านขวามือของรูป

จากทรีเดียวกับทรีตัวอย่างที่ผ่านมาดังนี้

การ splay ครั้งแรกเกิดขึ้นที่ k1 ซึ่งเป็นแบบ zig-zag ดังนั้นจึงเป็น double rotation ระหว่างโนด k1, k2 และโนด k3 แบบเดียวกับที่ใช้กับ AVL ได้ผลเป็นทรีข้างล่างนี้

ขั้นต่อไปเป็นการหมุนแบบ zig-zig ที่โนด k1, k4 และ k5 จะได้ทรีดังนี้

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

รูปที่ 4.46 แสดงตัวอย่างของทรีเมื่อมีการบรรจุค่า 1, 2, 3, …, N ลงในทรีว่างเริ่มต้นซึ่งมี running time เป็น $O(N)$ และแสดงผลที่ได้เมื่อมีการเข้าถึงและทำการ splay โนด 1 ซึ่งใช้เวลา N – 1 หน่วย จากนั้นการเข้าถึงโนดข้อมูล 2 จะใช้เวลาเป็น N/2 หน่วยเวลาแทนที่จะต้องใช้ N – 2 หน่วยเวลา

เมื่อเข้าถึงโนด 2 ก็จะทำให้โนดอื่น ๆ ขึ้นมาอยู่ที่ระดับ N/4 จากโนดราก และถ้าทำซ้ำ ๆ ก็จะทำให้ความลึกของทรีเหลือประมาณ log N (ทรีที่มี N = 7 เป็นขนาดที่เล็กเกินไปจะเห็นความเปลี่ยนแปลงนี้) รูปที่ 4.47 ถึง 4.55 แสดงตัวอย่างของการเข้าถึงโนด 1 ถึง 9 ตามลำดับของทรีที่มีจำนวนโนด 32 โนด โดยที่ทรีเริ่มต้นมีเฉพาะโนดลูกตัวซ้ายเท่านั้น

เพื่อที่จะลบค่า (deletion) เราจะต้องเข้าถึงโนดที่จะลบซึ่งทำให้โนดนั้นถูกเลื่อนขึ้นมาอยู่ที่รากแล้วจึงทำการลบ และเมื่อทำการลบโนด (ซึ่งขณะนี้อยู่ที่ตำแหน่งราก) ก็จะทำให้ทรีที่เหลือถูกแบ่งเป็น 2 ทรีย่อยโดยในที่นี้คือ TL และ TR (ทรีย่อยซ้ายและทรีย่อยขวา) จากนั้นจะใช้การหาค่าที่มากที่สุดในทรีย่อยซ้าย TL (ซึ่งสามารถทำได้ง่าย), และทำการหมุนโนดโดยหมุนค่านี้ไปที่รากของ TL, จะได้ TL ที่รากของมันไม่มีลูกทางขวา (right child) เราจบการทำงานด้วยการนำ TR มาเชื่อมต่อให้เป็นลูกทางขวา (right child) ของมัน

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

ตัวอย่าง โปรแกรม splay tree