الدرس 16 · الوحدة 7: اختيار تركيب بيانات لحل مشكلة
شجرة البحث الثنائية
بحث ثنائي في تركيب ينمو: كل عقدة تعرف أين تذهب القيم الأصغر والأكبر. ⏱ نحو 40 دقيقة.
بعد هذا الدرس ستستطيع أن:
- تعرف مصطلحات الشجرة: الجذر والورقة والارتفاع.
- تشرح قاعدة شجرة البحث الثنائية.
- تنفذ الإضافة والبحث والمرور الداخلي.
- تفسر أثر التوازن على التعقيد، وتقارن
BSTبالقاموس والقائمة المرتبة.
١الشجرة: مصطلحات
| المصطلح | معناه |
|---|---|
| الجذر Root | العقدة العليا التي لا أب لها. |
| الابن والأب | كل عقدة (عدا الجذر) لها أب واحد، وقد يكون لها أبناء. |
| الورقة Leaf | عقدة بلا أبناء. |
| الارتفاع Height | عدد المستويات من الجذر إلى أبعد ورقة. |
| الشجرة الثنائية | لكل عقدة ابنان على الأكثر: أيسر وأيمن. |
٢قاعدة شجرة البحث الثنائية
شجرة البحث الثنائية Binary Search Tree (BST): شجرة ثنائية فيها قاعدة واحدة لكل عقدة: كل ما في الفرع الأيسر أصغر منها، وكل ما في الفرع الأيمن أكبر منها. وهذا هو البحث الثنائي نفسه، لكن في تركيب يقبل الإضافة بسهولة.
٣الإضافة والبحث
class Node: def __init__(self, key): self.key = key self.left = None self.right = None def insert(node, key): if node is None: return Node(key) if key < node.key: node.left = insert(node.left, key) elif key > node.key: node.right = insert(node.right, key) return node def search(node, key): steps = 0 while node is not None: steps += 1 if key == node.key: return True, steps node = node.left if key < node.key else node.right return False, steps def inorder(node, out): if node is not None: inorder(node.left, out) out.append(node.key) inorder(node.right, out) return out root = Nonefor k in [50, 30, 70, 20, 40, 60, 80, 35, 65]: root = insert(root, k) print(search(root, 35))print(search(root, 90))print("مرتبة:", inorder(root, []))
>>> %Run main.py
(True, 4)
(False, 3)
مرتبة: [20, 30, 35, 40, 50, 60, 65, 70, 80]
>>>
المرور الداخلي In-order (يسار، العقدة، يمين) يُخرج المفاتيح مرتبة تصاعديًّا دائمًا؛ فالشجرة تحفظ البيانات مرتبة وهي تُضاف.
٤التوازن هو كل شيء
الإضافة والبحث يحتاجان خطوات بعدد ارتفاع الشجرة. في الشجرة المتوازنة الارتفاع نحو log₂ n. لكن إن أضفنا عناصر مرتبة، صارت الشجرة «عصا» طويلة، وارتفاعها n:
class Node: def __init__(self, key): self.key = key self.left = None self.right = None def insert(node, key): if node is None: return Node(key) if key < node.key: node.left = insert(node.left, key) elif key > node.key: node.right = insert(node.right, key) return node def search(node, key): steps = 0 while node is not None: steps += 1 if key == node.key: return True, steps node = node.left if key < node.key else node.right return False, steps def inorder(node, out): if node is not None: inorder(node.left, out) out.append(node.key) inorder(node.right, out) return out def height(node): if node is None: return 0 return 1 + max(height(node.left), height(node.right)) import randomrandom.seed(3)keys = random.sample(range(10000), 500) balanced = Nonefor k in keys: balanced = insert(balanced, k) stick = Nonefor k in sorted(keys)[:300]: stick = insert(stick, k) print("عشوائية (500):", height(balanced), "مستوى")print("مرتبة (300):", height(stick), "مستوى")
>>> %Run main.py
عشوائية (500): 18 مستوى
مرتبة (300): 300 مستوى
>>>
لذلك تستخدم الأنظمة الحقيقية أشجارًا ذاتية التوازن تعيد ترتيب نفسها بعد كل إضافة، مثل AVL و Red-Black، وأشجار B-Tree التي تقوم عليها فهارس قواعد البيانات (تذكّر مقرر 121).
٥BST أم قاموس أم قائمة مرتبة؟
| BST متوازنة | dict | قائمة مرتبة | |
|---|---|---|---|
| البحث | O(log n) | O(1) | O(log n) |
| الإضافة | O(log n) | O(1) | O(n) |
| العرض مرتبًا | O(n) | O(n log n) | O(n) |
| أصغر وأكبر قيمة | O(log n) | O(n) | O(1) |
| نطاق: كل القيم بين 30 و 60 | سريع | بطيء | سريع (bisect) |
توقّع وتحقّق
في BST، أين القيم الأصغر من العقدة؟
القاعدة.
المرور الذي يعطي القيم مرتبة:
يسار، عقدة، يمين.
إضافة قيم مرتبة إلى BST عادية تجعلها:
أسوأ حالة.
البحث في BST متوازنة:
بعدد المستويات.
الخلاصة
BST: اليسار أصغر واليمين أكبر في كل عقدة.- البحث والإضافة بعدد مستويات الشجرة.
- المرور الداخلي يعطي القيم مرتبة.
- متوازنة:
O(log n)، وعصا (مدخلات مرتبة):O(n). - الأشجار ذاتية التوازن و
B-Treeأساس الفهارس.
تحدٍّ برمجي: أصغر وأكبر وعدد العقد
متوسطأضف إلى كود الشجرة ثلاث دوال: smallest(node) و largest(node) بحلقة، و count(node) بالعودية.
المطلوب:
- الأصغر: اتجه يسارًا حتى النهاية. والأكبر: يمينًا.
count: 0للشجرة الفارغة، وإلا1 + count(left) + count(right).- اطبع: 12 91 8
ابدأ من هذا الكود، واضغط ▶ شغّل هنا لتكتب حلّك وتجرّبه مباشرة:
class Node: def __init__(self, key): self.key = key self.left = None self.right = None def insert(node, key): if node is None: return Node(key) if key < node.key: node.left = insert(node.left, key) elif key > node.key: node.right = insert(node.right, key) return node def search(node, key): steps = 0 while node is not None: steps += 1 if key == node.key: return True, steps node = node.left if key < node.key else node.right return False, steps def inorder(node, out): if node is not None: inorder(node.left, out) out.append(node.key) inorder(node.right, out) return out root = Nonefor k in [45, 23, 67, 12, 34, 56, 91, 29]: root = insert(root, k) # دوالك هنا
12 91 8
💡 تلميح 1
while node.left is not None: node = node.left💡 تلميح 2
count بالعودية مثل height.
حاول بنفسك أولًا؛ للمسألة أكثر من حلّ صحيح.
class Node: def __init__(self, key): self.key = key self.left = None self.right = None def insert(node, key): if node is None: return Node(key) if key < node.key: node.left = insert(node.left, key) elif key > node.key: node.right = insert(node.right, key) return node def search(node, key): steps = 0 while node is not None: steps += 1 if key == node.key: return True, steps node = node.left if key < node.key else node.right return False, steps def inorder(node, out): if node is not None: inorder(node.left, out) out.append(node.key) inorder(node.right, out) return out root = Nonefor k in [45, 23, 67, 12, 34, 56, 91, 29]: root = insert(root, k) def smallest(node): while node.left is not None: node = node.left return node.key def largest(node): while node.right is not None: node = node.right return node.key def count(node): if node is None: return 0 return 1 + count(node.left) + count(node.right) print(smallest(root), largest(root), count(root))