ผลต่างระหว่างรุ่นของ "204512/บรรยาย 3"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 20 รุ่นระหว่างกลางโดยผู้ใช้ 7 คน)
แถว 1: แถว 1:
 +
{{หัวคำบรรยาย|204512}}
 +
----
 +
'''จดบันทึกคำบรรยายโดย:'''
 +
:นางสาวพัชรินทร์  โกศลโพธิสกุล   รหัส : 50653831
 +
:นายศิวพงษ์  นิยมพานิช   รหัส : 50653948
 +
----
 
== ความรู้เบื้องต้น ==
 
== ความรู้เบื้องต้น ==
 
Tree เป็นโครงสร้างชนิดไม่เชิงเส้น (Non-linear) มีลักษณะเป็น recursive ประกอบไปด้วยสมาชิกที่เรียกว่า Node และมีเส้นที่เชื่อมระหว่าง Node ที่เรียกว่า branch คำสำคัญที่เกี่ยวกับ Tree มีดังนี้
 
Tree เป็นโครงสร้างชนิดไม่เชิงเส้น (Non-linear) มีลักษณะเป็น recursive ประกอบไปด้วยสมาชิกที่เรียกว่า Node และมีเส้นที่เชื่อมระหว่าง Node ที่เรียกว่า branch คำสำคัญที่เกี่ยวกับ Tree มีดังนี้
แถว 77: แถว 83:
 
<center>รูปที่7 แสดงการ Double Rotation เมื่อมีการใส่ข้อมูลเข้าไป </center>
 
<center>รูปที่7 แสดงการ Double Rotation เมื่อมีการใส่ข้อมูลเข้าไป </center>
  
== Delete Tree ==
+
== Amortized Analysis ==
การลบ Node ในต้นไม้มีวิธีการลบแบบหนึ่งที่เรียกว่า Lazy Delete มีวิธีการทำงานคือจะใช้การ Mark โหนดแทนการลบโหนดออกจากต้นไม้ โดยวิธีนี้จะเกิดปัญหาเมื่อมีการลบและ insert โหนดหลายๆครั้ง ส่งผลให้ต้นไม้มีความสูงมาก และไม่สามารถทำงานได้ภายในเวลา O(log n) เมื่อ N ≤ 2n <br />
+
เป็นการคิดการชาร์จเวลาการทำงานในการทำงานในส่วนกิจกรรมย่อยๆ เพื่อนำมาใช้ทดแทนกิจกรรมอื่นในภายหลัง ยกตัวอย่างเช่น การทำงานกับ Variable Array เมื่อ insert ข้อมูลเต็ม array แล้ว เราต้องทำการเพิ่ม array แล้วทำการคัดลอก array เก่า
 +
 
 +
สมมุติมี array 1 ชุดเมื่อมีการเต็มข้อมูลเต็มแล้วก็จะมีการจอง array ใหม่แล้วคัดลอกข้อมูลของเดิมมาเก็บที่ไหม่ ดังนั้นถ้ามีข้อมูล n ตัว จะต้องใช้เวลาถึง O(n&sup2;)
 +
 
 +
<center>[[ภาพ:Amor_1.jpg]]</center>
 +
 
 +
<center> รูปที่7 แสดงการใช้งาน Array แบบปรกติ </center>
 +
 
 +
 
 +
แต่เมื่อเราใช้การคิดเวลาแบบ Amortized แล้ว เราสามารถคิดแบบเวลาที่ทำทั้งหมด โดยใช้เวลาไม่เกินเท่าไร ซึ่งมีการคิดเวลาล่วงหน้าและมีการจองพื้นที่ array เป็นสองเท่าจากข้อมูลที่มีอยู่
 +
 
 +
<center>[[ภาพ:Amor_2.jpg]]</center>
 +
 
 +
<center> รูปที่8 แสดงการใช้งาน Array แบบ Amortized </center>
 +
 
 +
 
 +
ซึ่งสามารถสรุปเป็นกราฟได้ดังภาพ
 +
 
 +
<center>[[ภาพ:Amor_3.jpg]]</center>
 +
 
 +
<center> รูปที่9 แสดงเวลาที่ใช้งานในแบบต่างๆ </center>
 +
 
 +
 
 +
Claim: Variable array เมื่อมีการเพิ่มข้อมูลไป m ครั้งจะใช้เวลาทำงาน O(m) โดย amortized running time ของการเพิ่มข้อมูลคือ O(1)
 +
 
 +
Proof: ในการคิดเวลาการทำงานล่วงหน้าของการเพิ่มข้อมูลแต่ละคั้งคิดเป็น 3 หน่วย โดยถ้าในเวลาที่ทำการเพิ่มข้อมูลโดยไม่มีการเพิ่มขนาดของ array จะมีการใช้เวลาในการทำงานจริง 1 หน่วย ซึ่งดังนั้นจะเหลือเวลาอีก 2 หน่วย แต่ในกรณีที่มีการขยายขนาดของ array
 +
จาก 2i เป็น 2i+1 จะมีการเพิ่มข้อมูลที่ไม่มีการ array 2i-1 
 +
 
 +
<center>[[ภาพ:Amor_4.jpg]]</center>
 +
 
 +
<center> รูปที่9 แสดงเวลาที่ใช้งานในแบบต่างๆ </center>
 +
 
 +
 
 +
จะใช้เวลา 2 x 2i-1 = 2i 
 +
ดังนั้น การเพิ่มข้อมูล m ครั้ง ใช้เวลา 3m = O(m) หน่วย
  
[[ภาพ:Ld1.jpg]]
+
=== Delete Tree ===
 +
การลบ Node ในต้นไม้มีวิธีการลบแบบหนึ่งที่เรียกว่า Lazy Delete มีวิธีการทำงานคือจะใช้การ Mark โหนดแทนการลบโหนดออกจากต้นไม้ โดยวิธีนี้จะเกิดปัญหาเมื่อมีการลบและ insert โหนดหลายๆครั้ง ส่งผลให้ต้นไม้มีความสูงมาก และไม่สามารถทำงานได้ภายในเวลา O(log n) เมื่อ N ≤ 2n ; N คือโหนดที่ถูกลบ <br />
 +
 
 +
<center>[[ภาพ:Ld1.jpg]]</center>
  
 
ในกรณีที่ N > 2n จะต้องมีการสร้างต้นไม้ขึ้นมาใหม่ โดยจะนำ Data ออกมาทั้งหมดและ Insert เข้าไปใหม่ ใช้เวลาทำงาน O(n) <br />
 
ในกรณีที่ N > 2n จะต้องมีการสร้างต้นไม้ขึ้นมาใหม่ โดยจะนำ Data ออกมาทั้งหมดและ Insert เข้าไปใหม่ ใช้เวลาทำงาน O(n) <br />
 
จากข้างต้น กราฟในการทำงานของ Lazy Delete จะ peak เป็นช่วงๆ ซึ่งช่วงที่ peak จะเป็นช่วงที่มีการลบโหนด และเวลาในการทำงานจะคิดเฉลี่ยตามแบบการทำงานของ Amortized Analysis<br />
 
จากข้างต้น กราฟในการทำงานของ Lazy Delete จะ peak เป็นช่วงๆ ซึ่งช่วงที่ peak จะเป็นช่วงที่มีการลบโหนด และเวลาในการทำงานจะคิดเฉลี่ยตามแบบการทำงานของ Amortized Analysis<br />
  
== Amortized Analysis ==
+
== Scapegoat Tree ==
เป็นการคิดการชาร์จเวลาการทำงานในการทำงานในส่วนกิจกรรมย่อยๆ เพื่อนำมาใช้ทดแทนกิจกรรมอื่นในภายหลัง ยกตัวอย่างเช่น การทำงานกับ Variable Array เมื่อ insert ข้อมูลเต็ม array แล้ว เราต้องทำการเพิ่ม array แล้วทำการคัดลอก array เก่า
+
จากแนวคิดของ amortized analysis เราสามารถวิเคราะห์ต้นไม้ที่เรียกว่า Scapegoat โดยที่ AVL Tree นั้นรับประกันว่าการทำงานในแต่ละครั้งจะมีเวลาการทำงานไม่เกิน O(n) แต่ใน Scapegoat Tree จะมีเงื่อนไขที่แตกต่างไป
 +
 
 +
สำหรับ node ''v'' ในต้นไม้, ให้ <math>T_v</math> แทน subtree ที่มี Root เป็น ''v'' ให้ ''left''(''v'') แทนลูกด้านซ้ายของ ''v'', ''right''(''v'') แทนลูกด้านขวาของ v และ <math>|T_v|</math>
 +
แทนจำนวนโหนดใน <math>T_v</math>
 +
 
 +
เงื่อนไขความสมดุลย์ของ scapegoat tree เป็นดังนี้
 +
 
 +
{{กล่องฟ้า|'''Condition:''' สำหรับทุก ๆ โหนด ''v'',
 +
<center><math>|T_{left(v)}| \leq 2|T_{right(v)}|</math></center>
 +
และ
 +
<center><math>|T_{right(v)}| \leq 2|T_{left(v)}|</math></center>
 +
}}
 +
 
 +
เงื่อนไขดังกล่าว รับประกันความสูงของต้นไม้ ดังที่แสดงใน claim ต่อไปนี้
 +
 
 +
{{กล่องฟ้า|'''Claim:''' Scapegoat tree ที่มี n โหนดจะมีความลึกไม่เกิน O(log n)}}
 +
 
 +
Operation: Insert node
 +
การ Insert node ใหม่ใส่ใน Scapgoat trees จะมีลักษณะการ Insert ตามปรกติเหมือน Binary Search trees ซึ่งเป็นการใส่ node ใหม่ลงไปใน tree แบบ inorder ก็จะได้ลำดับที่เรียงแล้วในเวลา linear time
 +
แต่เมื่อมีการ insert node ใหม่เข้าไปใน Scapgoat trees เรื่อยๆ แล้วถ้าพบ node v ที่ h(v) >  log |v| จะต้องทำการ rebuild subtrees ที่ v ใหม่โดยใช้เวลาในการ rebuild O(|v|)
 +
 
 +
<center>[[ภาพ:Sc1.JPG]]</center>
 +
 
 +
ถ้าหาก Scapgoat trees นั้นไม่ balance ที่ node ที่อยู่ด้านบนของ node v อีกก็จะต้องเสีย time มาก ในการที่จะกลับไป balance ที่ node ด้านบนต่อ ซึ่งทำให้มี cost ของการ balance สูงมาก เราจะ amortize ไปที่การ insert หลายๆ ครั้งเพื่อให้มี cost ดีที่สุด
 +
 
 +
จากการ Amortize Analysis ที่ผ่านมา
 +
Operation: Insert node
 +
การ Insert node ใหม่ใส่ใน Scapgoat trees จะมีลักษณะการ Insert ตามปรกติเหมือน Binary Search trees ซึ่งเป็นการใส่ node ใหม่ลงไปใน tree แบบ inorder ก็จะได้ลำดับที่เรียงแล้วในเวลา linear time
 +
แต่เมื่อมีการ insert node ใหม่เข้าไปใน Scapgoat trees เรื่อยๆ แล้วถ้าพบ node v ที่ h(v) >  log |v| จะต้องทำการ rebuild subtrees ที่ v ใหม่โดยใช้เวลาในการ rebuild O(|v|)
 +
 
 +
<center>[[ภาพ:Sc2.JPG]]</center>
 +
 
 +
ถ้าหาก Scapgoat trees นั้นไม่ balance ที่ node ที่อยู่ด้านบนของ node v อีกก็จะต้องเสีย time มาก ในการที่จะกลับไป balance ที่ node ด้านบนต่อ ซึ่งทำให้มี cost ของการ balance สูงมาก เราจะ amortize ไปที่การ insert หลายๆ ครั้งเพื่อให้มี cost ดีที่สุด
 +
 
 +
จากการ Amortize Analysis ที่ผ่านมา
 +
 
 +
<center>[[ภาพ:Sc3.JPG]]</center>
 +
 
 +
ถ้าที่ node v
 +
 
 +
<center>[[ภาพ:Sc4.JPG]]</center>
 +
 
 +
Claim: ก่อนการ rebuild ใดๆ ที่node v จะมีการ insert เข้าไปใน subtree ทื่node v ไม่น้อยกว่า  (|v|) ครั้ง
 +
 
 +
 
 +
ถ้าต้องการ insert เข้าไป ต้องเตรียม amortized cost O(1) ต่อการ insert 1 ครั้ง ดังนั้นการ rebuild ที่ |v| ครั้ง เราสามารถ charge O(1) ไปที่ node ที่ถูก insert เข้าไปใน subtree ที่ node v เป็น root ได้
 +
สังเกตว่า node ใดๆ ที่ถูก insert ไปจะโดน charge ไม่เกิน  log n ครั้ง ดังนั้น cost ของการ insert + charge ของการ rebuild เท่ากับ O( log n ) ซึ่งเท่ากับ O( log n ) นั่นเอง
 +
 
 +
Prof of Claim:
 +
 
 +
<center>[[ภาพ:Sc5.JPG]]</center><br>
 +
<center>[[ภาพ:Sc6.JPG]]</center>
 +
 
 +
ดังนั้น
  
สมมุติมี array 1 ชุดเมื่อมีการเต็มข้อมูลเต็มแล้วก็จะมีการจอง array ใหม่แล้วคัดลอกข้อมูลของเดิมมาเก็บที่ไหม่ ดังนั้นถ้ามีข้อมูล n ตัว จะต้องใช้เวลาถึง O(n2)
+
<center>[[ภาพ:Sc7.JPG]]</center>
  
<center>[[ภาพ:Amor_1.jpg]]</center>
+
เราจะได้ข้อสรุปว่า เมื่อเรา rebuild ครั้งสุดท้ายแล้วจำนวน node ของ subtree ทางซ้ายและจำนวน node ของ subtree ทางขวาต่างกันอย่างมาก 1 node
  
<center> รูปที่7 แสดงการใช้งาน Array แบบปรกติ </center>
+
<center>[[ภาพ:Sc8.JPG]]</center>
  
 
== ทบทวนความรู้เรื่อง Experiment, Expected value, Random variable ==
 
== ทบทวนความรู้เรื่อง Experiment, Expected value, Random variable ==

รุ่นแก้ไขปัจจุบันเมื่อ 17:16, 25 กันยายน 2550

บันทึกคำบรรยายวิชา 204512 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง


จดบันทึกคำบรรยายโดย:

นางสาวพัชรินทร์ โกศลโพธิสกุล   รหัส : 50653831
นายศิวพงษ์ นิยมพานิช   รหัส : 50653948

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

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

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 ได้ดังนี้

Bst 1.jpg


รูปที่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

Bst 2.jpg
รูปที่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)

---*
จะสังเกตได้ว่าฟังก์ชันดังกล่าวมีขนาดเป็น 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 จึงใช้การกระทำที่เรียกว่า “การหมุนทางขวา” เพื่อทำให้ตรงตามเงื่อนไขดังกล่าว

Right.jpg


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


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

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

Left.jpg


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


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

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

การ Double Rotation

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

Double1.jpg


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


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

Double4.jpg


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

Amortized Analysis

เป็นการคิดการชาร์จเวลาการทำงานในการทำงานในส่วนกิจกรรมย่อยๆ เพื่อนำมาใช้ทดแทนกิจกรรมอื่นในภายหลัง ยกตัวอย่างเช่น การทำงานกับ Variable Array เมื่อ insert ข้อมูลเต็ม array แล้ว เราต้องทำการเพิ่ม array แล้วทำการคัดลอก array เก่า

สมมุติมี array 1 ชุดเมื่อมีการเต็มข้อมูลเต็มแล้วก็จะมีการจอง array ใหม่แล้วคัดลอกข้อมูลของเดิมมาเก็บที่ไหม่ ดังนั้นถ้ามีข้อมูล n ตัว จะต้องใช้เวลาถึง O(n²)

Amor 1.jpg
รูปที่7 แสดงการใช้งาน Array แบบปรกติ


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

Amor 2.jpg
รูปที่8 แสดงการใช้งาน Array แบบ Amortized


ซึ่งสามารถสรุปเป็นกราฟได้ดังภาพ

Amor 3.jpg
รูปที่9 แสดงเวลาที่ใช้งานในแบบต่างๆ


Claim: Variable array เมื่อมีการเพิ่มข้อมูลไป m ครั้งจะใช้เวลาทำงาน O(m) โดย amortized running time ของการเพิ่มข้อมูลคือ O(1)

Proof: ในการคิดเวลาการทำงานล่วงหน้าของการเพิ่มข้อมูลแต่ละคั้งคิดเป็น 3 หน่วย โดยถ้าในเวลาที่ทำการเพิ่มข้อมูลโดยไม่มีการเพิ่มขนาดของ array จะมีการใช้เวลาในการทำงานจริง 1 หน่วย ซึ่งดังนั้นจะเหลือเวลาอีก 2 หน่วย แต่ในกรณีที่มีการขยายขนาดของ array จาก 2i เป็น 2i+1 จะมีการเพิ่มข้อมูลที่ไม่มีการ array 2i-1

Amor 4.jpg
รูปที่9 แสดงเวลาที่ใช้งานในแบบต่างๆ


จะใช้เวลา 2 x 2i-1 = 2i ดังนั้น การเพิ่มข้อมูล m ครั้ง ใช้เวลา 3m = O(m) หน่วย

Delete Tree

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

Ld1.jpg

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

Scapegoat Tree

จากแนวคิดของ amortized analysis เราสามารถวิเคราะห์ต้นไม้ที่เรียกว่า Scapegoat โดยที่ AVL Tree นั้นรับประกันว่าการทำงานในแต่ละครั้งจะมีเวลาการทำงานไม่เกิน O(n) แต่ใน Scapegoat Tree จะมีเงื่อนไขที่แตกต่างไป

สำหรับ node v ในต้นไม้, ให้ แทน subtree ที่มี Root เป็น v ให้ left(v) แทนลูกด้านซ้ายของ v, right(v) แทนลูกด้านขวาของ v และ แทนจำนวนโหนดใน

เงื่อนไขความสมดุลย์ของ scapegoat tree เป็นดังนี้

Condition: สำหรับทุก ๆ โหนด v,

และ

เงื่อนไขดังกล่าว รับประกันความสูงของต้นไม้ ดังที่แสดงใน claim ต่อไปนี้

Claim: Scapegoat tree ที่มี n โหนดจะมีความลึกไม่เกิน O(log n)

Operation: Insert node การ Insert node ใหม่ใส่ใน Scapgoat trees จะมีลักษณะการ Insert ตามปรกติเหมือน Binary Search trees ซึ่งเป็นการใส่ node ใหม่ลงไปใน tree แบบ inorder ก็จะได้ลำดับที่เรียงแล้วในเวลา linear time แต่เมื่อมีการ insert node ใหม่เข้าไปใน Scapgoat trees เรื่อยๆ แล้วถ้าพบ node v ที่ h(v) > log |v| จะต้องทำการ rebuild subtrees ที่ v ใหม่โดยใช้เวลาในการ rebuild O(|v|)

Sc1.JPG

ถ้าหาก Scapgoat trees นั้นไม่ balance ที่ node ที่อยู่ด้านบนของ node v อีกก็จะต้องเสีย time มาก ในการที่จะกลับไป balance ที่ node ด้านบนต่อ ซึ่งทำให้มี cost ของการ balance สูงมาก เราจะ amortize ไปที่การ insert หลายๆ ครั้งเพื่อให้มี cost ดีที่สุด

จากการ Amortize Analysis ที่ผ่านมา Operation: Insert node การ Insert node ใหม่ใส่ใน Scapgoat trees จะมีลักษณะการ Insert ตามปรกติเหมือน Binary Search trees ซึ่งเป็นการใส่ node ใหม่ลงไปใน tree แบบ inorder ก็จะได้ลำดับที่เรียงแล้วในเวลา linear time แต่เมื่อมีการ insert node ใหม่เข้าไปใน Scapgoat trees เรื่อยๆ แล้วถ้าพบ node v ที่ h(v) > log |v| จะต้องทำการ rebuild subtrees ที่ v ใหม่โดยใช้เวลาในการ rebuild O(|v|)

Sc2.JPG

ถ้าหาก Scapgoat trees นั้นไม่ balance ที่ node ที่อยู่ด้านบนของ node v อีกก็จะต้องเสีย time มาก ในการที่จะกลับไป balance ที่ node ด้านบนต่อ ซึ่งทำให้มี cost ของการ balance สูงมาก เราจะ amortize ไปที่การ insert หลายๆ ครั้งเพื่อให้มี cost ดีที่สุด

จากการ Amortize Analysis ที่ผ่านมา

Sc3.JPG

ถ้าที่ node v

Sc4.JPG

Claim: ก่อนการ rebuild ใดๆ ที่node v จะมีการ insert เข้าไปใน subtree ทื่node v ไม่น้อยกว่า (|v|) ครั้ง


ถ้าต้องการ insert เข้าไป ต้องเตรียม amortized cost O(1) ต่อการ insert 1 ครั้ง ดังนั้นการ rebuild ที่ |v| ครั้ง เราสามารถ charge O(1) ไปที่ node ที่ถูก insert เข้าไปใน subtree ที่ node v เป็น root ได้ สังเกตว่า node ใดๆ ที่ถูก insert ไปจะโดน charge ไม่เกิน log n ครั้ง ดังนั้น cost ของการ insert + charge ของการ rebuild เท่ากับ O( log n ) ซึ่งเท่ากับ O( log n ) นั่นเอง

Prof of Claim:

Sc5.JPG


Sc6.JPG

ดังนั้น

Sc7.JPG

เราจะได้ข้อสรุปว่า เมื่อเรา rebuild ครั้งสุดท้ายแล้วจำนวน node ของ subtree ทางซ้ายและจำนวน node ของ subtree ทางขวาต่างกันอย่างมาก 1 node

Sc8.JPG

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

Experiment

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

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

2. สำหรับ Algo03.gif
3. สำหรับ Algo04.gif ที่ disjoint กัน Algo05.gif

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

Algo06.gif

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

Algo07.gif

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

Algo09.gif

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

Algo10.gif

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

Algo10.gif