شجرة البحث الثنائية (BST)

في درس الأشجار رأينا الشجرة الثنائية: كل عقدة لها ابنان على الأكثر. شجرة البحث الثنائية (Binary Search Tree أو BST) شجرة ثنائية بقاعدة إضافية واحدة، وهذه القاعدة هي ما يجعل البحث فيها سريعًا:

لكل عقدة: كل القيم في فرعها الأيسر أصغر منها، وكل القيم في فرعها الأيمن أكبر منها.

انتبه لكلمة "كل": القاعدة على الفرع كاملًا، لا على الابن المباشر فقط. سنرى في آخر الدرس لماذا هذا الفرق هو أشهر خطأ في المقابلات.

كل الكود هنا مجرّب على Python 3.13، والأرقام مقاسة فعليًا.

مثال

أدرجنا القيم 8, 3, 10, 1, 6, 14, 4, 7, 13 بهذا الترتيب، فنتجت هذه الشجرة:

          8
        /   \
       3     10
      / \      \
     1   6      14
        / \    /
       4   7  13

تحقّق من القاعدة على العقدة 3: فرعها الأيسر {1} كله أصغر منها، وفرعها الأيمن {6, 4, 7} كله أكبر منها ومع ذلك أصغر من 8، لأن هذا الفرع كله يقع يسار 8.

البناء

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class BST:
    def __init__(self):
        self.root = None

البحث: نصف الشجرة يُستبعد في كل خطوة

    def contains(self, value):
        node = self.root
        while node is not None:
            if value == node.value:
                return True
            node = node.left if value < node.value else node.right
        return False

للبحث عن 7: نبدأ من 8، و7 أصغر فنذهب يسارًا إلى 3، و7 أكبر فنذهب يمينًا إلى 6، و7 أكبر فنذهب يمينًا فنجدها. 4 مقارنات من 9 عناصر، ولم ننظر أبدًا إلى الفرع الأيمن للجذر. هذه نفس فكرة البحث الثنائي في مصفوفة مرتّبة، لكن في بنية تقبل الإضافة والحذف بسهولة.

الإدراج: ابحث عن المكان الفارغ

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
            return
        node = self.root
        while True:
            if value < node.value:
                if node.left is None:
                    node.left = Node(value)
                    return
                node = node.left
            elif value > node.value:
                if node.right is None:
                    node.right = Node(value)
                    return
                node = node.right
            else:
                return  # القيمة موجودة مسبقًا: نتجاهل التكرار

الإدراج هو بحث يفشل: نمشي كما لو كنا نبحث عن القيمة، وحين نصل إلى مكان فارغ نضعها فيه. القيمة الجديدة تصبح دائمًا ورقة (عقدة بلا أبناء).

التكرار قرار تصميمي: هنا نتجاهل القيمة المكرّرة، فتعمل الشجرة كمجموعة (set). بدائل أخرى: أن تحفظ عدّادًا داخل العقدة، أو أن تضع المكرّر دائمًا في جهة ثابتة (مثلًا اليمين). المهم أن تختار قاعدة واحدة وتلتزم بها في البحث والحذف أيضًا.

الاجتياز المرتّب: هدية مجانية

    def inorder(self):
        result = []

        def walk(node):
            if node is None:
                return
            walk(node.left)
            result.append(node.value)
            walk(node.right)

        walk(self.root)
        return result

tree = BST()
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    tree.insert(v)

print(tree.inorder())   # [1, 3, 4, 6, 7, 8, 10, 13, 14]
print(tree.contains(6), tree.contains(5))   # True False

اجتياز inorder (يسار، العقدة، يمين) على BST يعطي القيم مرتّبة دائمًا، بلا أي خوارزمية ترتيب. هذا ما يجعل BST مفيدة حين تحتاج البحث السريع والترتيب معًا، وهو ما لا يعطيك إياه جدول التجزئة.

الحذف: ثلاث حالات

الحذف هو الجزء الذي يحتاج تفكيرًا، لأن إزالة عقدة من وسط الشجرة يجب ألا تكسر القاعدة.

    def delete(self, value):
        self.root = self._delete(self.root, value)

    def _delete(self, node, value):
        if node is None:
            return None                     # القيمة غير موجودة
        if value < node.value:
            node.left = self._delete(node.left, value)
        elif value > node.value:
            node.right = self._delete(node.right, value)
        else:
            # الحالتان 1 و 2: صفر أو ابن واحد
            if node.left is None:
                return node.right
            if node.right is None:
                return node.left
            # الحالة 3: ابنان، نأخذ أصغر قيمة في الفرع الأيمن (الخلَف)
            successor = node.right
            while successor.left is not None:
                successor = successor.left
            node.value = successor.value
            node.right = self._delete(node.right, successor.value)
        return node

نطبّقها على شجرتنا:

1) ورقة: tree.delete(13). ببساطة تختفي؛ الأب (14) يصبح ابنه الأيسر None.

2) عقدة بابن واحد: tree.delete(10). الآن 10 لها ابن واحد (14)، فيأخذ 14 مكانها مباشرة كابن أيمن لـ 8.

3) عقدة بابنين: tree.delete(3). لا يمكن وضع ابنين في مكان واحد. الحل: نستبدل قيمة 3 بـ الخلَف (successor)، وهو أصغر قيمة أكبر منها، أي أقصى اليسار في فرعها الأيمن: 4. ثم نحذف 4 من مكانها القديم، وهي ورقة أو بابن أيمن واحد على الأكثر، فنعود لحالة سهلة.

قبل حذف 3:            بعد حذف 3:
      8                     8
     / \                   / \
    3   14                4   14
   / \                   / \
  1   6                 1   6
     / \                     \
    4   7                     7

tree.delete(13)
tree.delete(10)
tree.delete(3)
print(tree.inorder())   # [1, 4, 6, 7, 8, 14] — ما زالت مرتّبة

لماذا الخلَف تحديدًا؟ لأنه أكبر من كل ما في الفرع الأيسر (فهو من الفرع الأيمن) وأصغر من كل ما بقي في الفرع الأيمن (فهو أصغرها). يمكن أيضًا استخدام السلَف (أكبر قيمة في الفرع الأيسر)، والنتيجة صحيحة بنفس المنطق.

التعقيد: كل شيء يعتمد على الارتفاع

البحث والإدراج والحذف كلها تمشي مسارًا واحدًا من الجذر إلى الأسفل، فتكلفتها O(h) حيث h ارتفاع الشجرة. والسؤال الحقيقي: ما هو h؟

جرّبنا إدراج الأرقام من 0 إلى 999 بترتيبين:

log₂(1000) حوالي 10، والارتفاع الأدنى الممكن لـ 1000 عنصر هو 10. الإدراج العشوائي أعطى شجرة أعلى من ذلك بقليل لكنها ما زالت لوغاريتمية: البحث فيها يكلّف بضع عشرات من الخطوات. أما الإدراج المرتّب فأعطى شجرة كل عقدة فيها لها ابن أيمن فقط، أي قائمة مترابطة متنكّرة، والبحث فيها يمرّ على كل العناصر.

وهذه ليست حالة نظرية: البيانات تصلك مرتّبة كثيرًا في الواقع (معرّفات تتزايد، تواريخ، أسماء من ملف مرتّب).

فخ إضافي: الاستدعاء الذاتي على شجرة منحرفة

على الشجرة المنحرفة ذات الارتفاع 1000، استدعاء inorder() المكتوب بالاستدعاء الذاتي توقف بـ:

RecursionError: maximum recursion depth exceeded

لأن حد Python الافتراضي 1000 استدعاء متداخل، وكل مستوى في الشجرة استدعاء. لهذا كتبنا insert وcontains بحلقة while لا بالاستدعاء الذاتي. شرح الخطأ نفسه في أخطاء بايثون الشائعة.

الحل الجذري لكل هذا هو شجرة تحافظ على توازنها بنفسها بعد كل إدراج وحذف، مثل AVL وRed-Black، وهي موضوع درس الأشجار المتوازنة.

الخطأ الأشهر: التحقق من الأبناء فقط

سؤال مقابلات كلاسيكي: "اكتب دالة تتحقّق إن كانت شجرة ثنائية BST صحيحة". الحل الذي يكتبه أغلب الناس أولًا:

# Node هو نفس الكلاس من أعلى الدرس

def is_bst_wrong(node):
    if node is None:
        return True
    if node.left and node.left.value > node.value:
        return False
    if node.right and node.right.value < node.value:
        return False
    return is_bst_wrong(node.left) and is_bst_wrong(node.right)

يبدو صحيحًا، لكنه يقارن كل عقدة بأبنائها المباشرين فقط. جرّبه على هذه الشجرة:

      8
     /
    3
     \
      12      ← أكبر من 3 (صحيح محليًا) لكنها أكبر من 8 وهي في فرعه الأيسر

is_bst_wrong يرجع True، والشجرة ليست BST: البحث عن 12 سيذهب يمينًا من 8 ولن يجدها أبدًا. الحل الصحيح يمرّر الحدود المسموحة لكل فرع أثناء النزول:

def is_bst(node, low=float("-inf"), high=float("inf")):
    if node is None:
        return True
    if not (low < node.value < high):
        return False
    return is_bst(node.left, low, node.value) and is_bst(node.right, node.value, high)

كل نزول لليسار يضع العقدة الحالية حدًّا أعلى، وكل نزول لليمين يضعها حدًّا أدنى. على المثال فوق: is_bst يرجع False، لأن 12 وصلت بحد أعلى قيمته 8. وحل بديل لا يقل صحة: اجتز الشجرة inorder وتأكّد أن الناتج تصاعدي تمامًا.

هل تكتب BST بنفسك في العمل؟

نادرًا. فهمها ضروري لأنها أساس بنى تستخدمها يوميًا دون أن تراها، لكن المكتبات توفّر نسخًا متوازنة جاهزة:

• Java: TreeMap وTreeSet شجرة Red-Black.
• C++: std::map وstd::set مبنية عادةً على شجرة Red-Black أيضًا.
• Python: لا توجد BST في المكتبة القياسية. للبحث السريع فقط استخدم dict أو set. ولقائمة تبقى مرتّبة مع بحث سريع استخدم bisect:

import bisect

items = [1, 3, 6, 8, 10]
bisect.insort(items, 7)            # يُدرج في المكان الصحيح
print(items)                        # [1, 3, 6, 7, 8, 10]

i = bisect.bisect_left(items, 6)    # بحث ثنائي: O(log n)
print(i < len(items) and items[i] == 6)   # True

البحث هنا O(log n) لكن الإدراج O(n) لأن العناصر تُزاح في المصفوفة. للبيانات الكبيرة كثيرة التعديل توجد مكتبات خارجية مثل sortedcontainers.

وفي قواعد البيانات، الفهارس (indexes) مبنية غالبًا على B-Tree: تعميم لنفس الفكرة بعقد تحمل عشرات المفاتيح بدل مفتاح واحد، لتقليل قراءات القرص.

تمرين

1. اكتب min_value() وmax_value() للشجرة. (تلميح: إلى أين تمشي؟)
2. عدّل insert ليحفظ عدد مرات تكرار كل قيمة بدل تجاهلها.
3. ما ترتيب إدراج القيم 1 إلى 7 الذي ينتج شجرة متوازنة تمامًا بارتفاع 3؟

🎯 التالي: الأكوام (Heaps): شجرة ثنائية بقاعدة مختلفة، تعطيك أصغر عنصر (أو أكبره) فورًا.