تاريخ شجرة AVL
تم اختراع شجرة AVL في عام 1962 من قبل ج. م. أدلسون-فيلسكي وي. م. لانديس، وهما عالمان سوفييتيان. كانت أول هيكل بيانات لشجرة بحث ثنائية ذاتية الموازنة يتم تطويره. أدى عملهما الرائد إلى تطوير هياكل بيانات أكثر تعقيدًا ذاتية الموازنة مثل أشجار الأحمر والأسود وأشجار B.
مبدأ التوازن الذاتي
تعتمد أشجار AVL على مبدأ التوازن الذاتي لضمان الأداء الأمثل. عندما تتسبب عملية الإدراج أو الحذف في أن تصبح الشجرة غير متوازنة (أي أن عامل توازن العقدة يقع خارج النطاق من -1 إلى 1)، يتم إجراء الدوران لإعادة التوازن إلى الشجرة. هناك أربعة أنواع أساسية من الدورانات:
- الدوران الأيمن المفرد: يُستخدم عندما تكون الشجرة الفرعية اليسرى للعقدة اليسرى ثقيلة جدًا.
- الدوران الأيسر المفرد: يُستخدم عندما تكون الشجرة الفرعية اليمنى للعقدة اليمنى ثقيلة جدًا.
- الدوران الأيسر-الأيمن المزدوج: يُستخدم عندما تكون الشجرة الفرعية اليمنى للعقدة اليسرى ثقيلة جدًا.
- الدوران الأيمن-الأيسر المزدوج: يُستخدم عندما تكون الشجرة الفرعية اليسرى للعقدة اليمنى ثقيلة جدًا.
تُستخدم هذه الدورانات لإعادة ترتيب العقد في الشجرة، وبالتالي تقليل الارتفاع وضمان بقاء الشجرة متوازنة. بعد كل عملية إدراج أو حذف، يجب فحص عامل توازن كل عقدة على طول المسار من العقدة المدرجة أو المحذوفة إلى الجذر، ويجب إجراء الدورانات حسب الحاجة للحفاظ على توازن الشجرة.
عامل التوازن
عامل التوازن لعقدة في شجرة AVL هو الفرق بين ارتفاع الشجرة الفرعية اليسرى وارتفاع الشجرة الفرعية اليمنى. رياضياً، يتم تعريفه على النحو التالي:
عامل_التوازن(عقدة) = ارتفاع(الشجرة_الفرعية_اليسرى) - ارتفاع(الشجرة_الفرعية_اليمنى)
يجب أن يكون عامل التوازن لكل عقدة في شجرة AVL إما -1 أو 0 أو 1. إذا أصبح عامل التوازن لعقدة ما خارج هذا النطاق، فهذا يعني أن الشجرة غير متوازنة ويجب إجراء الدوران لإعادة التوازن إليها.
عمليات الإدراج
لإدراج عقدة جديدة في شجرة AVL، نبدأ بإجراء إدراج شجرة بحث ثنائية قياسي. بعد ذلك، يجب علينا تتبع المسار من العقدة المدرجة إلى الجذر وتحديث عوامل التوازن لكل عقدة على طول هذا المسار. إذا أصبح عامل التوازن لعقدة ما خارج النطاق من -1 إلى 1، فيجب علينا إجراء الدوران لإعادة التوازن إلى الشجرة. فيما يلي خطوات عملية الإدراج:
- أدرج العقدة الجديدة باستخدام إدراج شجرة بحث ثنائية قياسي.
- تتبع المسار من العقدة المدرجة إلى الجذر.
- لكل عقدة على طول المسار، قم بتحديث عامل التوازن الخاص بها.
- إذا أصبح عامل التوازن خارج النطاق من -1 إلى 1، فأجرِ الدوران المناسب.
عمليات الحذف
يشبه حذف عقدة من شجرة AVL عملية الإدراج. نبدأ بإجراء حذف شجرة بحث ثنائية قياسي. بعد ذلك، يجب علينا تتبع المسار من العقدة المحذوفة (أو سلفها إذا تم استبدالها) إلى الجذر وتحديث عوامل التوازن لكل عقدة على طول هذا المسار. إذا أصبح عامل التوازن لعقدة ما خارج النطاق من -1 إلى 1، فيجب علينا إجراء الدوران لإعادة التوازن إلى الشجرة. فيما يلي خطوات عملية الحذف:
- احذف العقدة باستخدام حذف شجرة بحث ثنائية قياسي.
- تتبع المسار من العقدة المحذوفة (أو سلفها) إلى الجذر.
- لكل عقدة على طول المسار، قم بتحديث عامل التوازن الخاص بها.
- إذا أصبح عامل التوازن خارج النطاق من -1 إلى 1، فأجرِ الدوران المناسب.
مقارنة مع أشجار البحث الثنائية الأخرى
تتفوق أشجار AVL على أشجار البحث الثنائية غير المتوازنة من حيث الأداء، خاصة بالنسبة لمجموعات البيانات الكبيرة. في أسوأ الحالات، يمكن أن تتدهور أشجار البحث الثنائية غير المتوازنة إلى قائمة مرتبطة، مما يؤدي إلى وقت بحث O(n). تضمن أشجار AVL وقت بحث O(log n) في جميع الحالات.
بالمقارنة مع أشجار الأحمر والأسود، تتمتع أشجار AVL بتوازن أكثر صرامة، مما يؤدي إلى أوقات بحث أسرع. ومع ذلك، غالبًا ما تكون أشجار AVL أبطأ من أشجار الأحمر والأسود لعمليات الإدراج والحذف لأنها قد تتطلب المزيد من الدورانات للحفاظ على التوازن. بشكل عام، تُفضل أشجار AVL عندما تكون عمليات البحث أكثر تكرارًا من عمليات الإدراج والحذف.
تطبيقات شجرة AVL
تُستخدم أشجار AVL في مجموعة متنوعة من التطبيقات، بما في ذلك:
- قواميس البيانات: يمكن استخدام أشجار AVL لتنفيذ قواميس البيانات التي تتطلب أوقات بحث وإدراج وحذف فعالة.
- الفهرسة: يمكن استخدام أشجار AVL لفهرسة البيانات في قواعد البيانات وأنظمة الملفات.
- التوجيه: يمكن استخدام أشجار AVL لتنفيذ جداول التوجيه في أجهزة التوجيه والمحولات.
- الضغط: يمكن استخدام أشجار AVL لتمثيل جداول الترميز في خوارزميات الضغط.
مثال على تنفيذ شجرة AVL (بشفرة زائفة)
فيما يلي مثال مبسط على كيفية تنفيذ شجرة AVL باستخدام شفرة زائفة:
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
def height(node):
if node is None:
return 0
return node.height
def balance_factor(node):
if node is None:
return 0
return height(node.left) - height(node.right)
def rotate_right(y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
y.height = 1 + max(height(y.left), height(y.right))
x.height = 1 + max(height(x.left), height(x.right))
return x
def rotate_left(x):
y = x.right
T2 = y.left
y.left = x
x.right = T2
x.height = 1 + max(height(x.left), height(x.right))
y.height = 1 + max(height(y.left), height(y.right))
return y
def insert(root, key):
# 1. Perform standard BST insert
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
else:
return root # Duplicate keys not allowed
# 2. Update height of current node
root.height = 1 + max(height(root.left), height(root.right))
# 3. Get the balance factor
balance = balance_factor(root)
# 4. If the node is unbalanced, then try out the 4 cases
# Case 1 - Left Left
if balance > 1 and key < root.left.key:
return rotate_right(root)
# Case 2 - Right Right
if balance < -1 and key > root.right.key:
return rotate_left(root)
# Case 3 - Left Right
if balance > 1 and key > root.left.key:
root.left = rotate_left(root.left)
return rotate_right(root)
# Case 4 - Right Left
if balance < -1 and key < root.right.key:
root.right = rotate_right(root.right)
return rotate_left(root)
return root
يوضح هذا المثال الأساسيات، ولكن التنفيذ الكامل يتضمن معالجة الحذف وجميع الحالات الحدودية.
مزايا وعيوب أشجار AVL
المزايا:
- أوقات بحث سريعة (O(log n))
- أداء موثوق به حتى في أسوأ الحالات
- توازن ذاتي يمنع التدهور إلى قائمة مرتبطة
العيوب:
- تعقيد التنفيذ أعلى من أشجار البحث الثنائية غير المتوازنة
- قد تتطلب عمليات الإدراج والحذف المزيد من الدورانات مقارنة بأشجار الأحمر والأسود
- أعلى قليلاً من حيث المساحة بسبب الحاجة لتخزين عامل التوازن لكل عقدة
خاتمة
شجرة AVL هي هيكل بيانات قوي يوفر أداءً فعالاً لعمليات البحث والإدراج والحذف. إنها توازن ذاتي، مما يضمن أن ارتفاع الشجرة يظل لوغاريتميًا، حتى مع إدخال أو إزالة البيانات. على الرغم من أن تنفيذها أكثر تعقيدًا من أشجار البحث الثنائية غير المتوازنة، إلا أن فوائد الأداء تجعلها خيارًا شائعًا للعديد من التطبيقات. ومع ذلك، يجب على المطورين مراعاة المفاضلات بين أشجار AVL وهياكل البيانات الأخرى ذاتية الموازنة مثل أشجار الأحمر والأسود لاختيار الحل الأنسب لاحتياجاتهم الخاصة.