شجرة البحث الثنائية هي شجرة ثنائية تتمتع بخاصية ترتيب ثابتة: لكل عقدة، جميع المفاتيح في الشجرة الفرعية اليسرى أصغر، وجميع المفاتيح في الشجرة الفرعية اليمنى أكبر. هذا يتيح لك البحث بتقسيم المشكلة إلى النصف في كل خطوة.
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.
شجرة البحث الثنائية تعطيك بيانات ديناميكية مرتبة مع عمليات لوغاريتمية — السلف المفاهيمي لفهارس قواعد البيانات والخرائط المرتبة.
مشكلة التدهور تحفز الأشجار ذاتية التوازن، وهي موضوع متابعة رئيسي في المقابلات.
مكتبة من أسئلة مقابلات تقنية المعلومات مع إجابات مفصّلة — من المبتدئ إلى المتقدم.
تبرع