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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 19: แถว 19:
 
| '''<center>Node</center>''' || '''<center>Depth</center>''' || '''<center>Height</center>'''
 
| '''<center>Node</center>''' || '''<center>Depth</center>''' || '''<center>Height</center>'''
 
|-
 
|-
|  A || 0 || 2
+
|  A || 0 || 3
 
|-
 
|-
|  B || 1 || 1
+
|  B || 1 || 2
 
|-
 
|-
|  C || 2 || 0
+
|  C || 2 || 1
 
|-
 
|-
|  D || 2 || 0
+
|  D || 2 || 1
 
|-
 
|-
|  E || 1 || 0
+
|  E || 1 || 1
 
|-
 
|-
|  F || 1 || 1
+
|  F || 1 || 2
 
|-
 
|-
|  G || 2 || 0
+
|  G || 2 || 1
 
|-
 
|-
|  H || 2 || 0
+
|  H || 2 || 1
 
|-
 
|-
|  I || 2 || 0
+
|  I || 2 || 1
 
|}
 
|}
 
----
 
----
 +
 
== Binary Search Tree ==
 
== Binary Search Tree ==
 
Binary Search Tree คือ Data Structure ที่ define แบบ Recursive โดยขั้นตอนวิธีการทำงานที่สำคัญของ Binary Tree จะสนับสนุนการทำงานดังต่อไปนี้
 
Binary Search Tree คือ Data Structure ที่ define แบบ Recursive โดยขั้นตอนวิธีการทำงานที่สำคัญของ Binary Tree จะสนับสนุนการทำงานดังต่อไปนี้

รุ่นแก้ไขเมื่อ 14:31, 24 มิถุนายน 2550

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

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


Node
Depth
Height
A 0 3
B 1 2
C 2 1
D 2 1
E 1 1
F 1 2
G 2 1
H 2 1
I 2 1

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)
≥ ()k
≥ () ---*
จะสังเกตได้ว่าฟังก์ชันดังกล่าวมีขนาดเป็น 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 เมื่อมีการใส่ข้อมูลเข้าไป