تعلم بنية شجرة البحث الثنائية Binary Search Tree في بايثون

🌳 شجرة البحث الثنائية في بايثون: دليلك الكامل للمبتدئين

مرحباً بك في عالم هياكل البيانات الرائع! بعد أن تعلمنا في الدروس السابقة هياكل خطية مثل القوائم (Lists) والمكدسات (Stacks)، حان الوقت للانتقال إلى مستوى جديد من التنظيم والكفاءة. في هذا الدرس، سنتعرف على شجرة البحث الثنائية (Binary Search Tree)، وهي إحدى أهم هياكل البيانات غير الخطية التي ستساعدك في تنظيم بياناتك بشكل يسرّع عمليات البحث بشكل هائل! 🚀

ما هي شجرة البحث الثنائية (BST)؟ 🤔

تخيل أن لديك دليلاً هاتفياً ورقيًا. للعثور على اسم "محمد"، لن تبدأ من الصفحة الأولى وتقلبها واحدة تلو الأخرى. بدلاً من ذلك، ستفتح الدليل من المنتصف تقريباً، وإذا وجدت أسماء تبدأ بحرف بعد "الميم"، تعود للخلف قليلاً، وهكذا. شجرة البحث الثنائية تطبق فكرة مشابهة على البيانات الرقمية!

شجرة البحث الثنائية (BST) هي هيكل بيانات شجري (Tree) يتكون من عُقَد (Nodes)، حيث كل عقدة تحتوي على:

1. البيانات (Data)، مثل رقم أو سلسلة نصية.
2. مؤشر (Reference) للعقدة الابن اليسرى (Left Child).
3. مؤشر (Reference) للعقدة الابن اليمنى (Right Child).

والقاعدة الذهبية التي تميز BST هي:

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

هذه القاعدة البسيطة والقوية هي سر سرعة البحث في هذه الشجرة! ⚡

بناء العقدة (Node) الأساسية في بايثون

كل شيء في الشجرة يبدأ من العقدة. لننشئ فئة Node تمثل اللبنة الأساسية لشجرتنا.

# تعريف فئة العقدة (Node)
class Node:
    def __init__(self, data):
        self.data = data       # تخزين القيمة
        self.left = None       # رابط للابن الأيسر (مبدئياً لا يوجد)
        self.right = None      # رابط للابن الأيمن (مبدئياً لا يوجد)

# مثال: إنشاء عقدة جذرية تحتوي على القيمة 10
root_node = Node(10)
print(f"عقدة الجذر تحتوي على: {root_node.data}")
print(f"الابن الأيسر: {root_node.left}")   # سيطبع None
print(f"الابن الأيمن: {root_node.right}")  # سيطبع None

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

الآن، سنبني الفئة الرئيسية BST التي ستتحكم في الشجرة وتوفر لنا العمليات الأساسية مثل الإدراج والبحث.

class BST:
    def __init__(self):
        self.root = None  # عند إنشاء الشجرة، تكون فارغة (الجذر = لا شيء)

    # دالة مساعدة لعرض الشجرة (سنشرح الاجتياز لاحقاً)
    def inorder_traversal(self, node):
        if node is not None:
            self.inorder_traversal(node.left)
            print(node.data, end=' ')
            self.inorder_traversal(node.right)

# مثال: إنشاء شجرة بحث ثنائية فارغة
my_tree = BST()
print(f"جذر الشجرة الجديدة: {my_tree.root}")  # سيطبع: None

🔧 العملية الأولى: إدراج عقدة جديدة (Insert)

عملية الإدراج تتبع القاعدة الذهبية. نبدأ من الجذر ونقارن القيمة المراد إدراجها مع قيمة العقدة الحالية:

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

class BST:
    # ... (الكود السابق) ...

    # الدالة الرئيسية للإدراج (سيستخدمها المستخدم)
    def insert(self, data):
        self.root = self._insert_recursive(self.root, data)

    # دالة مساعدة تعمل بشكل متكرر (Recursive) لإيجاد مكان الإدراج
    def _insert_recursive(self, node, data):
        # الحالة الأساسية: وصلنا لمكان فارغ، ننشئ عقدة جديدة
        if node is None:
            return Node(data)

        # تطبيق قاعدة BST: أصغر => يسار، أكبر => يمين
        if data < node.data:
            node.left = self._insert_recursive(node.left, data)
        elif data > node.data:
            node.right = self._insert_recursive(node.right, data)

        # إذا كانت data تساوي node.data (قيمة مكررة)، لا نفعل شيئاً في هذا المثال البسيط
        return node

# مثال عملي: بناء شجرة من الأرقام
my_tree = BST()
my_tree.insert(50)  # يصبح الجذر
my_tree.insert(30)  # أصغر من 50، تذهب لليسار
my_tree.insert(70)  # أكبر من 50، تذهب لليمين
my_tree.insert(20)  # أصغر من 50، ثم أصغر من 30، تذهب لليسار
my_tree.insert(40)  # أصغر من 50، لكن أكبر من 30، تذهب لليمين تحت 30

print("عناصر الشجرة بترتيب (In-order):")
my_tree.inorder_traversal(my_tree.root)  # المخرجات: 20 30 40 50 70

ملاحظة: لاحظ كيف أن طباعة العناصر بترتيب inorder تعطينا الأرقام مرتبة تصاعدياً! هذه إحدى المميزات الرائعة لـ BST.

🔍 العملية الثانية: البحث عن قيمة (Search)

الباحث في BST سريع جداً! الفكرة مشابهة للإدراج: نقارن ونتفرع يساراً أو يميناً بناءً على المقارنة.

class BST:
    # ... (الكود السابق) ...

    # دالة البحث الرئيسية
    def search(self, data):
        return self._search_recursive(self.root, data)

    # دالة البحث المساعدة (متكررة)
    def _search_recursive(self, node, data):
        # الحالة 1: العقدة فارغة أو وجدنا القيمة في العقدة الحالية
        if node is None or node.data == data:
            return node  # إما ترجع العقدة التي تحتوي على القيمة، أو ترجع None إذا لم توجد

        # الحالة 2: القيمة المطلوبة أصغر، نبحث في الفرع الأيسر
        if data < node.data:
            return self._search_recursive(node.left, data)

        # الحالة 3: القيمة المطلوبة أكبر، نبحث في الفرع الأيمن
        # if data > node.data:
        return self._search_recursive(node.right, data)

# مثال عملي: البحث في الشجرة التي بنيناها
my_tree = BST()
# ... (إدراج نفس الأرقام السابقة: 50, 30, 70, 20, 40) ...

result = my_tree.search(40)
if result:
    print(f"✅ وجدنا القيمة: {result.data}")
else:
    print("❌ القيمة غير موجودة في الشجرة")

result2 = my_tree.search(99)
if result2:
    print(f"وجدنا القيمة: {result2.data}")
else:
    print("❌ القيمة 99 غير موجودة في الشجرة")

ملخص الدرس 📝

تعلمنا اليوم أساسيات شجرة البحث الثنائية (BST) في بايثون:

• فكرتها: هيكل شجري يحافظ على ترتيب البيانات (يسار < جذر < يمين) لتمكين بحث سريع.
• العقدة (Node): اللبنة الأساسية، تحتوي على البيانات وروابط لابن أيسر وآخر أيمن.
• الإدراج (Insert): نجد المكان المناسب بتطبيق قاعدة المقارنة بشكل متكرر.
• البحث (Search): عملية سريعة تشبه الإدراج، حيث نتخلص من نصف البيانات تقريباً في كل خطوة!

تذكر أن كفاءة BST تعتمد على كونها متوازنة، فإذا أدرجنا أرقاماً مرتبة (مثل 1, 2, 3, 4) ستتحول إلى قائمة مرتبطة ويضيع ميزة السرعة! ولكن لا تقلق، سنتعلم في دروس متقدمة عن أشجار مثل AVL أو Red-Black التي تحافظ على التوازن تلقائياً. 😊