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

فصل ۲ از ۸

پیشرفت ترم
۰٪

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

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

چهار پیمایش می‌سازیم و روی درختِ ۸٬۱۹۱ گره‌ای امتحانشان می‌کنیم. هر چهارتا دقیقاً 8,191 گره را می‌بینند، پس از نظرِ مرتبه هیچ فرقی ندارند. ولی چیزی که هم‌زمان در حافظه نگه می‌دارند خیلی فرق دارد: یکی حداکثر 13 گره و دیگری 4,096 گره. آخرِ فصل هم RecursionError فصلِ قبل را با یک stack صریح از میان برمی‌داریم.

درختی که چهار مسیرِ رنگی متفاوت روی گره‌هایش کشیده شده و هر مسیر ترتیبِ دیگری دارد

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

  • pre-order، in-order، post-order و level-order را روی یک درختِ کوچک با دست بنویسی
  • یک پیمایش را با stack صریح، بدونِ recursion، پیاده کنی
  • هزینهٔ حافظهٔ پیمایشِ stackی و پیمایشِ queueای را از هم جدا کنی، با عدد
  • بگویی چرا دو کدِ تقریباً یکسان دو ترتیبِ متفاوت می‌دهند

قبل از شروع#

از فصلِ ۱: گره با سه خانه، درختِ کامل، زنجیر، و اینکه recursion روی زنجیر می‌شکند.

از ترمِ ۲ فصلِ ۷: stack و queue، و popleft در برابرِ pop(0). این فصل همان دو انضباط را روی یک درخت می‌گذارد و می‌بینی که فقط ترتیبِ بازدید عوض می‌شود.

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

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

۱. سه ترتیب، از یک الگوی واحد#

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

  • pre-order: اول خودِ گره
  • in-order: خودِ گره وسطِ دو زیردرخت
  • post-order: خودِ گره آخر از همه
VALUE, LEFT, RIGHT = 0, 1, 2


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 pre_order(node, out=None):
    """اول خودِ گره، بعد زیردرختِ چپ، بعد زیردرختِ راست."""
    if out is None:
        out = []
    if node is not None:
        out.append(node[VALUE])
        pre_order(node[LEFT], out)
        pre_order(node[RIGHT], out)
    return out


def in_order(node, out=None):
    """اول زیردرختِ چپ، بعد خودِ گره، بعد زیردرختِ راست."""
    if out is None:
        out = []
    if node is not None:
        in_order(node[LEFT], out)
        out.append(node[VALUE])
        in_order(node[RIGHT], out)
    return out


def post_order(node, out=None):
    """اول هر دو زیردرخت، آخر از همه خودِ گره."""
    if out is None:
        out = []
    if node is not None:
        post_order(node[LEFT], out)
        post_order(node[RIGHT], out)
        out.append(node[VALUE])
    return out


small = perfect(2)
print("درخت      :", small)
print("pre-order :", pre_order(small))
print("in-order  :", in_order(small))
print("post-order:", post_order(small))
درخت      : [1, [2, [4, None, None], [5, None, None]], [3, [6, None, None], [7, None, None]]]
pre-order : [1, 2, 4, 5, 3, 6, 7]
in-order  : [4, 2, 5, 1, 6, 3, 7]
post-order: [4, 5, 2, 6, 7, 3, 1]

سه سطرِ خروجی را با دست دنبال کن؛ همین یک بار کافی است تا دیگر هیچ‌وقت جایشان را عوض نکنی.

pre-order با ریشه شروع می‌شود، post-order با ریشه تمام می‌شود، و in-order ریشه را دقیقاً وسط می‌گذارد — سه گره قبلش، سه گره بعدش. هر سه ترتیب همان هفت عدد را دارند و فقط چیدمانشان فرق می‌کند.

کجا به‌دردت می‌خورد: post-order وقتی لازم است که تا زیردرخت‌ها تمام نشده‌اند نتوانی دربارهٔ گره تصمیم بگیری — دقیقاً مثلِ تابعِ height فصلِ قبل، که یک post-order بود بدونِ اینکه اسمش را برده باشیم. و in-order تا فصلِ بعد فقط یک ترتیبِ عجیب است؛ آن‌جا معلوم می‌شود چرا مهم‌ترینشان است.

۲. ترتیبِ چهارم: سطح به سطح#

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

from collections import deque


def level_order(node):
    """سطح به سطح: هر گره‌ای که بیرون می‌آید، فرزندانش ته صف می‌روند."""
    out = []
    if node is None:
        return out
    waiting = deque([node])
    while waiting:
        current = waiting.popleft()
        out.append(current[VALUE])
        if current[LEFT] is not None:
            waiting.append(current[LEFT])
        if current[RIGHT] is not None:
            waiting.append(current[RIGHT])
    return out


print("level-order:", level_order(small))
print("هر چهار ترتیب همان هفت گره را دارند؟",
      sorted(pre_order(small)) == sorted(in_order(small))
      == sorted(post_order(small)) == sorted(level_order(small)))
level-order: [1, 2, 3, 4, 5, 6, 7]
هر چهار ترتیب همان هفت گره را دارند؟ True

level-order روی این درخت دقیقاً 1 تا 7 را مرتب چاپ کرد — که اتفاقی نیست: تابعِ perfect به هر فرزند شمارهٔ 2 * value و 2 * value + 1 می‌دهد، و همین شماره‌گذاری یعنی سطح به سطح از چپ به راست. در فصلِ ۴ همین شماره‌گذاری تبدیل به کلِ ایدهٔ heap می‌شود.

۳. همان pre-order، بدونِ recursion#

recursion در واقع یک stack است که پایتون برایت نگه می‌دارد. اگر خودت آن stack را بسازی، همان کار را بدونِ سقفِ call stack انجام می‌دهی.

تنها نکته‌اش ترتیبِ گذاشتن است: stack آخرین چیز را اول برمی‌دارد، پس اگر می‌خواهی چپ زودتر بیرون بیاید، باید راست را اول بگذاری.

def pre_order_stack(node):
    """همان pre-order، با یک stack صریح به‌جای recursion."""
    out = []
    if node is None:
        return out
    pending = [node]
    while pending:
        current = pending.pop()
        out.append(current[VALUE])
        if current[RIGHT] is not None:
            pending.append(current[RIGHT])
        if current[LEFT] is not None:
            pending.append(current[LEFT])
    return out


print("با recursion:", pre_order(small))
print("با stack    :", pre_order_stack(small))
print("دو نسخه یک جواب می‌دهند؟", pre_order(small) == pre_order_stack(small))
با recursion: [1, 2, 4, 5, 3, 6, 7]
با stack    : [1, 2, 4, 5, 3, 6, 7]
دو نسخه یک جواب می‌دهند؟ True

سطرِ سوم اختیاری نیست. بازنویسیِ یک الگوریتم بدونِ مقایسهٔ خروجی، بازنویسی نیست؛ نوشتنِ کدِ دیگری است که ممکن است جوابِ دیگری بدهد. و این‌جا آن خطر کاملاً واقعی است:

def wrong_push_order(node):
    """همان کد، فقط چپ و راست جابه‌جا push شده‌اند."""
    out = []
    pending = [node]
    while pending:
        current = pending.pop()
        out.append(current[VALUE])
        if current[LEFT] is not None:
            pending.append(current[LEFT])
        if current[RIGHT] is not None:
            pending.append(current[RIGHT])
    return out


print("درست :", pre_order_stack(small))
print("معیوب:", wrong_push_order(small))
print("هر دو همهٔ گره‌ها را دیده‌اند؟",
      sorted(wrong_push_order(small)) == sorted(pre_order_stack(small)))
درست : [1, 2, 4, 5, 3, 6, 7]
معیوب: [1, 3, 7, 6, 2, 5, 4]
هر دو همهٔ گره‌ها را دیده‌اند؟ True

⚠️ مواظب باش: دو خطِ جابه‌جا، هیچ خطایی، و ترتیبِ کاملاً غلط. سطرِ آخر بدترین بخشِ ماجراست: هر دو نسخه هر هفت گره را دیده‌اند، پس هر آزمونی که فقط «همه را دیدی؟» بپرسد سبز می‌شود. تنها آزمونی که این را می‌گیرد، مقایسهٔ خودِ ترتیب است.

۴. هزینه: همه یک تعداد گره می‌بینند#

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

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

print("هر چهار پیمایش روی بزرگ‌ترین درخت یک تعداد گره می‌بینند؟",
      len(pre_order(forest[NODES[-1]])) == len(in_order(forest[NODES[-1]]))
      == len(post_order(forest[NODES[-1]])) == len(level_order(forest[NODES[-1]])))
table([(n, len(pre_order_stack(forest[n]))) for n in NODES], "گرهٔ بازدیدشده", ",d")
هر چهار پیمایش روی بزرگ‌ترین درخت یک تعداد گره می‌بینند؟ True
         n    گرهٔ بازدیدشده     نسبت به سطر قبل
     1,023             1,023                   —
     2,047             2,047                2.00
     4,095             4,095                2.00
     8,191             8,191                2.00

ستونِ نسبت دقیقاً 2.00 است: پیمایشِ کاملِ درخت O(n) است، برای هر چهار ترتیب. منطقش هم ساده است — هر گره دقیقاً یک بار دیده می‌شود، نه بیشتر و نه کمتر. پس اگر انتخابِ بینِ این چهارتا فقط بر اساسِ زمان بود، انتخاب معنایی نداشت.

۵. جایی که واقعاً فرق می‌کنند: حافظه#

سه پیمایشِ اولِ این فصل یک stack نگه می‌دارند و level-order یک queue. بزرگ‌ترین اندازه‌ای که هر کدام در طولِ کار به آن می‌رسند، هزینهٔ حافظهٔ آن پیمایش است.

🤔 اول حدس بزن: روی درختِ کاملِ ۸٬۱۹۱ گره‌ای، stack حداکثر چند گره را هم‌زمان نگه می‌دارد و queue چند تا؟ هر دو عدد را بنویس — این حدس‌زدنی‌ترین جدولِ فصل است.

def peak_stack(node):
    """بیشترین چیزی که pre-orderِ stackی هم‌زمان نگه می‌دارد."""
    peak = 0
    pending = [node]
    while pending:
        peak = max(peak, len(pending))
        current = pending.pop()
        if current[RIGHT] is not None:
            pending.append(current[RIGHT])
        if current[LEFT] is not None:
            pending.append(current[LEFT])
    return peak


def peak_queue(node):
    """بیشترین چیزی که level-order هم‌زمان نگه می‌دارد."""
    peak = 0
    waiting = deque([node])
    while waiting:
        peak = max(peak, len(waiting))
        current = waiting.popleft()
        if current[LEFT] is not None:
            waiting.append(current[LEFT])
        if current[RIGHT] is not None:
            waiting.append(current[RIGHT])
    return peak


print("— pre-order با stack: بیشینهٔ اندازهٔ stack")
table([(n, peak_stack(forest[n])) for n in NODES], "بیشینهٔ stack", ",d")
print("\n— level-order: بیشینهٔ اندازهٔ queue")
table([(n, peak_queue(forest[n])) for n in NODES], "بیشینهٔ queue", ",d")
— pre-order با stack: بیشینهٔ اندازهٔ stack
         n     بیشینهٔ stack     نسبت به سطر قبل
     1,023                10                   —
     2,047                11                1.10
     4,095                12                1.09
     8,191                13                1.08

— level-order: بیشینهٔ اندازهٔ queue
         n     بیشینهٔ queue     نسبت به سطر قبل
     1,023               512                   —
     2,047             1,024                2.00
     4,095             2,048                2.00
     8,191             4,096                2.00

13 در برابرِ 4,096. همان درخت، همان تعدادِ بازدید، و سیصد و پانزده برابر تفاوت در حافظه.

دلیلش را از فصلِ ۱ می‌شناسی: stack به‌اندازهٔ ارتفاعِ درخت بزرگ می‌شود و queue به‌اندازهٔ عرضِ آن. در درختِ کامل ارتفاع log n است و عریض‌ترین سطح نصفِ کلِ گره‌ها را دارد — و ستونِ نسبت دقیقاً همین را می‌گوید: 1.08 در برابرِ 2.00.

قاعده‌ای که از این درمی‌آید و در فصل‌های گراف بارها به‌کارت می‌آید: پیمایشِ stackی ارزانِ حافظه است و پیمایشِ queueای گران. روی درختِ باریک و بلند دقیقاً برعکس می‌شود، و بخشِ ۶ همان را نشان می‌دهد.

۶. و همان زنجیرِ فصلِ قبل#

line = chain(2_000)
try:
    pre_order(line)
except RecursionError as err:
    print(f"با recursion → {type(err).__name__}: {err}")
print("با stack     →", len(pre_order_stack(line)), "گره، بدونِ هیچ خطایی")
print("بیشینهٔ stack روی همین زنجیر:", peak_stack(line))
با recursion → RecursionError: maximum recursion depth exceeded
با stack     → 2000 گره، بدونِ هیچ خطایی
بیشینهٔ stack روی همین زنجیر: 1

بدهیِ فصلِ قبل پرداخت شد. نسخه‌ای که recursion دارد روی زنجیرِ ۲٬۰۰۰ گره‌ای می‌شکند و نسخهٔ stackی همان کار را بدونِ خطا انجام می‌دهد.

و سطرِ آخر شگفت‌انگیزترین عددِ فصل است: stack روی این زنجیر هیچ‌وقت از یک عضو بیشتر نشد. چون هر گره فقط یک فرزند دارد، هیچ چیزی برای «بعداً» کنار گذاشته نمی‌شود. همان ساختاری که recursion را می‌شکند، برای stack صریح ارزان‌ترین حالتِ ممکن است — و کلِ تفاوت این است که پایتون در call stack علاوه بر گره، کلِ وضعیتِ فراخوانی را هم نگه می‌دارد.

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

✅ چک کن: در peak_queue به‌جای popleft بنویس pop و جدولِ بخشِ ۵ را دوباره بگیر. بیشینهٔ queue باید از 4,096 به عددی حولِ 13 سقوط کند — چون با pop دیگر صف نیست و همان stack است. و همین آزمایش می‌گوید تفاوتِ حافظه از خودِ ظرف نمی‌آید، از انضباطی می‌آید که رویش گذاشته‌ای.

🔧 اگر کار نکرد: پرتکرارترین اشتباه در نوشتنِ پیمایشِ stackی این است که شرطِ خالی‌بودن را جا بیندازی و با while True جلو بروی:

try:
    pending = [small]
    while True:
        current = pending.pop()
        if current[RIGHT] is not None:
            pending.append(current[RIGHT])
        if current[LEFT] is not None:
            pending.append(current[LEFT])
except IndexError as err:
    print(f"{type(err).__name__}: {err}")
IndexError: pop from empty list

پیام صریح است و دقیقاً همان چیزی را می‌گوید که اتفاق افتاده: درخت تمام شد، stack خالی شد، و کد هنوز دنبالِ گرهٔ بعدی بود. خوبیِ این خطا این است که فوری بلند می‌شود — بر خلافِ تلهٔ بخشِ ۳ که یک ترتیبِ غلط را بی‌سروصدا برگرداند.

🤖 از دستیارت بپرس: «چرا level-order روی یک درختِ کامل حافظهٔ خیلی بیشتری از pre-order می‌خواهد؟» بعد جدولِ بخشِ ۵ را جلویش بگذار و بپرس: «روی چه شکلی از درخت این نتیجه برعکس می‌شود؟» — جوابِ درست باید درختِ باریک و بلند را نام ببرد و بگوید آن‌جا queue هیچ‌وقت بزرگ نمی‌شود.

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

کلمه تلفظ به حروف فارسی یعنی چه
traversal تراوِرسال پیمایش: دیدنِ همهٔ گره‌های یک ساختار، هر کدام یک بار
pre-order پری‌اُردر خودِ گره قبل از هر دو زیردرخت
in-order این‌اُردر خودِ گره بینِ دو زیردرخت
post-order پُست‌اُردر خودِ گره بعد از هر دو زیردرخت
level-order لِوِل‌اُردر سطح به سطح، با یک queue

تمرین‌ها

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

در فصل بعد#

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

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

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

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