ต้นไม้ค้นหาแบบไบนารี คือต้นไม้ไบนารีที่มีคุณสมบัติเรียงลำดับ: สำหรับแต่ละโหนด คีย์ทั้งหมดในซับทรีด้านซ้ายมีค่าน้อยกว่า และ คีย์ทั้งหมดในซับทรีด้านขวามีค่ามากกว่า สิ่งนี้ช่วยให้คุณสามารถค้นหาได้โดยลดปัญหาลงครึ่งหนึ่งในแต่ละขั้นตอน
8
/ \
3 10
/ \ \
1 6 14 left < node < right at every node
def search(node, key):
while node:
if key == node.val: return node
node = node.left if key < node.val else node.right # go one way
return None
def insert(node, key):
if node is None: return Node(key)
if key < node.val: node.left = insert(node.left, key)
else: node.right = insert(node.right, key)
return node
| การดำเนินการ | สมดุล | กรณีที่แย่ที่สุด (เสื่อม) |
|---|---|---|
| ค้นหา | O(log n) | O(n) |
| แทรก | O(log n) | O(n) |
| ลบ | O(log n) | O(n) |
กรณีที่แย่ที่สุด เกิดขึ้นเมื่อคีย์ถูกแทรกในลำดับที่เรียงลำดับ — ต้นไม้เสื่อมลงเป็นรายการที่เชื่อมโยงซึ่งมีความสูง n
BST ให้ข้อมูลแบบเรียงลำดับและแบบไดนามิกกับการดำเนินการแบบลอการิทึม — บรรพบุรุษแนวคิดของดัชนีฐานข้อมูลและแผนที่ที่เรียงลำดับ
ปัญหาการเสื่อมทำให้เกิดแรงจูงใจสำหรับ ต้นไม้ที่สมดุลเองอย่างอื่น ซึ่งเป็นหัวข้อติดตามที่สำคัญในการสัมภาษณ์