المپدیا

تجزیه یک درخت ریشه‌دار به مسیر‌های مجزای سبک و سنگین،‌ روشی است که راه‌حل‌های بهینه‌ای برای حل بعضی مسائل درخت‌ها ارائه می‌دهد.

تجزیه سبک-سنگین درخت $T = (V, E)$ رنگ‌آمیزی‌ای از یال‌‌های درخت با رنگ‌های سبک و سنگین است. برای تعیین رنگ یال $e$،‌ سری از آن که به ریشه نزدیک تر است را $v$ و دیگری را $u$ بنامید. رنگ $e$ سنگین است اگر و فقط اگر اندازه زیر‌درخت $u$ بزرگتر از نصف اندازه زیر‌درخت $v$ باشد.

اندازه زیردرخت $v$ را $size(v)$ می‌نامیم. فرض کنید راس $v$ دو فرزند $u$ و $w$ دارد که یال‌های $v-u$ و $v-w$ سنگین است. پس داریم:
$size(u) + size(w) > 1/2 size(v) + 1/2 size(v) = size(v)$
این متناقض است که با دانسته ما که می‌دانیم:
$size(u) + size(w) + 1 <= size(v)$
در نتیجه هر راس حداکثر یک یال سنگین دارد که به فرزندانش می‌رود.

در ضمن حداکثر دو یال هر راس می‌تواند سنگین باشد، یک یال به فرزند و یک یال به پدر. حال زیرگرافی از $T$ را در نظر بگیرید که تمام یال‌های سبک از آن حذف شده‌اند. حال تمام مولفه‌های همبند مسیر‌ند(که می‌توانند راس‌های تنها نیز باشند) و هر دو راس مجاور اختلاف ارتفاع یک دارند. در نتیجه یال‌های سنگین و راس‌هایی که روی آن‌ها واقع شده‌اند، درخت را به مسیر‌های مجزایی تقسیم می‌کنند که هر کدام قسمتی از مسیر ریشه به یک برگ است.

حال فرض کنید درختی N راس دارد. اگر از ریشه با یال سبکی پایین رویم، اندازه زیردرخت راسی که روی آن هستیم حداکثر برابر $ٔN/2$ است. اگر باز این کار را ادامه دهیم به زیر‌درختی به اندازه $N/4$ می‌رسیم. اگر این کار را ادامه دهیم مشاهده می‌کنیم که تعداد یال‌های سبک هر مسیر از ریشه به برگ حداکثر $lgN$ یال سبک خواهد داشت.

مسیر‌ها به کمک شبه‌کد زیر بدست می‌آیند.

def getPath(node):
    if node is a leaf:
        return [node]
    for each subtree S:
        if S is not the largest subtree:
            allPaths.append(getPath(S))
    for each subtree S:
        if S is the largest subtree:
            return getPath(S).append(node)

حال تمام مسیر‌ها به کمک این خط بدست می‌آیند.

allPaths.append(getPath(root))

دقت کنید که با این روش ساخت‌ و ساز هر یال سنگین است اگر و تنها اگر دو راس آن در یک مسیر باشند. این روش یال‌های سنگین بیشتری ایجاد می‌کند(نسبت به یال‌هایی که بر اساس تعریف نیاز است).