ต้นไม้ค้นหาแบบทวิภาค

ต้นไม้ค้นหาแบบทวิภาค
การเรียงตัวของต้นไม้ค้นหาแบบทวิภาค
ความสำคัญของลำดับ	เรียงจากน้อยไปมาก
การซ้ำกันของสมาชิก	ไม่อนุญาตให้ซ้ำ
เวลาที่ใช้ค้นหาตามดัชนี	-
เวลาที่ใช้ค้นหาตามค่า	โดยเฉลี่ย O(log n) กรณีแย่สุด O(n)
เวลาที่ใช้ในการเข้าถึง	โดยเฉลี่ย O(log n) กรณีแย่สุด O(n)
การทำให้ว่าง	ลบรากทิ้ง
เวลาที่ใช้ทำให้ว่าง	O(1)
โครงสร้างต้นแบบ	ต้นไม้ทวิภาค
โครงสร้างที่นำไปใช้	ต้นไม้AVL

ต้นไม้ค้นหาแบบทวิภาค (อังกฤษ: binary search tree , BST) เป็นโครงสร้างข้อมูล ซึ่งใช้โครงสร้างต้นไม้ในการทำต้นไม้ค้นหาแบบทวิภาคต่างจากต้นไม้แบบทวิภาคตรงที่ส่วนของต้นไม้ด้านซ้ายของข้อมูลใดๆ จะน้อยกว่าข้อมูลนั้น และส่วนของต้นไม้ด้านขวาของข้อมูลใดๆ จะมากกว่าข้อมูลนั้นเสมอ ต้นไม้ค้นหาแบบทวิภาคสร้างขึ้นมาเพื่อให้เติมลบ หรือหาได้ง่าย สำหรับข้อมูลที่เปรียบเทียบกันได้ ต้นไม้ค้นหาแบบทวิภาคมักใช้ในการทำโครงสร้างข้อมูลชนิดอื่นๆต่อไป

ลักษณะของต้นไม้ค้นหาทวิภาค

ต้นไม้ค้นหาแบบทวิภาคจะต้องเป็นต้นไม้ทวิภาค กล่าวคือมีสองลูกต่อหนึ่งโนด และส่วนของต้นไม้ด้านซ้าย (left subtree) จะต้องน้อยกว่า ตัวข้อมูล และส่วนของต้นไม้ด้านขวา (right subtree) จะต้องมากกว่า ตัวข้อมูลเสมอ สำหรับข้อมูลที่ใช้ในต้นไม้ค้นหาแบบทวิภาคเราจะใช้ข้อมูลที่เปรียบเทียบกันได้ (Comparable) เช่นตัวเลข ซึ่งสามารถบอกได้ว่าสิ่งใดมากกว่าหรือน้อยกว่าอีกสิ่งหนึ่งได้

จุดเด่นของต้นไม้ค้นหาแบบทวิภาค

จุดเด่นของต้นไม้ค้นหาแบบทวิภาคคือการเอาออก นำเข้า และการเรียงลำดับของข้อมูลอยู่ตลอดเวลา และการค้นหาแบบ ทวิภาค (binary search) ทำให้ตัดออกได้เป็นส่วนๆ และใช้เวลาโดยเฉลี่ย O(log n)

บริการที่มักจะมี

• หาจุดยอดที่เก็บสมาชิก e
• การเพิ่ม/ลบข้อมูล สมาชิก e
• การไล่ลำดับสมาชิก และการแวะผ่านต้นไม้
• การสำรวจสมาชิกพิเศษ เช่น สมาชิกที่เป็นใบ

ความเร็วที่ใช้ในการทำงาน

ความเร็วในการทำงานส่วนมากยังเป็น O(log n) เนื่องจากมีการค้นหาเป็นการค้นหาแบบทวิภาค ซึ่งตัดสิ่งที่เป็นไปไม่ได้ออกครึ่งหนึ่ง ทำให้ทำงานได้รวดเร็ว แต่บางกรณี ที่ต้นไม้ยาว (ยาวสุดคือต่อกันเป็นรายการโยง) เช่นนี้อาจทำให้ต้นไม้ทำงานช้า ไม่สามารถการันตีประสิทธิภาพได้ นำไปสู่แนวคิดการทำต้นไม้เอวีแอลต่อไป

การทำงาน	เวลา
การหาตามดัชนี	-
การเข้าถึงสมาชิก	O(log n)

ดูเพิ่ม

• ต้นไม้ (คณิตศาสตร์)
• โครงสร้างข้อมูล