AlgoVerse

شکافتن و پیوند درخت جستجوی دودویی

درخت جستجو را با کلید k به دو درخت (کوچک‌تر و بزرگ‌تر از k) می‌شکافد و بعد دو درخت را دوباره پیوند می‌دهد؛ هر دو O(h). شکافتن و سپس پیوند همان حذف k است.

SPLIT(t, k) درخت جستجو را به سه بخش تقسیم می‌کند: درخت small با کلیدهای کمتر از k، گره‌ی k (اگر باشد)، و درخت big با کلیدهای بیشتر از k. فقط در مسیر جست‌وجوی k پایین می‌رویم:

ادامه‌ی توضیح ↓
ورودی:
A 1×10 · k=40خروجی PDF

درخت ۱۰ کلیدی با k = ۴۰؛ مسیر جست‌وجوی ۴۰ درخت را به دو نیم می‌کند، و بعد بزرگ‌ترین کلید small، یعنی ۳۵، ریشه‌ی درخت پیوندخورده می‌شود.

  1. class Node:
  2. def __init__(self, key):
  3. self.key = key
  4. self.left = None
  5. self.right = None
  8. def split_join(A, k):
  9. root = build(A[0])
  10. small, mid, big = split(root, k)
  11. found = mid is not None
  12. root = None
  13. root = join(small, big)
  14. small = None
  15. big = None
  16. keys = []
  17. inorder(root, keys)
  18. return keys
  21. def split(t, k):
  22. # Returns the keys < k, the node with key k (or None), and the keys > k, as three search trees.
  23. if t is None:
  24. return None, None, None
  25. if k < t.key:
  26. s, m, b = split(t.left, k)
  27. t.left = b
  28. return s, m, t
  29. if k > t.key:
  30. s, m, b = split(t.right, k)
  31. t.right = s
  32. return t, m, b
  33. s, b = t.left, t.right
  34. t.left = None
  35. t.right = None
  36. return s, t, b
  39. def join(small, big):
  40. # Every key in small is below every key in big. The largest key of small becomes the new root.
  41. if small is None:
  42. return big
  43. parent = None
  44. m = small
  45. while m.right is not None:
  46. parent = m
  47. m = m.right
  48. if parent is None:
  49. small = m.left
  50. else:
  51. parent.right = m.left
  52. m.left = small
  53. m.right = big
  54. return m
  57. def inorder(t, keys):
  58. if t is not None:
  59. inorder(t.left, keys)
  60. keys.append(t.key)
  61. inorder(t.right, keys)
  64. def build(keys):
  65. root = None
  66. for key in keys:
  67. node = Node(key)
  68. if root is None:
  69. root = node
  70. continue
  71. p = root
  72. while True:
  73. if key < p.key:
  74. if p.left is None:
  75. p.left = node
  76. break
  77. p = p.left
  78. else:
  79. if p.right is None:
  80. p.right = node
  81. break
  82. p = p.right
  83. return root

ناوردا: در شکافتن، هر گره‌ی مسیر جست‌وجوی k با یکی از زیردرخت‌هایش دست‌نخورده به small یا big می‌رود؛ همه‌ی کلیدهای small کمتر از k و همه‌ی کلیدهای big بیشتر از k اند.

شروع اجرا

root

∅

small

∅

big

∅

درخت فراخوانی‌های بازگشتی

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

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

k40

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

A list

[50, 30, 70, 20, 40, 60, 80, 35, 45, 65]

Call stack

  1. split_join()خط 8
گام ۱ از ۲۸۰
خط سیاه = split_done, joined · خط نارنجی = گام کلیدیbuilt: 0/1 · found: 0/1 · keep_left: 0/1 · keep_right: 0/1 · split_done: 0/1 · find_max: 0/1 · unlink_max: 0/1 · new_root: 0/1 · joined: 0/1
    توضیح

    شکافتن

    SPLIT(t, k) درخت جستجو را به سه بخش تقسیم می‌کند: درخت small با کلیدهای کمتر از k، گره‌ی k (اگر باشد)، و درخت big با کلیدهای بیشتر از k. فقط در مسیر جست‌وجوی k پایین می‌رویم:

    • اگر k < t.key: گره‌ی t با زیردرخت راستش به big می‌رود و شکافتن در زیردرخت چپ ادامه دارد.
    • اگر k > t.key: برعکس، t با زیردرخت چپش به small می‌رود.

    پیوند

    JOIN(small, big) دو درخت را که همه‌ی کلیدهای اولی از دومی کوچک‌ترند یکی می‌کند: بزرگ‌ترین گره‌ی small را جدا می‌کنیم و ریشه‌ی تازه می‌کنیم، با small در چپ و big در راست. اگر یک کلید میانی m هم داشته باشیم (پیوند سه‌طرفه) کار ساده‌تر است: m ریشه می‌شود.

    هزینه

    هر دو فقط یک مسیر از ریشه تا برگ را می‌روند: O(h). این دو عمل پایه‌ی درخت‌های treap و splay و پیاده‌سازی مجموعه‌ها با اجتماع و اشتراک‌اند.

    ورودی

    A ترتیب درج کلیدها و k کلید شکافتن است.