=====تجزیه سبک-سنگین درخت‌ها=====

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


=====تعریف=====

تجزیه سبک-سنگین درخت $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$ یال سبک خواهد داشت.**


=====ساخت و ساز=====
مسیر‌ها به کمک شبه‌کد زیر بدست می‌آیند.
<code>
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)
</code>
حال تمام مسیر‌ها به کمک این خط بدست می‌آیند.

<code>
allPaths.append(getPath(root))
</code>
دقت کنید که با این روش ساخت‌ و ساز هر یال سنگین است اگر و تنها اگر دو راس آن در یک مسیر باشند. این روش یال‌های سنگین بیشتری ایجاد می‌کند(نسبت به یال‌هایی که بر اساس تعریف نیاز است).