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 เมื่อมีการใส่ข้อมูลเข้าไป

Delete Tree

การลบ Node ในต้นไม้มีวิธีการลบแบบหนึ่งที่เรียกว่า Lazy Delete มีวิธีการทำงานคือจะใช้การ Mark โหนดแทนการลบโหนดออกจากต้นไม้ โดยวิธีนี้จะเกิดปัญหาเมื่อมีการลบและ insert โหนดหลายๆครั้ง ส่งผลให้ต้นไม้มีความสูงมาก และไม่สามารถทำงานได้ภายในเวลา O(log n) เมื่อ N ≤ 2n

ในกรณีที่ N > 2n จะต้องมีการสร้างต้นไม้ขึ้นมาใหม่ โดยจะนำ Data ออกมาทั้งหมดและ Insert เข้าไปใหม่ ใช้เวลาทำงาน O(n)
จากข้างต้น กราฟในการทำงานของ Lazy Delete จะ peak เป็นช่วงๆ ซึ่งช่วงที่ peak จะเป็นช่วงที่มีการลบโหนด และเวลาในการทำงานจะคิดเฉลี่ยตามแบบการทำงานของ Amortized Analysis

Amortized Analysis

เป็นการคิดคำนวณเวลาเฉลี่ยที่ใช้ในการทำงานแต่ละครั้ง

ทบทวนความรู้เรื่อง Experiment, Expected value, Random variable

Experiment

• Event คือ เหตุการณ์ที่สนใจ
  
• Outcome คือ ผลลัพธ์ของเหตุการณ์ที่สนใจเป็น sub set ของ Sample space
  
• Sample space คือ set ของ outcome ที่เป็นไปได้
  
• Probability คือ ความน่าจะเป็น หมายถึง โอกาสที่จะเกิดเหตุการณ์ที่สนใจจากการทดลองสุ่มหนึ่งๆ เป็นจำนวนหรือค่าที่ไม่มีหน่วย เขียนแทนด้วย Pr(?) โดยที่ ? แทนด้วยชื่อของเหตุการณ์ที่สนใจ เช่น Pr [x=5] คือ ความน่าจะเป็นที่ x=5
  

สำหรับ โดยที่ A แทน Event เซตของ outcome จะได้ว่า
1.

2. สำหรับ
3. สำหรับ ที่ disjoint กัน

ตัวอย่าง สมมุติให้มีถัง 3 ถัง

ให้ที่ถังแรกไม่มีลูกบอลหล่นลงไปเลย หาความน่าจะเป็น(Pr) ที่จะไม่มีลูกบอลหล่นลงในถังแรก
Ai คือ event ที่ลูกบอลลูกที่ i ไม่หล่นลงในถังใบแรก

===Random Variable (ตัวแปรสุ่ม)=== คือ function หรือตัวแปรที่มีค่าขึ้นกับผลลัพธ์ (sample space) โดยจะรู้ค่าหลังจากการทดลอง
===Expected value (ค่าคาดหวัง)=== คือค่าเฉลี่ย โดยเฉลี่ยมีค่าเท่าไหร่ weight ตามความน่าจะเป็นที่จะได้ค่านั้น แทนด้วย E
นิยาม ตัวแปรสุ่ม X,
ตัวอย่าง ถ้ามีถัง 3 ถัง บอล 2 ลูกสีดำ และสีขาว

หา Pr[X = i] จะได้ว่า

เอามาเป็นค่า weight ในการคำนวณ

---