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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 38: แถว 38:
 
|}
 
|}
 
----
 
----
 +
== Binary Search Tree ==
 +
Binary Search Tree เป็นขั้นตอนวิธีการทำงานที่สำคัญของ Binary Tree โดยจะสนับสนุนการทำงานดังต่อไปนี้
 +
*Find (key)
 +
*Insert (key)
 +
*Delete (key)
 +
ซึ่งเวลาที่ใช้ในการค้นหานั้นจะขึ้นอยู่กับความสูงของต้นไม้ โดยถ้ามีข้อมูล n ตัวความสูงของต้นไม้จะลึกไปกว่า O(log n)
 +
[[ภาพ:bst_1.jpg]]

รุ่นแก้ไขเมื่อ 09:15, 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 2
B 1 1
C 2 0
D 2 0
E 1 0
F 1 1
G 2 0
H 2 0
I 2 0

Binary Search Tree

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

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

ซึ่งเวลาที่ใช้ในการค้นหานั้นจะขึ้นอยู่กับความสูงของต้นไม้ โดยถ้ามีข้อมูล n ตัวความสูงของต้นไม้จะลึกไปกว่า O(log n) Bst 1.jpg