مقدمة إلى هياكل البيانات في بايثون – الأشجار الثنائية للبحث
تعتبر الأشجار الثنائية للبحث (Binary Search Trees) من بين الهياكل البيانية الأساسية والتي تُستخدم في تخزين البيانات بشكل يسمح بإجراء عمليات البحث والإدراج والحذف بكفاءة عالية. في بايثون، يمكن تمثيل الشجرة الثنائية للبحث باستخدام الكائنات والفئات (classes). تتميز هذه الأشجار بخصائص معينة تجعل من الوصول إلى البيانات أكثر سرعة وفعالية، حيث يتم تخزين كل عقدة (Node) في الشجرة بحيث تكون كل القيم في العقدة اليسرى أقل من قيمة العقدة نفسها، وكل القيم في العقدة اليمنى أكبر منها. هذه الخاصية تجعل من عملية البحث عملية ذات تعقيد زمني لوجاريتمي في المتوسط.
لنبدأ بإنشاء فئة تمثل العقدة في الشجرة. كل عقدة تحتوي على قيمة بالإضافة إلى مراجع للعقدتين اليسرى واليمنى. يمكننا في بايثون تعريف هذه الفئة بسهولة باستخدام الكائنات. إليك مثالاً بسيطاً عن كيفية تعريف عقدة شجرة:
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
عمليات أساسية على الأشجار الثنائية للبحث
تعتبر العمليات الأساسية على الأشجار الثنائية للبحث هي الإدراج، البحث، والحذف. كل عملية من هذه العمليات تستفيد من خاصية الترتيب الموجودة في الشجرة الثنائية للبحث.
عملية الإدراج تتطلب منا مقارنة القيمة الجديدة مع العقد الموجودة في الشجرة، بدءًا من الجذر. إذا كانت القيمة أقل من قيمة العقدة الحالية، ننتقل إلى العقدة اليسرى، وإذا كانت أكبر، ننتقل إلى العقدة اليمنى. نستمر في هذه العملية حتى نجد مكان العقدة المناسبة. إليك مثال عن كيفية تنفيذ عملية الإدراج:
def insert(root, key):
if root is None:
return Node(key)
else:
if root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root
أما عملية البحث فتتم بشكل مشابه، حيث نقارن القيمة المطلوبة مع قيم العقد الموجودة. إذا وجدنا القيمة، نعيد العقدة، وإذا لم نجدها نعيد None. الحذف هو العملية الأكثر تعقيدًا بين هذه العمليات، حيث يتعين علينا إعادة تنظيم الشجرة بعد إزالة العقدة. هناك ثلاث حالات رئيسية في الحذف: العقدة المراد حذفها ليس لها أبناء، أو لها ابن واحد، أو لها ابنان. كل حالة تتطلب معالجة خاصة لضمان بقاء الشجرة مرتبة بشكل صحيح.
تعتبر الأشجار الثنائية للبحث من الهياكل البيانية الفعالة في العديد من التطبيقات التي تتطلب عمليات بحث متكررة وسريعة، مثل قواعد البيانات ومحركات البحث. توفر لنا بايثون الأدوات اللازمة لتطبيق هذه الهياكل بسهولة وكفاءة.