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

จากวิกิพีเดีย สารานุกรมเสรี
ต้นไม้ค้นหาแบบทวิภาค
Binary search tree.svg
การเรียงตัวของต้นไม้ค้นหาแบบทวิภาค
ความสำคัญของลำดับ เรียงจากน้อยไปมาก
การซ้ำกันของสมาชิก ไม่อนุญาตให้ซ้ำ
การทำให้ว่าง ลบรากทิ้ง
เวลาที่ใช้ทำให้ว่าง 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)

ดูเพิ่ม[แก้]