شمارش درخت‌های دودویی (بازگشتی)
تعداد درخت‌های دودویی با n گره را مستقیم از تعریف بازگشتی می‌شمارد؛ درخت فراخوانی نشان می‌دهد چرا نسخه‌ی پویا (عددهای کاتالان) بهتر است.
درخت دودویی با n گره را با ریشه‌اش و زیردرخت‌هایش توصیف می‌کنیم. اگر i گره در زیردرخت چپ باشد، n − 1 − i گره در راست است و هر زوجی از دو زیردرخت یک درخت تازه می‌سازد:
- زمان:
O(3ⁿ) - حافظه:
O(n) - هوروویتز–ساهنی، فصل ۵
- گریمالدی، فصل ۱۰
۳ گره: ۵ درخت (۲ + ۱ + ۲، بسته به اینکه چند گره زیر ریشه در سمت چپ است).
def count_trees(n):# The number of binary trees with n nodes: the root, then i nodes on the left and n − 1 − i on the right.if n <= 1:return 1total = 0for left in range(n):right = n - 1 - lefttotal = total + count_trees(left) * count_trees(right)return total
شروع اجرا
درخت فراخوانی‌های بازگشتی
نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده
متغیرهای محلی
نارنجی = در همین گام عوض شد
Call stack
- count_trees()خط 1
توضیح
ایده
درخت دودویی با n گره را با ریشه‌اش و زیردرخت‌هایش توصیف می‌کنیم. اگر i گره در زیردرخت چپ باشد، n − 1 − i گره در راست است و هر زوجی از دو زیردرخت یک درخت تازه می‌سازد:
T(n) = Σ T(i) · T(n − 1 − i) برای i = 0 … n − 1، T(0) = T(1) = 1
جواب‌ها همان عددهای کاتالان هستند: ۱، ۱، ۲، ۵، ۱۴، ۴۲، …
چرا کند است؟
هر فراخوانی چند زیرمسئله‌ی کوچک‌تر را صدا می‌زند و همان زیرمسئله‌ها بارها از نو حساب می‌شوند؛ تعداد فراخوانی‌ها نمایی است. نسخه‌ی برنامه‌ریزی پویا (صفحه‌ی «عددهای کاتالان») هر T(k) را یک بار حساب می‌کند: O(n²).
در trace به چه چیزی نگاه کنی
- درخت فراخوانی‌ها را ببین: گره‌هایی با همان
nبارها تکرار می‌شوند.