AlgoVerse

درخت جستجوی دودویی بهینه

با برنامه‌ریزی پویا درخت جستجویی می‌سازد که با دانستن بسامد جست‌وجوی هر کلید، کمترین هزینه‌ی مورد انتظار را دارد؛ برای هر بازه‌ی کلیدها، بهترین ریشه را امتحان می‌کند. O(n³).

کلیدهای k1 < … < kn را داریم و می‌دانیم هر کلید ki با بسامد pi جست‌وجو می‌شود، و جست‌وجوهای ناموفقی که بین ki و ki+1 می‌افتند بسامد qi دارند. هزینه‌ی هر جست‌وجو تعداد گره‌هایی است که می‌بینیم. درخت جستجویی می‌خواهیم که هزینه‌ی مورد انتظار کمینه باشد. درخت متوازن لزوماً بهینه نیست: کلید پرطرفدار باید نزدیک ریشه باشد.

ادامه‌ی توضیح ↓
ورودی:
P 1×5 · Q 1×6خروجی PDF

پنج کلید با p = ۱۵، ۱۰، ۵، ۱۰، ۲۰ و q = ۵، ۱۰، ۵، ۵، ۵، ۱۰ (صدم)؛ هزینه‌ی بهینه ۲۷۵، یعنی ۲٫۷۵، با k2 در ریشه.

  1. class Node:
  2. def __init__(self, key):
  3. self.key = key
  4. self.left = None
  5. self.right = None
  8. def optimal_bst(P, Q):
  9. # p[1..n]: how often each key k1..kn is searched; q[0..n]: how often a search falls between keys (in hundredths).
  10. p = [0] + P[0]
  11. q = Q[0]
  12. n = len(P[0])
  13. if len(q) != n + 1:
  14. return None
  15. # e[i][j]: the cheapest expected cost of a tree on keys ki..kj; rt[i][j]: its root. Row 0 is unused, as in CLRS.
  16. e = [["·"] * (n + 1) for _ in range(n + 2)]
  17. w = [[0] * (n + 1) for _ in range(n + 2)]
  18. rt = [["·"] * (n + 1) for _ in range(n + 2)]
  19. for i in range(1, n + 2):
  20. e[i][i - 1] = q[i - 1]
  21. w[i][i - 1] = q[i - 1]
  22. for length in range(1, n + 1):
  23. for i in range(1, n - length + 2):
  24. j = i + length - 1
  25. w[i][j] = w[i][j - 1] + p[j] + q[j]
  26. best = None
  27. for r in range(i, j + 1):
  28. t = e[i][r - 1] + e[r + 1][j] + w[i][j]
  29. if best is None or t < best:
  30. best = t
  31. e[i][j] = t
  32. rt[i][j] = r
  33. cost = e[1][n]
  34. # Rebuild the tree from rt, with a stack of (node, i, j) ranges.
  35. tree = Node("k" + str(rt[1][n]))
  36. stack = [[tree, 1, n, rt[1][n]]]
  37. while stack:
  38. node, i, j, r = stack.pop()
  39. if i <= r - 1:
  40. node.left = Node("k" + str(rt[i][r - 1]))
  41. stack.append([node.left, i, r - 1, rt[i][r - 1]])
  42. if r + 1 <= j:
  43. node.right = Node("k" + str(rt[r + 1][j]))
  44. stack.append([node.right, r + 1, j, rt[r + 1][j]])
  45. return cost

ناوردا: وقتی بازه‌های طول ℓ پر می‌شوند، همه‌ی بازه‌های کوتاه‌تر از قبل هزینه‌ی بهینه‌شان را دارند.

شروع اجرا

∅

cost—

e

جدول هنوز خالی است.

rt

جدول هنوز خالی است.

متغیرهای محلی

نارنجی = در همین گام عوض شد

P list

[15, 10, 5, 10, 20]

Q list

[5, 10, 5, 5, 5, 10]

Call stack

  1. optimal_bst()خط 8
گام ۱ از ۳۴۳
خط سیاه = weight · خط نارنجی = گام کلیدیweight: 0/15 · try_root: 0/35 · better: 0/24 · tree_built: 0/1
    توضیح

    مسئله

    کلیدهای k1 < … < kn را داریم و می‌دانیم هر کلید ki با بسامد pi جست‌وجو می‌شود، و جست‌وجوهای ناموفقی که بین ki و ki+1 می‌افتند بسامد qi دارند. هزینه‌ی هر جست‌وجو تعداد گره‌هایی است که می‌بینیم. درخت جستجویی می‌خواهیم که هزینه‌ی مورد انتظار کمینه باشد. درخت متوازن لزوماً بهینه نیست: کلید پرطرفدار باید نزدیک ریشه باشد.

    زیرساختار بهینه

    اگر kr ریشه‌ی درخت بهینه برای ki..kj باشد، زیردرخت چپ و راست هم برای ki..kr−1 و kr+1..kj بهینه‌اند. وقتی زیردرختی زیر ریشه می‌رود، هر کلیدش یک سطح پایین‌تر می‌رود، یعنی w(i, j) (جمع بسامدها) به هزینه اضافه می‌شود:

    e[i][j] = min over r of  e[i][r−1] + e[r+1][j] + w[i][j]

    هزینه

    Θ(n²) بازه و برای هر کدام تا n ریشه: Θ(n³). Knuth نشان داد ریشه‌ی بهینه بین rt[i][j−1] و rt[i+1][j] است و این زمان را به O(n²) می‌رساند.

    ورودی

    P بسامد کلیدها و Q بسامد جست‌وجوهای ناموفق (n + 1 عدد) است، به صدم. جدول e هزینه‌ها و rt ریشه‌ها را با اندیس‌های CLRS نشان می‌دهد (سطر ۰ استفاده نمی‌شود).