# فصل ۰۳ — `binary search tree`: `log n`ی که می‌تواند `n` شود

<div dir="rtl">

# فصل ۰۳ — `binary search tree`: `log n`ی که می‌تواند `n` شود

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

یک قاعدهٔ ساده روی مقدارهای درخت می‌گذاریم — **کوچک‌تر به چپ، بزرگ‌تر به راست** — و همان `in-order` بی‌خاصیتِ فصلِ قبل، همه‌چیز را مرتب بیرون می‌دهد. جست‌وجو هم دیگر لازم نیست همهٔ گره‌ها را ببیند: در هر گره نصفِ درخت کنار می‌رود.

**بعد همان کلیدها را از پیش مرتب به همان کد می‌دهیم و ساختار فرو می‌ریزد.** ارتفاع از `26.4` به `3,999` می‌رود و میانگینِ مقایسه‌های جست‌وجو از `14.99` به `2,000.50` — بدونِ هیچ خطایی، با همان مجموعهٔ کلید.

![درختی که شاخه‌هایش دو طرف پخش شده در کنارِ درختی که همهٔ گره‌هایش فقط به یک سمت افتاده‌اند](/lesson-assets/t5-s03-bst/prompt/01-image-balanced-versus-skewed.png)

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

- یک `binary search tree` بسازی و درج و جست‌وجویش را بنویسی
- **ورودی‌ای بسازی که همین ساختار را به یک فهرستِ ساده تبدیل کند**
- بگویی چرا هزینهٔ جست‌وجو دقیقاً ارتفاع را دنبال می‌کند
- هزینهٔ **درج** را هم بسنجی و کنارِ `insort` روی یک فهرستِ مرتب بگذاری

## قبل از شروع

**از فصلِ ۱:** ارتفاع به‌عنوان هزینه. **از فصلِ ۲:** `in-order` و پیمایش با `stack` صریح. **از ترمِ ۳ فصلِ ۴:** ورودیِ خصمانه — همان ایده، این بار بدونِ هیچ مهاجمی.

</div>

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

<div dir="rtl">

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

## ۱. قاعده، و چیزی که از آن درمی‌آید

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

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

</div>

```python
KEY, LEFT, RIGHT = 0, 1, 2


def bst_insert(root, key):
    """کلید را در جای درستش می‌گذارد: کوچک‌تر به چپ، بزرگ‌تر به راست."""
    if root is None:
        return [key, None, None]
    node = root
    while True:
        if key < node[KEY]:
            if node[LEFT] is None:
                node[LEFT] = [key, None, None]
                return root
            node = node[LEFT]
        elif key > node[KEY]:
            if node[RIGHT] is None:
                node[RIGHT] = [key, None, None]
                return root
            node = node[RIGHT]
        else:
            return root                      # کلیدِ تکراری: هیچ کاری لازم نیست


def bst_search(root, key):
    """(پیدا شد یا نه، تعدادِ گره‌هایی که با آن‌ها مقایسه شد)"""
    node = root
    steps = 0
    while node is not None:
        steps += 1
        if key == node[KEY]:
            return True, steps
        node = node[LEFT] if key < node[KEY] else node[RIGHT]
    return False, steps


def build_bst(keys):
    root = None
    for k in keys:
        root = bst_insert(root, k)
    return root


def in_order(root):
    """پیمایشِ in-orderِ فصلِ قبل، این بار با stack صریح."""
    out = []
    pending = []
    node = root
    while pending or node is not None:
        while node is not None:
            pending.append(node)
            node = node[LEFT]
        node = pending.pop()
        out.append(node[KEY])
        node = node[RIGHT]
    return out


demo = build_bst([50, 30, 70, 20, 40, 60, 80])
print("ساختار :", demo)
print("in-order:", in_order(demo))
print("۴۰ هست؟", bst_search(demo, 40), " · ۴۵ هست؟", bst_search(demo, 45))
```

```text
ساختار : [50, [30, [20, None, None], [40, None, None]], [70, [60, None, None], [80, None, None]]]
in-order: [20, 30, 40, 50, 60, 70, 80]
۴۰ هست؟ (True, 3)  · ۴۵ هست؟ (False, 3)
```

<div dir="rtl">

**دو چیز در این خروجی هست.** اول: `in-order` مرتب درآمد و هیچ کدِ اضافه‌ای نخواست — **همان تابعِ فصلِ قبل، عیناً.** قاعدهٔ درج، ترتیب را در خودِ ساختار ذخیره کرده.

دوم: هر دو جست‌وجو سه مقایسه خوردند، حتی آن‌که کلیدش وجود ندارد. **جوابِ «نه» هم به‌اندازهٔ جوابِ «بله» ارزان است**، چون هر دو تا یک برگ پایین می‌روند.

## ۲. ارتفاع، وقتی کلیدها بی‌ترتیب می‌آیند و وقتی نمی‌آیند

حالا همان مجموعهٔ کلید را به دو ترتیبِ متفاوت به `build_bst` می‌دهیم: یک بار به‌هم‌ریخته، یک بار از پیش مرتب.

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

</div>

```python
def bst_height(root):
    """ارتفاع، با stack صریح — تا درختِ منحرف هم recursion را نشکند."""
    best = -1
    pending = [(root, 0)]
    while pending:
        node, depth = pending.pop()
        if node is None:
            best = max(best, depth - 1)
            continue
        pending.append((node[LEFT], depth + 1))
        pending.append((node[RIGHT], depth + 1))
    return best


LADDER = [500, 1_000, 2_000, 4_000]
TRIES = 5
rng = random.Random(SEED)
shuffled = {}
for n in LADDER:
    orders = []
    for _ in range(TRIES):
        keys = list(range(n))
        rng.shuffle(keys)
        orders.append(keys)
    shuffled[n] = orders

print("سه کلیدِ اولِ اولین ترتیبِ به‌هم‌ریخته:", shuffled[500][0][:3])
print("سه کلیدِ اولِ ورودیِ مرتب            :", list(range(500))[:3])
print("هر دو همان مجموعه‌اند؟", sorted(shuffled[500][0]) == list(range(500)))
```

```text
سه کلیدِ اولِ اولین ترتیبِ به‌هم‌ریخته: [332, 313, 92]
سه کلیدِ اولِ ورودیِ مرتب            : [0, 1, 2]
هر دو همان مجموعه‌اند؟ True
```

<div dir="rtl">

**اینجا یک قاعدهٔ چهارترمهٔ دوره عوض می‌شود و باید صریح گفته شود: از این جدول به بعد، میانگین می‌گیریم، نه کمینه.**

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

**پس قاعده عوض نشده؛ همان قاعده روی وضعیتِ متفاوتی اعمال شده.** و چون میانگین به‌تنهایی پراکندگی را پنهان می‌کند (ترمِ ۱ فصلِ ۳)، **کنارش کمینه تا بیشینه را هم چاپ می‌کنیم.**

</div>

```python
def height_stats(orders):
    """ارتفاعِ همان کلیدها با چند ترتیبِ متفاوت: میانگین، کمینه، بیشینه."""
    hs = [bst_height(build_bst(keys)) for keys in orders]
    return sum(hs) / len(hs), min(hs), max(hs)


print(f"— ورودیِ به‌هم‌ریخته ({TRIES} ترتیبِ متفاوت از همان کلیدها)")
print(f"{'n':>10}{'میانگینِ ارتفاع':>18}{'کمینه تا بیشینه':>20}{'نسبت به سطر قبل':>20}")
previous = None
for n in LADDER:
    avg, lo, hi = height_stats(shuffled[n])
    ratio = "—" if not previous else f"{avg / previous:.2f}"
    print(f"{n:>10,}{avg:>18.1f}{f'{lo} تا {hi}':>20}{ratio:>20}")
    previous = avg
print("\n— ورودیِ از پیش مرتب، همان کلیدها")
table([(n, bst_height(build_bst(range(n)))) for n in LADDER], "ارتفاع", ",d")
```

```text
— ورودیِ به‌هم‌ریخته (5 ترتیبِ متفاوت از همان کلیدها)
         n   میانگینِ ارتفاع     کمینه تا بیشینه     نسبت به سطر قبل
       500              18.6            17 تا 20                   —
     1,000              21.4            20 تا 25                1.15
     2,000              25.8            24 تا 29                1.21
     4,000              26.4            22 تا 32                1.02

— ورودیِ از پیش مرتب، همان کلیدها
         n            ارتفاع     نسبت به سطر قبل
       500               499                   —
     1,000               999                2.00
     2,000             1,999                2.00
     4,000             3,999                2.00
```

<div dir="rtl">

**ستونِ دوم `2.00` است و ستونِ اول حولِ `1.1` می‌لرزد.**

ستونِ مرتب هیچ ابهامی ندارد: ارتفاع **دقیقاً** `n - 1` است. کلیدها صعودی می‌آیند، پس هر کلیدِ تازه از همهٔ گره‌های موجود بزرگ‌تر است و همیشه به راست می‌رود. **نتیجه یک زنجیر است — همان زنجیرِ فصلِ ۱، این بار نه به‌عنوان یک مثالِ ساختگی بلکه به‌عنوانِ چیزی که از عادی‌ترین ورودیِ ممکن درآمد.**

ستونِ به‌هم‌ریخته لرزان است و **ستونِ «کمینه تا بیشینه» می‌گوید چقدر**: در `n = 4,000` پنج ترتیب ارتفاع‌های `22` تا `32` دادند — **بازه‌ای ده‌واحدی، در حالی که خودِ میانگین از سطرِ قبل فقط ۰٫۶ واحد بالاتر رفته.** برای همین نسبتِ سطرِ آخر `1.02` درآمد و نه `1.1`: **آن `1.02` یک نتیجه نیست، یک تصادف است** — و بدونِ ستونِ پراکندگی به‌عنوان نتیجه خوانده می‌شد.

**پس چرا `TRIES = 5`؟ صادقانه: چون ارزان است، نه چون کافی است.** پنج‌تا برای دیدنِ «حولِ `1.1`» کافی است و برای اعلامِ عددِ دقیق نیست. **تمرینِ ستاره‌دارِ آخرِ فصل می‌پرسد چند تا کافی است، و حالا ابزارِ جوابش را داری: `TRIES` را بالا ببر تا بازه دیگر با هر اجرا تکان نخورد.**

## ۳. هزینهٔ جست‌وجو دقیقاً ارتفاع را دنبال می‌کند

ارتفاع یک عددِ هندسی است. حالا ببینیم در جست‌وجو چه چیزی از آن درمی‌آید.

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

</div>

```python
def average_steps(root, keys):
    """میانگینِ تعدادِ مقایسه برای جست‌وجوی همهٔ کلیدها."""
    total = 0
    for k in keys:
        total += bst_search(root, k)[1]
    return total / len(keys)


print("— ورودیِ به‌هم‌ریخته: میانگینِ مقایسه در جست‌وجو")
table([(n, average_steps(build_bst(shuffled[n][0]), shuffled[n][0])) for n in LADDER],
      "میانگینِ مقایسه", ",.2f")
print("\n— ورودیِ از پیش مرتب")
table([(n, average_steps(build_bst(range(n)), range(n))) for n in LADDER],
      "میانگینِ مقایسه", ",.2f")
```

```text
— ورودیِ به‌هم‌ریخته: میانگینِ مقایسه در جست‌وجو
         n   میانگینِ مقایسه     نسبت به سطر قبل
       500             11.03                   —
     1,000             12.32                1.12
     2,000             13.46                1.09
     4,000             14.99                1.11

— ورودیِ از پیش مرتب
         n   میانگینِ مقایسه     نسبت به سطر قبل
       500            250.50                   —
     1,000            500.50                2.00
     2,000          1,000.50                2.00
     4,000          2,000.50                2.00
```

<div dir="rtl">

**این جدول صاف‌تر از جدولِ ارتفاع است، و دلیلش ساده است: هر سطرش میانگینِ هزاران جست‌وجوست، نه یک عدد.** ستونِ چپ `1.12`، `1.09`، `1.11` — یعنی `O(log n)`. ستونِ راست `2.00` — یعنی `O(n)`.

و عددِ سطرِ آخرِ جدولِ مرتب را با ترمِ ۳ فصلِ ۱ بسنج: `2,000.50` برای چهار هزار کلید، یعنی دقیقاً همان `(n + 1) / 2` جست‌وجوی خطی. **درختِ منحرف نه فقط از `log n` افتاده، بلکه **دقیقاً** به همان چیزی رسیده که اگر کلیدها را در یک `list` ساده ریخته بودیم می‌داشتیم — با سربارِ ساخت و حافظهٔ اضافهٔ گره‌ها روی آن.

</div>

```python
n = 4_000
skewed = build_bst(range(n))
balanced = build_bst(shuffled[n][0])
print("همان کلیدها، همان ترتیبِ in-order؟", in_order(skewed) == in_order(balanced))
print(f"ارتفاعِ منحرف {bst_height(skewed):>5,}  ·  ارتفاعِ به‌هم‌ریخته {bst_height(balanced):>3}")
print(f"نسبتِ ارتفاع        : {bst_height(skewed) / bst_height(balanced):.1f} برابر")
print(f"نسبتِ میانگینِ مقایسه: "
      f"{average_steps(skewed, range(n)) / average_steps(balanced, shuffled[n][0]):.1f} برابر")
```

```text
همان کلیدها، همان ترتیبِ in-order؟ True
ارتفاعِ منحرف 3,999  ·  ارتفاعِ به‌هم‌ریخته  32
نسبتِ ارتفاع        : 125.0 برابر
نسبتِ میانگینِ مقایسه: 133.5 برابر
```

<div dir="rtl">

**سطرِ اول مهم‌ترین سطرِ فصل است: هر دو درخت همان ترتیبِ `in-order` را می‌دهند.** یعنی هر دو کاملاً درست‌اند و هر آزمونی که فقط جوابِ نهایی را چک کند، هر دو را قبول می‌کند. **تنها چیزی که فرق دارد هزینه است** — نسبتِ ارتفاع `125.0` و نسبتِ هزینه `133.5`؛ دو عددِ نزدیک، و این تصادفی نیست. (عددِ `32` ارتفاعِ **یک** درختِ به‌هم‌ریخته است، نه میانگینِ پنج‌تای بخشِ ۲ که `26.4` بود.)

**و این‌جا نکته‌ای هست که فراتر از این ساختار می‌رود:** ورودیِ مرتب یک ورودیِ عجیب نیست. داده‌ای که از یک فایلِ مرتب، از یک جدولِ پایگاه‌داده، یا از یک `sorted` قبلی می‌آید، **دقیقاً همین است**. بدترین حالتِ `BST` رایج‌ترین حالتِ داده‌های واقعی است.

## ۴. و درج؟ ترمِ ۴ یک وعده داد

آخرین فصلِ ترمِ ۴ وعده داد **ترمِ ۵ ساختاری می‌سازد که ترتیب را نگه می‌دارد و درجش هم ارزان است.** تا اینجا فقط جست‌وجو را سنجیدیم. **حالا خودِ درج** — روی همان کلیدها، در سه حالت: `BST` با ورودیِ به‌هم‌ریخته، `BST` با ورودیِ مرتب، و `insort` روی یک فهرستِ مرتب (نامزدی که ترمِ ۴ فصلِ ۷ ساخت).

> 🤔 **اول حدس بزن:** برای هر سه ستونِ نسبت را بنویس. **و یک حدسِ چهارم که از هر سه مهم‌تر است:** ورودیِ **مرتب** برای `insort` بدترین حالت است یا بهترین؟

</div>

```python
from bisect import bisect_left


def build_steps(keys):
    """گره‌هایی که در کلِ n درج دیده می‌شوند — همان مسیری که جست‌وجو هم می‌رود."""
    root = None
    steps = 0
    for k in keys:
        if root is None:
            root = [k, None, None]
            continue
        node = root
        while True:
            steps += 1
            if k < node[KEY]:
                if node[LEFT] is None:
                    node[LEFT] = [k, None, None]
                    break
                node = node[LEFT]
            else:
                if node[RIGHT] is None:
                    node[RIGHT] = [k, None, None]
                    break
                node = node[RIGHT]
    return steps


def insort_moves(keys):
    """عنصرهایی که نگه داشتنِ یک فهرستِ مرتب با insort جابه‌جا می‌کند."""
    out = []
    moved = 0
    for k in keys:
        i = bisect_left(out, k)
        moved += len(out) - i
        out.insert(i, k)
    return moved


print("— n درج در BST، ورودیِ به‌هم‌ریخته")
table([(n, build_steps(shuffled[n][0])) for n in LADDER], "گام", ",d")
print("\n— n درج در BST، ورودیِ از پیش مرتب")
table([(n, build_steps(range(n))) for n in LADDER], "گام", ",d")
print("\n— n درج با insort در فهرستِ مرتب، همان ورودیِ به‌هم‌ریخته")
table([(n, insort_moves(shuffled[n][0])) for n in LADDER], "جابه‌جایی", ",d")
print("\nهمان insort روی ورودیِ از پیش مرتب، n = 4,000:",
      f"{insort_moves(range(4_000)):,} جابه‌جایی")
```

```text
— n درج در BST، ورودیِ به‌هم‌ریخته
         n               گام     نسبت به سطر قبل
       500             5,015                   —
     1,000            11,317                2.26
     2,000            24,919                2.20
     4,000            55,943                2.24

— n درج در BST، ورودیِ از پیش مرتب
         n               گام     نسبت به سطر قبل
       500           124,750                   —
     1,000           499,500                4.00
     2,000         1,999,000                4.00
     4,000         7,998,000                4.00

— n درج با insort در فهرستِ مرتب، همان ورودیِ به‌هم‌ریخته
         n         جابه‌جایی     نسبت به سطر قبل
       500            67,808                   —
     1,000           254,425                3.75
     2,000         1,001,793                3.94
     4,000         3,946,664                3.94

همان insort روی ورودیِ از پیش مرتب، n = 4,000: 0 جابه‌جایی
```

<div dir="rtl">

**وعدهٔ ترمِ ۴ پرداخت شد، و با یک شرط که آنجا نوشته نشده بود.**

- **`BST` روی ورودیِ به‌هم‌ریخته: نسبت `2.24` — `O(n log n)` برای کلِ `n` درج**، یعنی `O(log n)` برای هر درج. **این همان «درجش هم ارزان است» است:** در `n = 4,000` جمعاً `55,943` گام، در برابرِ `3,946,664` جابه‌جاییِ `insort`.
- **`BST` روی ورودیِ از پیش مرتب: نسبت `4.00`** — و عددهایش سطر به سطر **دقیقاً** همان `n(n-1)/2`ِ ترمِ ۱ فصلِ ۴ هستند. **ساختنِ درخت از `n` کلیدِ مرتب `O(n²)` است.**
- **و سطرِ آخر ورق را برمی‌گرداند: `insort` روی همان ورودیِ مرتب صفر جابه‌جایی می‌کند**، چون هر کلیدِ تازه از همه بزرگ‌تر است و `bisect_left` ته فهرست را نشان می‌دهد.

**پس هیچ‌کدام از این دو ساختار «بهتر» نیست؛ ورودیِ بدشان با هم فرق دارد.** همان ورودی‌ای که `BST` را به `O(n²)` می‌برد، `insort` را به `O(n log n)` می‌رساند — فقط هزینهٔ `bisect`، بدونِ هیچ جابه‌جایی — **و برعکس.** ترمِ ۶ فصلِ ۲ کلِ جدولِ تصمیمش را روی همین می‌سازد.

## ۵. چیزی که وجود دارد: متوازن‌سازی

راهِ حل، تغییرِ قاعده نیست؛ **بازآراییِ ساختار بعد از هر درج است.** خانواده‌ای از درخت‌ها دقیقاً همین کار را می‌کنند — `AVL` و `red-black tree` دو تای معروفشان — و تضمین می‌کنند ارتفاع حولِ `log n` بماند، به‌قیمتِ کارِ اضافه در هر درج.

**این فصل هیچ‌کدام را پیاده نمی‌کند و این یک تصمیم است.** چیزی که برای تصمیمِ مهندسی لازم داری همین جدول‌های بالاست: **هزینه به ارتفاع بند است و ارتفاع به ترتیبِ ورودی.** بقیه‌اش جزئیاتِ پیاده‌سازی است.

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

> ⚠️ **مواظب باش:** جدولِ دومِ بخشِ ۴ نشان داد ساختنِ درخت از `n` کلیدِ مرتب `O(n²)` است — ستونِ نسبتِ `4.00`. **پس اگر `LADDER` را به `[4_000, 8_000, 16_000, 32_000]` ببری، همان جدول به بیش از پانصد میلیون گام می‌رسد و سلولت دقیقه‌ها طول می‌کشد.** **همین که ساختنِ ساختار خودش گران شده، یک هشدارِ مستقل است.**

> 🔧 **اگر کار نکرد:** `BST` روی کلیدهایش `<` می‌زند، پس کلیدها باید با هم **قابلِ مقایسه** باشند. این دقیقاً همان قیدی است که ترمِ ۳ فصلِ ۶ برای `dict` گذاشت، فقط با شرطِ متفاوت: آن‌جا `hashable` لازم بود، این‌جا ترتیب‌پذیری.

</div>

```python
try:
    mixed = build_bst([50, 30, 70])
    bst_insert(mixed, "sara")
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
TypeError: '<' not supported between instances of 'str' and 'int'
```

<div dir="rtl">

پیام دقیقاً می‌گوید چه اتفاقی افتاده و کجا. **و خوبیِ این خطا این است که فوری بلند می‌شود** — بر خلافِ ورودیِ مرتبِ بخشِ ۲ که هیچ چیزی نگفت و فقط کند شد.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** یک `BST` واحد با دو ترتیبِ ورودیِ متفاوت روی **همان مجموعهٔ کلید**، با `in-order` یکسانِ تأییدشده. **در کدام بازهٔ `n`؟** ۵۰۰ تا ۴٬۰۰۰ کلید. **با چند تکرار، و کمینه یا میانگین؟** جدولِ ارتفاع میانگینِ پنج ترتیبِ تصادفی، جدولِ مقایسه یک اجرا روی همهٔ کلیدها؛ هر دو شمارش‌اند و شمارش قطعی است. **هیچ عددِ ثانیه‌ای در این فصل نیست.**

> ✅ **چک کن:** به‌جای `range(n)` کلیدها را **نزولی** بده (`range(n - 1, -1, -1)`) و جدولِ بخشِ ۲ را دوباره بگیر. **ارتفاع باید دوباره دقیقاً `n - 1` شود** — این بار با زنجیری که همه‌اش به چپ افتاده. اگر عددت عوض شد، احتمالاً `bst_insert` را دست زده‌ای.

> 🤖 **از دستیارت بپرس:** **جدولِ بخشِ ۳ را جلویش بگذار و بپرس:** «هر دو درخت همان کلیدها را دارند و همان ترتیب را می‌دهند؛ پس چرا یکی صد و سی برابر گران‌تر است؟» — جوابِ درست باید ارتفاع را نام ببرد، نه تعدادِ گره‌ها. بعد این را هم بپرس: **«اگر کلیدهایم همیشه مرتب می‌آیند، `BST` انتخابِ درستی است؟»**

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| `binary search tree` | بایناری سِرچ تِری | درختی که در هر گره، چپ کوچک‌تر و راست بزرگ‌تر است |
| skewed tree | اسکیود تِری | درختِ منحرف: درختی که به یک زنجیر تبدیل شده |
| balancing | بالانسینگ | بازآراییِ درخت بعد از درج، تا ارتفاعش کوچک بماند |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا ورودیِ از پیش مرتب برای این ساختار بدترین حالت است؟

**تمرینِ اجباری:** تابعی بنویس که کوچک‌ترین کلیدِ یک `BST` را پیدا کند و تعدادِ گام‌هایش را هم برگرداند. **جدولِ چهار اندازه‌ای‌اش را برای هر دو ترتیبِ ورودی بگیر.** سؤالِ اصلی: **ستونِ نسبتِ هر کدام چه عددی می‌دهد؟**

**تمرینِ ستاره‌دار ⭐:** ورودی‌ای بساز که **نه مرتب باشد نه تصادفی**: نیمی از کلیدها مرتب و نیمِ دیگر به‌هم‌ریخته. **قبل از اجرا پیش‌بینی کن** ارتفاع به کدام‌یک از دو ستونِ بخشِ ۲ نزدیک‌تر می‌شود، و **مهم‌تر: پیش‌بینی کن ترتیبِ این دو نیمه (اول مرتب یا اول به‌هم‌ریخته) روی نتیجه اثر دارد یا نه.** حالا هر دو حالت را اندازه بگیر و خطای پیش‌بینی‌ات را بنویس.

## در فصل بعد

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

فصلِ بعد ساختاری می‌سازد که فقط همین یک کار را می‌کند و برایش هیچ درختی هم لازم ندارد: **یک `list` ساده که خودش درخت است.** آن‌جا می‌بینی که `n` درج در آن ستونِ نسبتِ `2.02` می‌دهد ولی `n` درج به‌علاوهٔ `n` برداشت ستونِ `2.19` — و همین تفاوتِ کوچک، کلِ حرفِ آن فصل است.

</div>

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