Binary Tree เป็นโครงสร้างข้อมูลพิเศษสำหรับเก็บข้อมูล Binary tree มีเงื่อนไขพิเศษคือแต่ละ node สามารถมี child ได้สูงสุด 2 ตัว Binary tree มีข้อดีของทั้ง ordered array และ linked list คือ search เร็วเท่า sorted array และ insertion/deletion เร็วเท่า linked list
นี่คือภาพประกอบ binary tree พร้อมคำศัพท์ที่เราจะอธิบาย:
คำศัพท์สำคัญ
คำศัพท์สำคัญเกี่ยวกับ tree:
- Path - ลำดับของ nodes ตามขอบของ tree
- Root - Node สุดบนของ tree เรียกว่า root มี root เพียง 1 ต่อ tree และมี path จาก root ไป node ใดๆ เพียง 1 path
- Parent - Node ใดๆ ยกเว้น root มี edge ขึ้นไป 1 edge ไปยัง node เรียกว่า parent
- Child - Node ที่อยู่ด้านล่างของ node ที่กำหนด เชื่อมด้วย edge ลง เรียกว่า child node
- Leaf - Node ที่ไม่มี child node เรียกว่า leaf node
- Subtree - แสดง descendants ของ node
- Visiting - ตรวจสอบค่าของ node เมื่อ control อยู่ที่ node นั้น
- Traversing - การผ่าน nodes ตามลำดับเฉพาะ
- Levels - Level ของ node แสดง generation ถ้า root อยู่ level 0 child ถัดไป level 1 ลูกหลาน level 2 ไปเรื่อยๆ
- Keys - ค่าของ node ที่ใช้ในการ search operation
