ต้นไม้ค้นหาแบบทวิภาค
บทความนี้ไม่มีการอ้างอิงจากแหล่งที่มาใด |
ต้นไม้ค้นหาแบบทวิภาค (อังกฤษ: binary search tree , BST) เป็นโครงสร้างข้อมูล ซึ่งใช้โครงสร้างต้นไม้ในการทำต้นไม้ค้นหาแบบทวิภาคต่างจากต้นไม้แบบทวิภาคตรงที่ส่วนของต้นไม้ด้านซ้ายของข้อมูลใดๆ จะน้อยกว่าข้อมูลนั้น และส่วนของต้นไม้ด้านขวาของข้อมูลใดๆ จะมากกว่าข้อมูลนั้นเสมอ ต้นไม้ค้นหาแบบทวิภาคสร้างขึ้นมาเพื่อให้เติมลบ หรือหาได้ง่าย สำหรับข้อมูลที่เปรียบเทียบกันได้ ต้นไม้ค้นหาแบบทวิภาคมักใช้ในการทำโครงสร้างข้อมูลชนิดอื่นๆต่อไป
| ต้นไม้ค้นหาแบบทวิภาค | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
 การเรียงตัวของต้นไม้ค้นหาแบบทวิภาค | |||||||||||||||||||||
| ความสำคัญของลำดับ | เรียงจากน้อยไปมาก | ||||||||||||||||||||
| การซ้ำกันของสมาชิก | ไม่อนุญาตให้ซ้ำ | ||||||||||||||||||||
| เวลาที่ใช้ค้นหาตามดัชนี | - | ||||||||||||||||||||
| เวลาที่ใช้ค้นหาตามค่า | โดยเฉลี่ย O(log n) กรณีแย่สุด O(n) | ||||||||||||||||||||
| เวลาที่ใช้ในการเข้าถึง | โดยเฉลี่ย O(log n) กรณีแย่สุด O(n) | ||||||||||||||||||||
| การทำให้ว่าง | ลบรากทิ้ง | ||||||||||||||||||||
| เวลาที่ใช้ทำให้ว่าง | O(1) | ||||||||||||||||||||
| โครงสร้างต้นแบบ | ต้นไม้ทวิภาค | ||||||||||||||||||||
| โครงสร้างที่นำไปใช้ | ต้นไม้AVL | ||||||||||||||||||||
| ความซับซ้อนในการคำนวณแบบสัญกรณ์โอใหญ่ | |||||||||||||||||||||
| |||||||||||||||||||||
ลักษณะของต้นไม้ค้นหาทวิภาค แก้
ต้นไม้ค้นหาแบบทวิภาคจะต้องเป็นต้นไม้ทวิภาค กล่าวคือมีสองลูกต่อหนึ่งโนด และส่วนของต้นไม้ด้านซ้าย (left subtree) จะต้องน้อยกว่า ตัวข้อมูล และส่วนของต้นไม้ด้านขวา (right subtree) จะต้องมากกว่า ตัวข้อมูลเสมอ สำหรับข้อมูลที่ใช้ในต้นไม้ค้นหาแบบทวิภาคเราจะใช้ข้อมูลที่เปรียบเทียบกันได้ (Comparable) เช่นตัวเลข ซึ่งสามารถบอกได้ว่าสิ่งใดมากกว่าหรือน้อยกว่าอีกสิ่งหนึ่งได้
จุดเด่นของต้นไม้ค้นหาแบบทวิภาค แก้
จุดเด่นของต้นไม้ค้นหาแบบทวิภาคคือการเอาออก นำเข้า และการเรียงลำดับของข้อมูลอยู่ตลอดเวลา และการค้นหาแบบ ทวิภาค (binary search) ทำให้ตัดออกได้เป็นส่วนๆ และใช้เวลาโดยเฉลี่ย O(log n)
บริการที่มักจะมี แก้
- หาจุดยอดที่เก็บสมาชิก e
- การเพิ่ม/ลบข้อมูล สมาชิก e
- การไล่ลำดับสมาชิก และการแวะผ่านต้นไม้
- การสำรวจสมาชิกพิเศษ เช่น สมาชิกที่เป็นใบ
ความเร็วที่ใช้ในการทำงาน แก้
ความเร็วในการทำงานส่วนมากยังเป็น O(log n) เนื่องจากมีการค้นหาเป็นการค้นหาแบบทวิภาค ซึ่งตัดสิ่งที่เป็นไปไม่ได้ออกครึ่งหนึ่ง ทำให้ทำงานได้รวดเร็ว แต่บางกรณี ที่ต้นไม้ยาว (ยาวสุดคือต่อกันเป็นรายการโยง) เช่นนี้อาจทำให้ต้นไม้ทำงานช้า ไม่สามารถการันตีประสิทธิภาพได้ นำไปสู่แนวคิดการทำต้นไม้เอวีแอลต่อไป
| การทำงาน | เวลา |
|---|---|
| การหาตามดัชนี | - |
| การเข้าถึงสมาชิก | O(log n) |
ดูเพิ่ม แก้
 | บทความคณิตศาสตร์นี้ยังเป็นโครง คุณสามารถช่วยวิกิพีเดียได้โดยการเพิ่มเติมข้อมูล |