204512/บรรยาย 3 - ประวัติรุ่นแก้ไข

Patcharin เมื่อ 17:16, 25 กันยายน 2550

2007-09-25T17:16:59Z

Jittat เมื่อ 05:12, 9 สิงหาคม 2550

2007-08-09T05:12:28Z

203.185.129.244: /* Amortized Analysis */

2007-07-30T16:58:30Z

Amortized Analysis

158.108.135.236: /* Scapegoat Tree */

2007-07-19T14:11:39Z

Scapegoat Tree

158.108.135.236 เมื่อ 14:08, 19 กรกฎาคม 2550

2007-07-19T14:08:35Z

158.108.135.236: /* Scapegoat Tree */

2007-07-19T14:00:54Z

Scapegoat Tree

158.108.135.236: /* Scapegoat Tree */

2007-07-19T13:44:40Z

Scapegoat Tree

158.108.131.4: /* Scapegoat Tree */

2007-07-19T13:19:18Z

Scapegoat Tree

158.108.131.4: /* Scapegoat Tree */

2007-07-19T13:18:19Z

Scapegoat Tree

158.108.131.4: /* Delete Tree */

2007-07-19T12:00:37Z

Delete Tree

@@ แถว 1: / แถว 1: @@
 {{หัวคำบรรยาย|204512}}
-'''จดบันทึกคำบรรยายโดย:''' ''(กรุณาใส่ด้วย)''
+----
 == ความรู้เบื้องต้น ==
 Tree เป็นโครงสร้างชนิดไม่เชิงเส้น (Non-linear) มีลักษณะเป็น recursive ประกอบไปด้วยสมาชิกที่เรียกว่า Node และมีเส้นที่เชื่อมระหว่าง Node ที่เรียกว่า branch คำสำคัญที่เกี่ยวกับ Tree มีดังนี้

@@ แถว 1: / แถว 1: @@
 {{หัวคำบรรยาย|204512}}
 == ความรู้เบื้องต้น ==
 Tree เป็นโครงสร้างชนิดไม่เชิงเส้น (Non-linear) มีลักษณะเป็น recursive ประกอบไปด้วยสมาชิกที่เรียกว่า Node และมีเส้นที่เชื่อมระหว่าง Node ที่เรียกว่า branch คำสำคัญที่เกี่ยวกับ Tree มีดังนี้

@@ แถว 81: / แถว 81: @@
 เป็นการคิดการชาร์จเวลาการทำงานในการทำงานในส่วนกิจกรรมย่อยๆ เพื่อนำมาใช้ทดแทนกิจกรรมอื่นในภายหลัง ยกตัวอย่างเช่น การทำงานกับ Variable Array เมื่อ insert ข้อมูลเต็ม array แล้ว เราต้องทำการเพิ่ม array แล้วทำการคัดลอก array เก่า
-สมมุติมี array 1 ชุดเมื่อมีการเต็มข้อมูลเต็มแล้วก็จะมีการจอง array ใหม่แล้วคัดลอกข้อมูลของเดิมมาเก็บที่ไหม่ ดังนั้นถ้ามีข้อมูล n ตัว จะต้องใช้เวลาถึง O(n2)
+สมมุติมี array 1 ชุดเมื่อมีการเต็มข้อมูลเต็มแล้วก็จะมีการจอง array ใหม่แล้วคัดลอกข้อมูลของเดิมมาเก็บที่ไหม่ ดังนั้นถ้ามีข้อมูล n ตัว จะต้องใช้เวลาถึง O(n&sup2;)
 <center>[[ภาพ:Amor_1.jpg]]</center>

@@ แถว 131: / แถว 131: @@
 เงื่อนไขความสมดุลย์ของ scapegoat tree เป็นดังนี้
-{{กล่องเทา|'''Condition:''' สำหรับทุก ๆ โหนด ''v'',
+{{กล่องฟ้า|'''Condition:''' สำหรับทุก ๆ โหนด ''v'',
 <center><math>|T_{left(v)}| \leq 2|T_{right(v)}|</math></center>
 และ
@@ แถว 139: / แถว 139: @@
 เงื่อนไขดังกล่าว รับประกันความสูงของต้นไม้ ดังที่แสดงใน claim ต่อไปนี้
-{{กล่องเทา|'''Claim:''' Scapegoat tree ที่มี n โหนดจะมีความลึกไม่เกิน O(log n)}}
+{{กล่องฟ้า|'''Claim:''' Scapegoat tree ที่มี n โหนดจะมีความลึกไม่เกิน O(log n)}}
 Operation: Insert node

@@ แถว 1: / แถว 1: @@
 == ความรู้เบื้องต้น ==
 Tree เป็นโครงสร้างชนิดไม่เชิงเส้น (Non-linear) มีลักษณะเป็น recursive ประกอบไปด้วยสมาชิกที่เรียกว่า Node และมีเส้นที่เชื่อมระหว่าง Node ที่เรียกว่า branch คำสำคัญที่เกี่ยวกับ Tree มีดังนี้
@@ แถว 130: / แถว 131: @@
 เงื่อนไขความสมดุลย์ของ scapegoat tree เป็นดังนี้
-<div style="padding: 3px; background-color: #f9f9f9; border: 1px solid gray;">
+{{กล่องเทา|'''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>
-</div>
+}}
 เงื่อนไขดังกล่าว รับประกันความสูงของต้นไม้ ดังที่แสดงใน claim ต่อไปนี้
-<div style="padding: 3px; background-color: #f9f9f9; border: 1px solid gray;">
+{{กล่องเทา|'''Claim:''' Scapegoat tree ที่มี n โหนดจะมีความลึกไม่เกิน O(log n)}}
 Operation: Insert node

@@ แถว 128: / แถว 128: @@
 แทนจำนวนโหนดใน <math>T_v</math>
-'''Condition:''' สำหรับทุก ๆ โหนด ''v''<br>
+เงื่อนไขความสมดุลย์ของ scapegoat tree เป็นดังนี้
 '''Claim:''' Scapegoat tree ที่มี n โหนดจะมีความลึกไม่เกิน O(log n)<br>
 Operation: Insert node

@@ แถว 125: / แถว 125: @@
 จากแนวคิดของ 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>
+สำหรับ node ''v'' ในต้นไม้, ให้ <math>T_v</math> แทน subtree ที่มี Root เป็น ''v'' ให้ ''left''(''v'') แทนลูกด้านซ้ายของ ''v'', ''right''(''v'') แทนลูกด้านขวาของ v และ <math>|T_v|</math>
 แทนจำนวนโหนดใน <math>T_v</math>
-'''Condition:''' สำหรับทุก ๆ โหนด 'v'
+'''Condition:''' สำหรับทุก ๆ โหนด ''v''
 <math>|T_{left(v)}| \leq 2|T_{right(v)}|</math><br>
 และ<br>

@@ แถว 123: / แถว 123: @@
 == Scapegoat Tree ==
-จากแนวคิดของ amortized analysis เราสามารถวิเคราะห์ต้นไม้ที่เรียกว่า Scapegoat โดยที่ AVL Tree นั้นรับประกันว่าการทำงานในแต่ละครั้งจะมีเวลาการทำงานไม่เกิน O(n) แต่ใน Scapegoat Tree จะมีเงื่อนไขดังนี้
+จากแนวคิดของ amortized analysis เราสามารถวิเคราะห์ต้นไม้ที่เรียกว่า Scapegoat โดยที่ AVL Tree นั้นรับประกันว่าการทำงานในแต่ละครั้งจะมีเวลาการทำงานไม่เกิน O(n) แต่ใน Scapegoat Tree จะมีเงื่อนไขที่แตกต่างไป
-Condition: สำหรับ node v,<br>
+สำหรับ node 'v' ในต้นไม้, ให้ <math>T_v</math> แทน subtree ที่มี Root เป็น 'v' ให้ 'left'('v') แทนลูกด้านซ้ายของ 'v', 'right'('v') แทนลูกด้านขวาของ v และ <math>|T_v|</math>
-Tv แทน subtree ที่มี Root เป็น v<br>
+แทนจำนวนโหนดใน <math>T_v</math>
-left (v) แทนลูกด้านซ้ายของ v<br>
-right (v) แทนลูกด้านขวาของ v<br>
+'''Condition:''' สำหรับทุก ๆ โหนด 'v'
-|Tv| แทนจำนวนโหนดใน Tv<br>
+<math>|T_{left(v)}| \leq 2|T_{right(v)}|</math><br>
 และ<br>
-|Tright(v)| ≤ 2|Tleft(v)|<br>
+<math>|T_{right(v)}| \leq 2|T_{left(v)}|</math>
-<br>
-Claim: Scapegoat tree ที่มี n โหนดจะมีความลึกไม่เกิน O(log n)<br>
+'''Claim:''' Scapegoat tree ที่มี n โหนดจะมีความลึกไม่เกิน O(log n)<br>
 Operation: Insert node

@@ แถว 115: / แถว 115: @@
 === Delete Tree ===
-การลบ Node ในต้นไม้มีวิธีการลบแบบหนึ่งที่เรียกว่า Lazy Delete มีวิธีการทำงานคือจะใช้การ Mark โหนดแทนการลบโหนดออกจากต้นไม้ โดยวิธีนี้จะเกิดปัญหาเมื่อมีการลบและ insert โหนดหลายๆครั้ง ส่งผลให้ต้นไม้มีความสูงมาก และไม่สามารถทำงานได้ภายในเวลา O(log n) เมื่อ N ≤ 2n <br />
+การลบ Node ในต้นไม้มีวิธีการลบแบบหนึ่งที่เรียกว่า Lazy Delete มีวิธีการทำงานคือจะใช้การ Mark โหนดแทนการลบโหนดออกจากต้นไม้ โดยวิธีนี้จะเกิดปัญหาเมื่อมีการลบและ insert โหนดหลายๆครั้ง ส่งผลให้ต้นไม้มีความสูงมาก และไม่สามารถทำงานได้ภายในเวลา O(log n) เมื่อ N ≤ 2n ; N คือโหนดที่ถูกลบ <br />
 <center>[[ภาพ:Ld1.jpg]]</center>