Binary Search Tree
- Binary Search Tree
บทความนี้จะอธิบายเกี่ยวกับโครงสร้างข้อมูลที่เรียกว่า “Binary Search Tree” (BST) หรือ ต้นไม้ค้นหาแบบไบนารี เหมาะสำหรับผู้เริ่มต้นที่ต้องการทำความเข้าใจหลักการพื้นฐานและวิธีการใช้งานของโครงสร้างข้อมูลนี้ โดยจะเน้นที่แนวคิดหลัก, การดำเนินการพื้นฐาน, และข้อดีข้อเสียของ BST รวมถึงการเปรียบเทียบกับโครงสร้างข้อมูลอื่นๆ
บทนำ
โครงสร้างข้อมูล เป็นองค์ประกอบสำคัญในการเขียนโปรแกรมที่มีประสิทธิภาพ การเลือกใช้โครงสร้างข้อมูลที่เหมาะสมจะส่งผลต่อความเร็วในการทำงานและปริมาณการใช้หน่วยความจำของโปรแกรม Binary Search Tree (BST) เป็นหนึ่งในโครงสร้างข้อมูลที่ได้รับความนิยมเนื่องจากมีประสิทธิภาพในการค้นหา, แทรก, และลบข้อมูล
BST เป็นโครงสร้างข้อมูลแบบลำดับชั้น (hierarchical) ที่ประกอบด้วย โหนด (node) แต่ละโหนดมีข้อมูล, ตัวชี้ไปยังโหนดลูกซ้าย (left child), และตัวชี้ไปยังโหนดลูกขวา (right child) คุณสมบัติสำคัญของ BST คือ:
- สำหรับแต่ละโหนด ข้อมูลในโหนดลูกซ้ายทั้งหมดต้องมีค่าน้อยกว่าข้อมูลในโหนดนั้น
- สำหรับแต่ละโหนด ข้อมูลในโหนดลูกขวาทั้งหมดต้องมีค่ามากกว่าข้อมูลในโหนดนั้น
คุณสมบัติเหล่านี้ทำให้ BST มีประสิทธิภาพในการค้นหาข้อมูล เนื่องจากสามารถตัดส่วนที่ไม่เกี่ยวข้องของต้นไม้ทิ้งไปได้ในแต่ละขั้นตอน
แนวคิดพื้นฐาน
- **โหนด (Node):** หน่วยพื้นฐานของ BST แต่ละโหนดเก็บข้อมูลและตัวชี้ไปยังโหนดลูกซ้ายและขวา
- **ราก (Root):** โหนดบนสุดของต้นไม้ ไม่มีโหนดแม่
- **ใบ (Leaf):** โหนดที่ไม่มีโหนดลูก
- **ความสูง (Height):** จำนวนเส้นทางที่ยาวที่สุดจากรากไปยังใบ
- **ระดับ (Level):** ระยะห่างจากราก (รากมีระดับ 0)
- **การจัดเรียง (Ordering):** คุณสมบัติที่สำคัญของ BST ที่ระบุว่าข้อมูลในโหนดลูกซ้ายต้องน้อยกว่าข้อมูลในโหนดปัจจุบัน และข้อมูลในโหนดลูกขวาต้องมากกว่าข้อมูลในโหนดปัจจุบัน
การดำเนินการพื้นฐาน
1. **การค้นหา (Search):** เริ่มต้นจากราก เปรียบเทียบข้อมูลที่ต้องการค้นหากับข้อมูลในโหนดปัจจุบัน
* ถ้าเท่ากัน ให้คืนค่าโหนดนั้น * ถ้าข้อมูลที่ต้องการค้นหาน้อยกว่าข้อมูลในโหนดปัจจุบัน ให้ค้นหาในโหนดลูกซ้าย * ถ้าข้อมูลที่ต้องการค้นหามากกว่าข้อมูลในโหนดปัจจุบัน ให้ค้นหาในโหนดลูกขวา * ถ้าถึงโหนดใบแล้วยังไม่พบข้อมูล ให้คืนค่า null หรือบอกว่าไม่พบข้อมูล การค้นหาใน BST มีความซับซ้อนเป็น O(log n) ในกรณีที่ดีที่สุดและกรณีเฉลี่ย แต่เป็น O(n) ในกรณีที่แย่ที่สุด (เช่น เมื่อต้นไม้กลายเป็นเส้นตรง)
2. **การแทรก (Insertion):** ค้นหาตำแหน่งที่เหมาะสมสำหรับโหนดใหม่ตามคุณสมบัติของ BST
* เริ่มต้นจากราก เปรียบเทียบข้อมูลที่ต้องการแทรกกับข้อมูลในโหนดปัจจุบัน * ถ้าข้อมูลที่ต้องการแทรกน้อยกว่าข้อมูลในโหนดปัจจุบัน ให้เลื่อนไปที่โหนดลูกซ้าย * ถ้าข้อมูลที่ต้องการแทรกมากกว่าข้อมูลในโหนดปัจจุบัน ให้เลื่อนไปที่โหนดลูกขวา * เมื่อถึงโหนดใบ (หรือตำแหน่งที่ว่าง) ให้สร้างโหนดใหม่และแทรกข้อมูลเข้าไป การแทรกใน BST มีความซับซ้อนเป็น O(log n) ในกรณีที่ดีที่สุดและกรณีเฉลี่ย แต่เป็น O(n) ในกรณีที่แย่ที่สุด
3. **การลบ (Deletion):** การลบโหนดใน BST มีความซับซ้อนกว่าการค้นหาและการแทรก เนื่องจากต้องรักษาคุณสมบัติของ BST ไว้
* **กรณีที่ 1:** โหนดที่ต้องการลบเป็นใบ: ลบโหนดนั้นได้เลย
* **กรณีที่ 2:** โหนดที่ต้องการลบมีโหนดลูกเพียงโหนดเดียว: แทนที่โหนดนั้นด้วยโหนดลูก
* **กรณีที่ 3:** โหนดที่ต้องการลบมีโหนดลูกสองโหนด:
* หาโหนดที่เล็กที่สุดในโหนดลูกขวา (inorder successor) หรือโหนดที่ใหญ่ที่สุดในโหนดลูกซ้าย (inorder predecessor)
* แทนที่ข้อมูลในโหนดที่ต้องการลบด้วยข้อมูลจากโหนดที่เลือก
* ลบโหนดที่เลือกออกจากตำแหน่งเดิม
การลบใน BST มีความซับซ้อนเป็น O(log n) ในกรณีที่ดีที่สุดและกรณีเฉลี่ย แต่เป็น O(n) ในกรณีที่แย่ที่สุด
4. **การหาค่าต่ำสุด (Minimum):** เลื่อนไปทางซ้ายเรื่อยๆ จนถึงโหนดใบซ้ายสุด 5. **การหาค่าสูงสุด (Maximum):** เลื่อนไปทางขวาเรื่อยๆ จนถึงโหนดใบขวาสุด
ตัวอย่างการใช้งาน
สมมติว่าเรามีข้อมูลชุดหนึ่ง: 50, 30, 20, 40, 70, 60, 80
การสร้าง BST จากข้อมูลนี้:
- แทรก 50 (ราก)
- แทรก 30 (ลูกซ้ายของ 50)
- แทรก 20 (ลูกซ้ายของ 30)
- แทรก 40 (ลูกขวาของ 30)
- แทรก 70 (ลูกขวาของ 50)
- แทรก 60 (ลูกซ้ายของ 70)
- แทรก 80 (ลูกขวาของ 70)
ต้นไม้ที่ได
เริ่มต้นการซื้อขายตอนนี้
ลงทะเบียนกับ IQ Option (เงินฝากขั้นต่ำ $10) เปิดบัญชีกับ Pocket Option (เงินฝากขั้นต่ำ $5)
เข้าร่วมชุมชนของเรา
สมัครสมาชิกช่อง Telegram ของเรา @strategybin เพื่อรับ: ✓ สัญญาณการซื้อขายรายวัน ✓ การวิเคราะห์เชิงกลยุทธ์แบบพิเศษ ✓ การแจ้งเตือนแนวโน้มตลาด ✓ วัสดุการศึกษาสำหรับผู้เริ่มต้น
