درخت های AVL (AVL Trees)
درخت های AVL نوعی «درخت جستجوی دودویی (BST)» خودمتعادل هستند. یعنی «ارتفاع (Height)» کم می ماند. بنابراین جستجو، درج، و حذف خیلی سریع می شوند؛ حدود O(log n).
ایده اصلی تعادل در AVL
«عامل تعادل (Balance Factor)» اختلاف ارتفاع زیر درخت راست و چپ است. اگر قدرمطلقش بیش از 1 شود، با «چرخش (Rotation)» درستش می کنیم؛ مثل LL، RR، LR، و RL.
نکته: چرخش فقط والد زیر درخت را عوض می کند تا ترتیب درون گرد حفظ شود.
پیاده سازی درج و چرخش ها
طبق منبع، این کد درج را با محاسبه ارتفاع، عامل تعادل، و چرخش ها انجام می دهد.
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.height = 1
def getHeight(node):
if not node:
return 0
return node.height
def getBalance(node):
if not node:
return 0
return getHeight(node.left) - getHeight(node.right)
def rightRotate(y):
print('Rotate right on node', y.data)
x = y.left
T2 = x.right
x.right = y
y.left = T2
y.height = 1 + max(getHeight(y.left), getHeight(y.right))
x.height = 1 + max(getHeight(x.left), getHeight(x.right))
return x
def leftRotate(x):
print('Rotate left on node', x.data)
y = x.right
T2 = y.left
y.left = x
x.right = T2
x.height = 1 + max(getHeight(x.left), getHeight(x.right))
y.height = 1 + max(getHeight(y.left), getHeight(y.right))
return y
def insert(node, data):
if not node:
return TreeNode(data)
if data < node.data:
node.left = insert(node.left, data)
elif data > node.data:
node.right = insert(node.right, data)
node.height = 1 + max(getHeight(node.left), getHeight(node.right))
balance = getBalance(node)
if balance > 1 and getBalance(node.left) >= 0:
return rightRotate(node)
if balance > 1 and getBalance(node.left) < 0:
node.left = leftRotate(node.left)
return rightRotate(node)
if balance < -1 and getBalance(node.right) <= 0:
return leftRotate(node)
if balance < -1 and getBalance(node.right) > 0:
node.right = rightRotate(node.right)
return leftRotate(node)
return node
def inOrderTraversal(node):
if node is None:
return
inOrderTraversal(node.left)
print(node.data, end=", ")
inOrderTraversal(node.right)
root = None
letters = ['C', 'B', 'E', 'A', 'D', 'H', 'G', 'F']
for letter in letters:
root = insert(root, letter)
inOrderTraversal(root)
حذف گره در AVL
طبق منبع، حذف مانند BST است و سپس تعادل باید بازیابی شود. نمونه زیر حذف پایه را نشان می دهد.
def minValueNode(node):
current = node
while current.left is not None:
current = current.left
return current
def delete(node, data):
if not node:
return node
if data < node.data:
node.left = delete(node.left, data)
elif data > node.data:
node.right = delete(node.right, data)
else:
if node.left is None:
temp = node.right
node = None
return temp
elif node.right is None:
temp = node.left
node = None
return temp
temp = minValueNode(node.right)
node.data = temp.data
node.right = delete(node.right, temp.data)
return node
def inOrderTraversal(node):
if node is None:
return
inOrderTraversal(node.left)
print(node.data, end=", ")
inOrderTraversal(node.right)
root = None
letters = ['C', 'B', 'E', 'A', 'D', 'H', 'G', 'F']
for letter in letters:
root = insert(root, letter)
inOrderTraversal(root)
گام های عملی
- پس از هر درج، ارتفاع را به روز کن.
- عامل تعادل هر نود را حساب کن.
- اگر خارج از [-1, 1] بود، چرخش مناسب بزن.
نکته: LL ⇢ راست چرخش. RR ⇢ چپ چرخش. LR ⇢ چپ روی فرزند، بعد راست. RL ⇢ راست روی فرزند، بعد چپ.
جمع بندی سریع
- AVL همیشه تقریباً کوتاه می ماند.
- عامل تعادل، کلید تشخیص نابرابری است.
- چهار حالت چرخش داریم: LL, RR, LR, RL.
- زمان عملیات حدود
O(log n)است.
برای ادامه مسیر، صفحه درخت جستجوی دودویی و هیپ ها را ببین.