بنیاد — ساختمان داده و الگوریتم، با اندازه‌گیری واقعی

فصل ۳ از ۸

پیشرفت ترم
۰٪

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

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

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

درختی که شاخه‌هایش دو طرف پخش شده در کنارِ درختی که همهٔ گره‌هایش فقط به یک سمت افتاده‌اند

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

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

قبل از شروع#

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

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

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

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

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

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

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))
ساختار : [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)

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

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

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

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

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

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)))
سه کلیدِ اولِ اولین ترتیبِ به‌هم‌ریخته: [332, 313, 92]
سه کلیدِ اولِ ورودیِ مرتب            : [0, 1, 2]
هر دو همان مجموعه‌اند؟ True

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

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

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

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")
— ورودیِ به‌هم‌ریخته (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

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

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

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

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

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

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

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

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")
— ورودیِ به‌هم‌ریخته: میانگینِ مقایسه در جست‌وجو
         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

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

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

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} برابر")
همان کلیدها، همان ترتیبِ in-order؟ True
ارتفاعِ منحرف 3,999  ·  ارتفاعِ به‌هم‌ریخته  32
نسبتِ ارتفاع        : 125.0 برابر
نسبتِ میانگینِ مقایسه: 133.5 برابر

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

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

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

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

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

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)):,} جابه‌جایی")
— 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 جابه‌جایی

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

  • 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 لازم بود، این‌جا ترتیب‌پذیری.

try:
    mixed = build_bst([50, 30, 70])
    bst_insert(mixed, "sara")
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
TypeError: '<' not supported between instances of 'str' and 'int'

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

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

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

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

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

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

تمرین‌ها

اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.

در فصل بعد#

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

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

به آخر این فصل رسیدی!

اگر ساختی و جواب داد، این دکمه مال توست.