Python3

سری چهارم: درخت‌ها (Trees) 🌳

پارت ۵: درخت‌های متوازن (Balanced Trees) ⚖️🌲

سلام دوستان! 😊 امروز توی پارت پنجم، یکی از مباحث مهم و پیشرفته درخت‌ها رو بررسی می‌کنیم: درخت‌های متوازن (Balanced Trees). متوازن‌سازی درخت‌ها باعث می‌شه که عملیات‌های جستجو، درج و حذف کارآمدتر باشن و درخت همیشه در بهترین حالت عملکرد باقی بمونه. بیایید شروع کنیم! 🚀

درخت متوازن چیست؟ 🤔

یک درخت متوازن، درختیه که در آن ارتفاع دو زیر درخت چپ و راست هر گره تفاوت زیادی با هم نداشته باشن. به عبارت دیگر، اختلاف ارتفاع زیر درخت‌های چپ و راست یک گره نباید از یک مقدار مشخص (معمولاً ۱) بیشتر باشه. این تعادل باعث می‌شه که ارتفاع درخت تقریباً برابر log(n) باشه که n تعداد گره‌های درخته.

چرا متوازن‌سازی مهم است؟ 🌟

اگر درخت جستجوی دودویی (BST) متوازن نباشه، ممکنه در بدترین حالت به یک لیست پیوندی خطی تبدیل بشه، که در این صورت تمام عملیات‌های درج، جستجو و حذف به O(n) می‌رسن. در حالی که اگر درخت متوازن باشه، این عملیات‌ها به O(log n) کاهش پیدا می‌کنن.

انواع درخت‌های متوازن 🌳

چند نوع درخت متوازن معروف وجود دارن که هر کدوم ویژگی‌ها و الگوریتم‌های خاص خودشون رو دارن:

1. درخت AVL 🌲
- تعریف: درخت AVL یکی از اولین انواع درخت‌های متوازن جستجوگره. این درخت طوری طراحی شده که ارتفاع دو زیر درخت چپ و راست هر گره حداکثر ۱ اختلاف داشته باشه.
- عملیات: وقتی یک گره جدید به درخت اضافه یا از درخت حذف می‌شه، ممکنه تعادل درخت به هم بخوره. برای بازیابی تعادل، از چرخش‌های (Rotations) مختلف استفاده می‌کنیم.
- پیچیدگی زمانی: O(log n) برای درج، جستجو و حذف.

2. درخت Red-Black 🎨⚫
- تعریف: درخت Red-Black نوع دیگه‌ای از درخت‌های متوازنه که در اون هر گره به یکی از دو رنگ قرمز یا سیاه رنگ‌آمیزی می‌شه. این درخت قوانین خاصی داره که باعث می‌شه ارتفاع درخت متوازن باقی بمونه.
- ویژگی‌ها: درخت Red-Black همیشه یک درخت نیمه‌متوازنه که تضمین می‌کنه هیچ مسیری درخت بیش از دو برابر مسیر کوتاه‌ترین مسیر نباشه.
- پیچیدگی زمانی: O(log n) برای تمام عملیات‌ها.

پیاده‌سازی ساده درخت AVL 🛠️

در ادامه، یک پیاده‌سازی ساده از درخت AVL رو بررسی می‌کنیم.

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

def get_height(node):
    if not node:
        return 0
    return node.height

def update_height(node):
    node.height = 1 + max(get_height(node.left), get_height(node.right))

def get_balance(node):
    if not node:
        return 0
    return get_height(node.left) - get_height(node.right)

def rotate_right(y):
    x = y.left
    T2 = x.right

    x.right = y
    y.left = T2

    update_height(y)
    update_height(x)

    return x

def rotate_left(x):
    y = x.right
    T2 = y.left

    y.left = x
    x.right = T2

    update_height(x)
    update_height(y)

    return y

def insert(node, value):
    if not node:
        return Node(value)

    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)

    update_height(node)

    balance = get_balance(node)

    if balance > 1:
        if value < node.left.value:
            return rotate_right(node)
        else:
            node.left = rotate_left(node.left)
            return rotate_right(node)

    if balance < -1:
        if value > node.right.value:
            return rotate_left(node)
        else:
            node.right = rotate_right(node.right)
            return rotate_left(node)

    return node

مفهوم چرخش (Rotations) در درخت AVL 🔄

- چرخش به راست (Right Rotation): وقتی یک زیر درخت چپ بیش از حد رشد می‌کنه.
- چرخش به چپ (Left Rotation): وقتی یک زیر درخت راست بیش از حد رشد می‌کنه.
- چرخش دوگانه به راست-چپ و چپ-راست (Left-Right and Right-Left Rotations): برای زمانی که ترکیبی از عدم تعادل در زیر درخت‌ها وجود داره.

این چرخش‌ها کمک می‌کنن که درخت دوباره متوازن بشه و ارتفاع درخت کاهش پیدا کنه.

بررسی پیچیدگی زمانی در درخت‌های متوازن ⏱️

- جستجو: O(log n)
- درج: O(log n)
- حذف: O(log n)

این پیچیدگی‌ها نشان می‌ده که درخت‌های متوازن حتی در بدترین حالت هم عملکرد مناسبی دارن و برای کاربردهای واقعی بسیار مناسب هستن.

👍1

57 views20:41