در این فصل چه یاد میگیری#
یک قاعدهٔ ساده روی مقدارهای درخت میگذاریم — کوچکتر به چپ، بزرگتر به راست — و همان 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 — و همین تفاوتِ کوچک، کلِ حرفِ آن فصل است.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.