# فصل ۰۱ — درخت: وقتی رابطه سلسله‌مراتبی است

<div dir="rtl">

# فصل ۰۱ — درخت: وقتی رابطه سلسله‌مراتبی است

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

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

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

![درختی با شاخه‌های متوازن در کنارِ زنجیری از همان تعداد گره که فقط رو به پایین رفته است](/lesson-assets/t5-s01-tree/prompt/01-image-tree-versus-chain.png)

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

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

## قبل از شروع

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

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

</div>

| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیش‌فرضِ Colab) | کمتر از یک دقیقه |

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-5-trees-and-graphs/session-01-tree.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

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

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

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

</div>

```python
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])
```

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

<div dir="rtl">

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

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

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

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

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

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

</div>

```python
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]))
```

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

<div dir="rtl">

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

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

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

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

</div>

```python
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)}")
```

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

<div dir="rtl">

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

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

</div>

```python
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")
```

```text
— درختِ کامل
         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
```

<div dir="rtl">

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

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

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

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

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

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

</div>

```python
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")
```

```text
— درختِ کامل: گره‌هایی که تا رسیدن به عمیق‌ترین برگ دیده می‌شوند
         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
```

<div dir="rtl">

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

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

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

</div>

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

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

<div dir="rtl">

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

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

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

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

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

</div>

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

```text
RecursionError: maximum recursion depth exceeded
```

<div dir="rtl">

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

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

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

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

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| node | نُود | یک عضوِ درخت: مقدار به‌علاوهٔ ارجاعِ فرزندان |
| root | روت | ریشه: گره‌ای که هیچ‌کس به آن ارجاع نمی‌دهد |
| leaf | لیف | برگ: گره‌ای که هیچ فرزندی ندارد |
| depth | دپث | عمق: فاصلهٔ یک گره تا ریشه |
| height | هایت | ارتفاع: بلندترین مسیر از ریشه تا یک برگ |
| `binary tree` | بایناری تِری | درختی که هر گره‌اش حداکثر دو فرزند دارد |

<div dir="rtl">

## تمرین‌ها

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

**تمرینِ اجباری:** تابعی بنویس که تعدادِ برگ‌های یک درخت را برگرداند. حالا **جدولِ چهار اندازه‌ای‌اش را برای درختِ کامل بگیر** و ستونِ نسبت را بخوان. **سؤالِ اصلی: نسبتِ برگ‌ها چه عددی می‌دهد و چرا با نسبتِ ارتفاع فرق دارد؟** جوابت باید بگوید تعدادِ برگ‌ها چه کسری از کلِ گره‌هاست — و آن کسر خودش یک درسِ کوچک دربارهٔ درختِ کامل است.

**تمرینِ ستاره‌دار ⭐:** درختی بساز که نه کامل باشد نه زنجیر: با احتمالِ نصف-نصف برای هر گره تصمیم بگیر فرزند بسازد یا نه (از `random.Random(SEED)` استفاده کن تا نتیجه تکرارپذیر بماند). **قبل از اجرا پیش‌بینی کن** ستونِ نسبتِ ارتفاعش به کدام‌یک از دو جدولِ بخشِ ۳ نزدیک‌تر است. حالا برای چهار اندازه اندازه بگیر و خطای پیش‌بینی‌ات را بنویس. **و در آخر: آیا عددت بینِ دو اجرا با دو `SEED` متفاوت ثابت می‌ماند؟** اگر نه، یک بار اندازه‌گیری کافی نیست و باید بگویی چند بار.

## در فصل بعد

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

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

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t5/s01-tree (یادستان, Yaadestan)
