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
  

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)
สมมติว่ามี data 1,2,8,3,7,5,10,20,12 เขียนเป็น Binary Search Tree ได้ดังนี้