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

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

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

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

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

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

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

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

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

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

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

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

ดูเพิ่ม

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