204512/บรรยาย 3

ความรู้เบื้องต้น

Tree เป็นโครงสร้างชนิดไม่เชิงเส้น (Non-linear) มีลักษณะเป็น recursive ประกอบไปด้วยสมาชิกที่เรียกว่า Node และมีเส้นที่เชื่อมระหว่าง Node ที่เรียกว่า branch คำสำคัญที่เกี่ยวกับ Tree มีดังนี้

Root Node: A	Sibling Node: {B, E, F}, {C, D}, {G, H, I}
Parents Node: A, B, F	Leaves Node: C, D, E, G, H, I
Child Node: B, E, F, C, D, G, H, I	Internal Node: B, F

• Root Node คือ โหนดที่อยู่บนสุดของต้นไม้
  
• Leaf Node คือ โหนดที่ไม่มีลูกหรือโหนดอื่นต่อ เรียกอีกอย่างหนึ่งว่า External Node
  
• Internal Node คือ โหนดที่ไม่ใช่ Root และ Leaf Node
  
• Depth คือ ความยาวจาก Root node ถึง Node ที่สนใจ
  
• Height คือ ความยาวจาก Node ที่สนใจถึง Leaf Node ที่ลึกที่สุดที่มี Node ที่สนใจเป็น Parent
  

Binary Search Tree

Binary Search Tree คือ Data Structure ที่ define แบบ Recursive โดยขั้นตอนวิธีการทำงานที่สำคัญของ Binary Tree จะสนับสนุนการทำงานดังต่อไปนี้

• Find (key)
• Insert (key)
• Delete (key)

ซึ่งเวลาที่ใช้ในการค้นหานั้นจะขึ้นอยู่กับความสูงของต้นไม้ โดยถ้ามีข้อมูล n ตัวความสูงของต้นไม้จะไม่ลึกไปกว่า O(log n) ถ้าสูงกว่าจะทำให้เกิด Worse-case
สมมติว่ามี data 1,2,8,3,7,5,10,20,12 เขียนเป็น Binary Search Tree ได้ดังนี้

รูปที่1 ตัวอย่าง Binary Search Tree เมื่อมีข้อมูล {1,2,8,3,7,5,10,20,12}

AVL Tree

AVL (Adelson-Velskii and Landis) tree คือ binary search tree ที่มีเงื่อนไขของความสมดุล (Balance Condition) โดยเงื่อนไขดังกล่าวคือ
Condition: ในทุกๆ โหนด ความสูงของ subtree ทางด้ายซ้ายและด้านขวาต่างกันไม่เกิน 1 โดยที่ให้ N(k) แทนจำนวนโหนดที่น้อยที่สุดใน AVL Tree ที่มีความสูง k

รูปที่2 แสดงเงื่อนไปของ AVL Tree

จากเงื่อนไขของ AVL Tree จะสรุปได้
N(1) = 1, N(2) = 2
N(k) = N(k-1) + N(k-2) + 1
จะสังเกตได้ว่ามีลักษณะเป็น Fibonacci แต่มีการบวก 1 เข้ามาด้วย
จากสมการข้างต้น
N(k) = N(k-1) + N(k-2) + 1
N(k) = N(k-2) + N(k-3) + N(k-2) + 1
≥ 2N(k-2)
≥ ${(sqr2)^{k}}$
≥ ${2^{k/2}}$ ---*
จะสังเกตได้ว่าฟังก์ชันดังกล่าวมีขนาดเป็น Exponential ใน k
สรุป: AVL Tree ที่มี n โหนดจะมีความสูง O(log n)

การหมุนของ AVL Tree

การหมุน (Rotation) ของ AVL Tree กระทำเพื่อให้ต้นไม่ที่ไม่อยู่ในเงื่อนไขของ AVL Tree กลับเข้ามาอยู่ในเงื่อนไข ซึ่งมีรูปแบบการทำงานดังนี้

• Single Rotation
  • การหมุนทางขวา (Right Rotation)
  • การหมุนทางซ้าย (Left Rotation)
• Double Rotation

การหมุนทางขวา (Right Rotation)

จะกระทำเมื่อทางด้านซ้ายของต้นไม้มีความสุงกว่าด้านขวาเกิน 1 ซึ่งไม่ตรงตามเงื่อนไขของ AVL Tree จึงใช้การกระทำที่เรียกว่า “การหมุนทางขวา” เพื่อทำให้ตรงตามเงื่อนไขดังกล่าว

รูปที่3 แสดงการหมุนทางขวา (Right Rotation)

การหมุนทางซ้าย (Left Rotation)

ในทางกลับกันถ้าหากทางด้านขวาของต้นไม้มีความสูงไม่สัมพันธ์กับเงื่อนไขของ AVL Tree จะทำการหมุนทางซ้ายเพื่อให้ต้นไม่กลับมาสมดุล

รูปที่4 แสดงการหมุนทางซ้าย (Left Rotation)

ตัวอย่าง Single Rotation โดยการใส่ตัวเลข 1 – 7 ตามลำดับ

รูปที่5 แสดงการ Single Rotation เมื่อมีการใส่ข้อมูล {1,2,3,4,5,6,7}

การ Double Rotation

ในบางครั้งการหมุนสามารถทำการหมุนได้หลาย ครั้งเช่น เมื่อทำการหมุนซ้ายแล้วทำการหมุนขวา หรือทำหารหมุนขวาแล้วหมุนซ้าย โดยอาศัยเทคนิคการหมุนทางซ้ายและทางขวาร่วมกัน

รูปที่6 แสดงการ Double Rotation

ตัวอย่าง Double Rotation โดยการใส่ตัวเลข 14 เข้าไปในต้นไม้

รูปที่7 แสดงการ Double Rotation เมื่อมีการใส่ข้อมูลเข้าไป