درخت: وقتی رابطه سلسله‌مراتبی است

در این فصل چه یاد می‌گیری#

تا این‌جا هر ظرفی که ساختیم یک دنباله بود: چیزها پشتِ سرِ هم. ولی خیلی از رابطه‌ها پشتِ سرِ هم نیستند — پوشه‌ای که پوشه‌های دیگری داخلش هست، بخشی از یک سند که زیربخش دارد، تصمیمی که به دو تصمیمِ دیگر منشعب می‌شود. شکلِ این‌ها درخت است.

درخت را با همان چیزی می‌سازیم که در ترمِ ۲ ساختیم — گره و ارجاع — فقط این بار هر گره دو ارجاع دارد. بعد یک عدد را اندازه می‌گیریم که کلِ این ترم دربارهٔ آن است: ارتفاع. با هشت برابر شدنِ تعدادِ گره‌ها، ارتفاعِ یک درختِ کامل از 9 به 12 می‌رود — سه واحد. همان تعدادِ گره در یک درختِ بدشکل، ارتفاعش از 1,022 به 8,190 می‌رسد.

آخر این فصل می‌توانی:

• یک درخت را با listهای سه‌خانه‌ای بسازی و گره، ریشه و برگش را نشان بدهی
• عمقِ یک گره را از ارتفاعِ یک درخت جدا کنی
• ارتفاع را به‌عنوان هزینه بخوانی، نه به‌عنوان یک ویژگیِ تزئینی
• بگویی چرا recursion روی درختِ بدشکل می‌شکند

قبل از شروع#

از ترمِ ۲ فصلِ ۶: گره به‌عنوان یک list کوچک، و ارجاع به گرهٔ بعدی. آن فصل با یک ارجاع کار می‌کرد؛ این‌جا فقط یکی اضافه می‌شود.

از ترمِ ۱ فصلِ ۵: ستونِ نسبت. نزدیکِ 2 یعنی خطی، و کمی بالای 1 و رو به کاهش یعنی log n. هر دو شکل در همین فصل می‌آیند.

📓 نوت‌بوک: نوت‌بوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

۱. کوچک‌ترین نسخهٔ ممکن، با دست#

یک گرهِ درخت سه چیز لازم دارد: مقدار، ارجاع به فرزندِ چپ، و ارجاع به فرزندِ راست. پس یک list سه‌خانه‌ای کافی است. گره‌ای که هیچ فرزندی ندارد، هر دو ارجاعش None است و اسمش برگ است. گرهی که هیچ‌کس به آن ارجاع نمی‌دهد ریشه است.

درختی که هر گره‌اش حداکثر دو فرزند دارد، binary tree نام دارد و کلِ این ترم با همین کار می‌کند.

VALUE, LEFT, RIGHT = 0, 1, 2


def leaf(value):
    """برگ: گره‌ای که هر دو ارجاعش None است."""
    return [value, None, None]


tiny = [1,
        [2, leaf(4), leaf(5)],
        [3, None, leaf(6)]]

print("خودِ ساختار  :", tiny)
print("ریشه         :", tiny[VALUE])
print("فرزندانِ ریشه:", tiny[LEFT][VALUE], "و", tiny[RIGHT][VALUE])
print("زیرِ گرهٔ ۳   :", tiny[RIGHT][LEFT], "و", tiny[RIGHT][RIGHT][VALUE])

خودِ ساختار  : [1, [2, [4, None, None], [5, None, None]], [3, None, [6, None, None]]]
ریشه         : 1
فرزندانِ ریشه: 2 و 3
زیرِ گرهٔ ۳   : None و 6

کلِ ساختار همین است. خطِ اول را با دقت بخوان: درخت، listی است که داخلش list است و داخلِ آن باز list. هیچ کلاسی، هیچ کتابخانه‌ای، هیچ چیزِ تازه‌ای در کار نیست — فقط همان گرهِ ترمِ ۲، با یک خانهٔ اضافه.

گرهٔ 3 فرزندِ چپ ندارد و فرزندِ راستش 6 است. این نامتقارنی مجاز است، و در بخشِ ۳ می‌بینی که وقتی از حد بگذرد چه بلایی سرِ هزینه می‌آورد.

۲. عمق مالِ گره است، ارتفاع مالِ درخت#

دو کلمه که خیلی راحت جایشان عوض می‌شود:

• عمقِ یک گره: چند یال از ریشه تا آن گره. عمقِ ریشه صفر است.
• ارتفاعِ یک درخت: بلندترین مسیر از ریشه تا یک برگ.

یعنی ارتفاعِ درخت، بیشترین عمقِ گره‌هایش است. هر دو را با recursion می‌شود حساب کرد — و منطقش همان منطقِ ترمِ ۴ است: حالتِ پایه، به‌علاوهٔ همان سؤال روی زیردرخت‌ها.

def height(node):
    """بلندترین مسیر از این گره تا یک برگ، شمرده بر حسبِ تعدادِ یال."""
    if node is None:
        return -1
    return 1 + max(height(node[LEFT]), height(node[RIGHT]))


def depths(node, depth=0, found=None):
    """همان بازگشت، این بار عمقِ هر گره را جمع می‌کند."""
    if found is None:
        found = []
    if node is not None:
        found.append((node[VALUE], depth))
        depths(node[LEFT], depth + 1, found)
        depths(node[RIGHT], depth + 1, found)
    return found


print("عمقِ هر گره     :", depths(tiny))
print("ارتفاعِ کلِ درخت:", height(tiny))
print("ارتفاعِ زیردرختِ ۲:", height(tiny[LEFT]), "· ارتفاعِ زیردرختِ ۳:", height(tiny[RIGHT]))

عمقِ هر گره     : [(1, 0), (2, 1), (4, 2), (5, 2), (3, 1), (6, 2)]
ارتفاعِ کلِ درخت: 2
ارتفاعِ زیردرختِ ۲: 1 · ارتفاعِ زیردرختِ ۳: 1

درختِ خالی ارتفاعِ -1 دارد. این یک قرارداد است، نه یک حقیقت، و دلیلش راحتیِ حساب است: با این قرارداد ارتفاعِ یک برگ می‌شود 1 + max(-1, -1) که همان صفر است — یعنی «از این گره تا یک برگ، صفر یال». اگر جایی عددت یکی بیشتر یا کمتر از انتظار درآمد، اول همین قرارداد را چک کن.

۳. یک تعدادِ گره، دو ارتفاعِ کاملاً متفاوت#

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

درختِ کامل: هر گره یا دو فرزند دارد یا هیچ‌کدام، و همهٔ برگ‌ها هم‌عمق‌اند. زنجیر: هر گره فقط یک فرزندِ چپ دارد — که در واقع همان linked list ترمِ ۲ است، فقط با یک خانهٔ خالیِ اضافه.

def perfect(h, value=1):
    """درختِ کامل: هر گره یا دو فرزند دارد یا هیچ، و همهٔ برگ‌ها هم‌عمق‌اند."""
    if h < 0:
        return None
    return [value, perfect(h - 1, 2 * value), perfect(h - 1, 2 * value + 1)]


def chain(n):
    """n گره که هر کدام فقط یک فرزندِ چپ دارد."""
    node = None
    for v in range(n, 0, -1):
        node = [v, node, None]
    return node


def size(node):
    """تعدادِ کلِ گره‌ها."""
    if node is None:
        return 0
    return 1 + size(node[LEFT]) + size(node[RIGHT])


full = perfect(3)
line = chain(15)
print(f"درختِ کامل: {size(full):>3} گره  ·  ارتفاع {height(full)}")
print(f"زنجیر     : {size(line):>3} گره  ·  ارتفاع {height(line)}")

درختِ کامل:  15 گره  ·  ارتفاع 3
زنجیر     :  15 گره  ·  ارتفاع 14

پانزده گره، ارتفاعِ 3 در برابرِ 14. و این تازه در اندازهٔ پانزده است.

🤔 اول حدس بزن: تعدادِ گره‌ها را دو برابر می‌کنیم. ارتفاعِ درختِ کامل چند برابر می‌شود، و ارتفاعِ زنجیر چند برابر؟ هر دو عدد را بنویس، بعد جدول را ببین.

def chain_height(node):
    """در زنجیر هر گره حداکثر یک فرزند دارد، پس یک حلقه کافی است."""
    h = -1
    while node is not None:
        h += 1
        node = node[LEFT]
    return h


forest = {}
for h in (9, 10, 11, 12):
    tree = perfect(h)
    forest[size(tree)] = tree
NODES = sorted(forest)

print("— درختِ کامل")
table([(n, height(forest[n])) for n in NODES], "ارتفاع", ",d")
print("\n— زنجیر با همان تعدادِ گره")
table([(n, chain_height(chain(n))) for n in NODES], "ارتفاع", ",d")

— درختِ کامل
         n            ارتفاع     نسبت به سطر قبل
     1,023                 9                   —
     2,047                10                1.11
     4,095                11                1.10
     8,191                12                1.09

— زنجیر با همان تعدادِ گره
         n            ارتفاع     نسبت به سطر قبل
     1,023             1,022                   —
     2,047             2,046                2.00
     4,095             4,094                2.00
     8,191             8,190                2.00

دو ستونِ نسبت، دو دنیای متفاوت.

ستونِ اول 1.11، 1.10، 1.09 است — کمی بالای یک و رو به کاهش. ترمِ ۱ فصلِ ۵ اسمِ این شکل را گفت: O(log n). با دو برابر شدنِ n فقط یک واحد به ارتفاع اضافه می‌شود، چون یک سطحِ تازه به درخت اضافه شده و آن سطح به‌تنهایی تقریباً به‌اندازهٔ کلِ سطوحِ بالای خودش گره دارد.

ستونِ دوم 2.00 است، یعنی O(n). زنجیر هیچ چیزی از درخت‌بودن نصیبش نشده؛ همان دنبالهٔ ترمِ ۲ است با ظاهرِ درخت.

۴. چرا ارتفاع همان هزینه است#

تا این‌جا ارتفاع فقط یک عدد بود. حالا ببینیم چه چیزی را می‌سنجد. برای رسیدن از ریشه به یک برگ، چند گره را باید ببینی؟

🤔 اول حدس بزن: این ادعای مرکزیِ کلِ ترم است، پس قبل از دیدنِ جدول بنویس: تعدادِ گره‌هایی که تا رسیدن به عمیق‌ترین برگ دیده می‌شوند، ستونِ نسبتش با کدام‌یک از دو جدولِ بخشِ ۳ یکی درمی‌آید — ستونِ ارتفاع یا هیچ‌کدام؟ و یک عددِ دقیق هم بنویس: در درختِ کاملِ 8,191 گره‌ای، چند گره؟

def descend(node):
    """از ریشه تا عمیق‌ترین برگِ سمتِ چپ پایین می‌رود و گره‌های دیده‌شده را می‌شمارد."""
    seen = 0
    while node is not None:
        seen += 1
        node = node[LEFT]
    return seen


print("— درختِ کامل: گره‌هایی که تا رسیدن به عمیق‌ترین برگ دیده می‌شوند")
table([(n, descend(forest[n])) for n in NODES], "گرهٔ دیده‌شده", ",d")
print("\n— زنجیر: همان کار، همان تعدادِ گره")
table([(n, descend(chain(n))) for n in NODES], "گرهٔ دیده‌شده", ",d")

— درختِ کامل: گره‌هایی که تا رسیدن به عمیق‌ترین برگ دیده می‌شوند
         n     گرهٔ دیده‌شده     نسبت به سطر قبل
     1,023                10                   —
     2,047                11                1.10
     4,095                12                1.09
     8,191                13                1.08

— زنجیر: همان کار، همان تعدادِ گره
         n     گرهٔ دیده‌شده     نسبت به سطر قبل
     1,023             1,023                   —
     2,047             2,047                2.00
     4,095             4,095                2.00
     8,191             8,191                2.00

در n = 8,191 یکی سیزده گره می‌بیند و دیگری هشت هزار و صد و نود و یک گره. ششصد و سی برابر، با تعدادِ گرهِ کاملاً یکسان.

و این جملهٔ ثابتِ کلِ ترم است: هزینهٔ رسیدن به یک گره، ارتفاع است — نه تعدادِ گره‌ها. تا وقتی ارتفاع کوچک بماند، بزرگ شدنِ درخت تقریباً رایگان است. کلِ فصلِ ۳ دربارهٔ همین «تا وقتی» است.

حالا امضای دوره را اجرا کنیم: مرتبه را اعلام کن، اندازهٔ بعدی را پیش‌بینی کن، بعد اجرا کن.

bigger = perfect(13)
predicted = 13
measured = height(bigger)
print(f"n = {size(bigger):,}  ·  پیش‌بینی {predicted}  ·  اندازه‌گیری {measured}")
print("خطای پیش‌بینی:", abs(measured - predicted))

n = 16,383  ·  پیش‌بینی 13  ·  اندازه‌گیری 13
خطای پیش‌بینی: 0

پیش‌بینی از خودِ جدول درآمد: آخرین سطر n = 8,191 بود با ارتفاعِ 12، و قاعده می‌گفت هر دو برابر شدنِ n یک واحد اضافه می‌کند. خطا صفر شد، و این‌جا اتفاقی نیست: شمارش قطعی است و ارتفاعِ درختِ کامل یک عددِ ساخته‌شده است، نه یک اندازه‌گیریِ نویزی.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ دو درخت با تعدادِ گرهِ کاملاً یکسان و شکلِ کاملاً متفاوت، روی دو سؤال: ارتفاع، و تعدادِ گره تا رسیدن به عمیق‌ترین برگ. در کدام بازهٔ n؟ ۱٬۰۲۳ تا ۸٬۱۹۱ گره، به‌علاوهٔ یک سطرِ پیش‌بینی در ۱۶٬۳۸۳. با چند تکرار، و کمینه یا میانگین؟ یک اجرا؛ هر دو عدد شمارش‌اند و شمارش قطعی است. هیچ عددِ ثانیه‌ای در این فصل نیست، چون هیچ نتیجه‌ای به سرعتِ ماشین بند نبود.

۵. جایی که recursion می‌شکند#

تابعِ height با recursion نوشته شده و روی درختِ کامل هیچ مشکلی ندارد: عمقِ بازگشتش به‌اندازهٔ ارتفاعِ درخت است، یعنی عددی حولِ سیزده که هیچ سقفی را تهدید نمی‌کند. ولی روی زنجیر، عمقِ بازگشت به‌اندازهٔ تعدادِ گره‌هاست.

🔧 اگر کار نکرد: به همین دلیل بود که ارتفاعِ زنجیر را با یک حلقه حساب کردیم، نه با height. اگر height را روی زنجیر صدا بزنی، همان چیزی را می‌گیری که ترمِ ۴ فصلِ ۱ نشانت داد:

try:
    print(height(chain(1_023)))
except RecursionError as err:
    print(f"{type(err).__name__}: {err}")

RecursionError: maximum recursion depth exceeded

عمقِ call stack سقف دارد، و روی زنجیر آن سقف دقیقاً همان‌جایی است که به آن می‌خوری. راهِ حلِ بد این است که سقف را بالا ببری؛ راهِ حلِ درست این است که بازگشت را با یک ساختارِ صریح جایگزین کنی — که موضوعِ فصلِ بعد است.

و نکتهٔ مهم‌تر: این خطا فقط یک دردسرِ فنی نیست. هر بار که آن را می‌بینی، درختت به تو گفته که ارتفاعش از حدِ معقول گذشته — یعنی همان چیزی که در بخشِ ۴ اندازه گرفتیم، این بار به‌شکلِ یک traceback.

✅ چک کن: در تابعِ perfect خطِ فرزندِ راست را به None تغییر بده و جدولِ بخشِ ۳ را دوباره بگیر. درختِ «کامل» باید دقیقاً به زنجیر تبدیل شود، و راهِ دیدنش ستونِ n است نه ستونِ نسبت: size به‌جای ۸٬۱۹۱ عددی مثلِ 13 می‌دهد، چون NODES از خودِ size ساخته می‌شود. ستونِ نسبت عوض نمی‌شود — و همین درسِ دوم است: وقتی نردبانِ n دیگر دوبرابری نیست، ستونِ نسبت هیچ چیزی دربارهٔ مرتبه نمی‌گوید. اگر size عوض نشد، جای دیگری را دست زده‌ای.

🤖 از دستیارت بپرس: «چرا ارتفاعِ یک درختِ کامل با log n می‌رود ولی تعدادِ گره‌هایش با n؟» بعد این را هم بپرس: «یک درختِ سه‌فرزندی چه ارتفاعی دارد و چقدر از دوفرزندی کمتر است؟» — جوابِ درست باید بگوید ارتفاع فقط بر حسبِ پایهٔ log عوض می‌شود و مرتبه همان O(log n) می‌ماند؛ اگر دستیارت گفت «خیلی بهتر می‌شود»، جدولِ بخشِ ۳ را با یک درختِ سه‌فرزندی بازسازی کن و جلویش بگذار.

واژه‌های تازهٔ این فصل#

در فصل بعد#

تا حالا فقط از ریشه به پایین راه رفتیم. فصلِ بعد چهار راهِ متفاوتِ دیدنِ همهٔ گره‌های یک درخت را می‌سازد. هر چهارتا دقیقاً 8,191 گره را می‌بینند، پس از نظرِ مرتبه فرقی ندارند. ولی حافظه‌ای که مصرف می‌کنند اصلاً یکی نیست: یکی روی همان درخت حداکثر 13 چیز را هم‌زمان نگه می‌دارد و دیگری 4,096 تا.

همان‌جا هم RecursionError این فصل را با یک stack صریح از میان برمی‌داریم.