127- كورس لغة بايثون Python شرح هياكل البيانات في بايثون – Python Data Structures – AVL Trees

مقدمة إلى هيكل البيانات AVL Trees في بايثون

تعد شجرة AVL نوعًا من الأشجار الثنائية المتزنة، والتي تضمن أن تظل الشجرة متزنة بعد كل عملية إدراج أو حذف. تم تسمية هذه الشجرة نسبة إلى مخترعيها G.M. Adelson-Velsky و E.M. Landis. يتميز هذا النوع من الأشجار بكونه يوفر عمليات بحث وإدراج وحذف بشكل فعال، حيث يضمن أن يكون الفرق بين ارتفاع الشجرتين الفرعيتين لأي عقدة لا يزيد عن 1. هذا التوازن يتيح تحسين أداء العمليات إلى O(log n).

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

عمليات أساسية في شجرة AVL

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

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

مثال على شجرة AVL في بايثون

لنلقِ نظرة على مثال بسيط لشجرة AVL في بايثون. سنقوم بتعريف فئة Node وفئة AVLTree. تحتوي فئة Node على القيم والمراجع للعقد الفرعية، بينما تحتوي فئة AVLTree على العمليات الأساسية مثل الإضافة والتوازن.

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.height = 1
        self.key = key

class AVLTree:
    def insert(self, root, key):
        if not root:
            return Node(key)
        elif key < root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

        root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
        balance = self.getBalance(root)

        if balance > 1 and key < root.left.key:
            return self.rightRotate(root)
        if balance < -1 and key > root.right.key:
            return self.leftRotate(root)
        if balance > 1 and key > root.left.key:
            root.left = self.leftRotate(root.left)
            return self.rightRotate(root)
        if balance < -1 and key < root.right.key:
            root.right = self.rightRotate(root.right)
            return self.leftRotate(root)

        return root

    def leftRotate(self, z):
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
        return y

    def rightRotate(self, z):
        y = z.left
        T3 = y.right
        y.right = z
        z.left = T3
        z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
        return y

    def getHeight(self, root):
        if not root:
            return 0
        return root.height

    def getBalance(self, root):
        if not root:
            return 0
        return self.getHeight(root.left) - self.getHeight(root.right)

    def preOrder(self, root):
        if not root:
            return
        print("{0} ".format(root.key), end="")
        self.preOrder(root.left)
        self.preOrder(root.right)

tree = AVLTree()
root = None
nums = [10, 20, 30, 40, 50, 25]
for num in nums:
    root = tree.insert(root, num)
print("Preorder traversal of the constructed AVL tree is")
tree.preOrder(root)

في هذا المثال، نقوم بإنشاء شجرة AVL وإدراج عناصر متعددة بها. بعد إدراج كل عنصر، نقوم بطباعة الترتيب السابق للعقد لتوضيح كيف يتم تعديل الشجرة للحفاظ على التوازن.