أشجار البحث الثنائية
أشجار البحث الثنائية
- شجرة البحث الثنائية (BST) تخزن قيمًا بحيث تبقى مرتبة وسهلة العثور عليها.
- كل عقدة تحمل قيمة وترتبط بما يصل إلى طفلين:
leftوright. - العقدة العليا هي الجذر. عقدة بدون أطفال هي ورقة.
قاعدة شجرة البحث الثنائية
- لكل عقدة: كل شيء في الشجرة الفرعية اليسرى أصغر، وكل شيء في الشجرة الفرعية اليمنى أكبر أو يساوي (هذا الدرس يرسل القيم المتساوية لليمين).
- هذه القاعدة الوحيدة هي ما يسمح لك بإيجاد قيمة بالذهاب يسارًا أو يمينًا — لا كليهما.
5
/ \
3 8
/ \ \
1 4 9
left < node <= right, at every node
العقدة
- نمذج العقدة ككائن صغير يحتوي على
value، وleft، وright. - العقدة الجديدة تماماً ليس لها أطفال بعد، لذا
leftوrightتبدأان كـNone.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
n = Node(5)
print(n.value) # 5
print(n.left) # None
إدخال قيمة
- ابدأ من الجذر. إذا كانت الشجرة فارغة، تصبح القيمة الجديدة الجذر.
- إذا كانت القيمة أصغر من العقدة الحالية، اذهب يسارًا؛ وإلا اذهب يمينًا.
- كرر حتى تصل إلى مكان فارغ، وضع العقدة الجديدة هناك.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
root = None
for v in [5, 3, 8, 1]:
root = insert(root, v)
print(root.value) # 5
print(root.left.value) # 3
print(root.right.value) # 8
المسار الترتيبي يعطي ترتيبًا مرتبًا
- الترتيب الداخلي يزور: الفرع الأيسر، ثم العقدة، ثم الفرع الأيمن.
- بسبب قاعدة شجرة البحث الثنائي (BST)، يتم زيارة القيم بترتيب مرتبط — مجاناً.
- هي بطبيعتها تكرارية: traversal يسار، خذ القيمة، traversal يمين.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def in_order(root):
if root is None:
return []
return in_order(root.left) + [root.value] + in_order(root.right)
root = None
for v in [5, 3, 8, 1, 4]:
root = insert(root, v)
print(in_order(root)) # [1, 3, 4, 5, 8]
البحث سريع
- لإيجاد قيمة، قارنها بالعقدة، ثم اذهب يسار أو يمين — متجاوزاً نصف الشجرة في كل خطوة.
- في شجرة متوازنة يستغرق ذلك حوالي
O(log n)خطوات، أسرع بكثير من مسح قائمة. - شجرة سيئة الشكل (قيم مُدرجة مسبقاً) يمكن أن تتدهور إلى خط —
O(n).
أخطاء شائعة
- في شجرة البحث الثنائية: الطفل الأيسر < العقدة <= الطفل الأيمن (القيم المتساوية تذهب لليمين هنا).
- الشجرة غير المتوازنة تفقد ميزة السرعة.
الآن جرب بنفسك
- بنِ العمليات الأساسية الثلاث:
insert،in_order، وcontains. - تم توفير فصل
Node(وفصلinsertيعمل، حيث تحتاجه). - اضغط تحقق من الإجابة لاختباره على عدة أشجار.
البحث في شجرة BST
الأيسر أصغر، والأيمن أكبر — لذا كل خطوة تتجاوز نصف الشجرة.
الصعوبة 5/5 · 400 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
فئة Node مُقدَّمة. اكتب insert(root, value) التي تضيف value إلى شجرة BST وتُرجع الجذر. إذا كان root هو None، أرجع Node(value) جديداً. إذا كان value < root.value اذهب يساراً، وإلا اذهب يميناً — وأعد تعيين ذلك الابن لناتج الإدراج فيه.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 5/5 · 400 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Node وinsert تعملان مُقدَّمان. اكتب in_order(root) الذي يُرجع قائمة من القيم من خلال traversal ترتيبية: الفرع الأيسر، ثم قيمة هذا العقدة، ثم الفرع الأيمن. بفضل قاعدة BST تظهر القائمة مرتبة. شجرة فارغة (None) تُعطي [].
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 5/5 · 400 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Node وinsert تعملان مُقدَّمان. اكتب contains(root, value) الذي يُرجع True إذا كان value في الشجرة، وإلا False. استخدم قاعدة BST: إذا تساوي هذا العقدة أرجع True؛ إذا كانت أصغر ابحث يساراً، وإلا ابحث يميناً؛ فرع فارغ (None) يعني أنه غير موجود.
اضغط تشغيل لرؤية المخرجات هنا.