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

จากวิกิพีเดีย สารานุกรมเสรี

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

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

เนื้อหา 1 ลักษณะของต้นไม้ค้นหาทวิภาค 2 จุดเด่นของต้นไม้ค้นหาแบบทวิภาค 3 บริการที่มักจะมี 4 ความเร็วที่ใช้ในการทำงาน 5 ดูเพิ่ม

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

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

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

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

[แก้] บริการที่มักจะมี

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

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

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

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

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

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

ด • พ • ก ประเภทข้อมูลอย่างย่อและโครงสร้างข้อมูล ประเภทข้อมูลอย่างย่อ Collection • รายการ • เซต • ต้นไม้ • กองซ้อน • คิว • คิวสองหน้า • คิวลำดับความสำคัญ • Associative Array รายการ รายการแถวลำดับ • รายการโยง ต้นไม้ ต้นไม้ค้นหาแบบทวิภาค • ทรีพ • ต้นไม้แดงดำ • Splay Tree คิว คิว • คิวสองหน้า • คิวลำดับความสำคัญ • ฮีป Associative Array ตารางแฮช ดูเพิ่ม ฟังก์ชันแฮช • ขั้นตอนวิธี • สัญกรณ์โอใหญ่