AlgoVerse

کپی و برابری دو درخت

دو الگوریتم بازگشتی کوتاه: کپی یک درخت دودویی گره به گره، و بررسی اینکه دو درخت هم شکل و هم کلیدهایشان یکی است؛ هر دو O(n).

یک درخت دودویی را با پیمایش پیش‌ترتیب کپی می‌کنیم: گره‌ی تازه با همان کلید بساز، بعد زیردرخت چپ و راست را به صورت بازگشتی کپی کن و به آن وصل کن. هر گره یک بار کپی می‌شود: O(n).

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

A و B همان کلیدها با دو ترتیب درج‌اند که به یک درخت می‌رسند؛ a کپی می‌شود و a و b برابرند.

  1. class Node:
  2. def __init__(self, key):
  3. self.key = key
  4. self.left = None
  5. self.right = None
  8. def copy_and_compare(A, B):
  9. a = build(A[0])
  10. b = build(B[0])
  11. c = copy(a)
  12. same = equal(a, b)
  13. return same
  16. def copy(node):
  17. if node is None:
  18. return None
  19. t = Node(node.key)
  20. t.left = copy(node.left)
  21. t.right = copy(node.right)
  22. return t
  25. def equal(x, y):
  26. if x is None and y is None:
  27. return True
  28. if x is None or y is None:
  29. return False
  30. if x.key != y.key:
  31. return False
  32. match = x.key
  33. return equal(x.left, y.left) and equal(x.right, y.right)
  36. def build(keys):
  37. # A binary search tree from the keys in this insertion order.
  38. root = None
  39. for k in keys:
  40. node = Node(k)
  41. if root is None:
  42. root = node
  43. continue
  44. p = root
  45. while True:
  46. if k < p.key:
  47. if p.left is None:
  48. p.left = node
  49. break
  50. p = p.left
  51. else:
  52. if p.right is None:
  53. p.right = node
  54. break
  55. p = p.right
  56. return root

ناوردا: EQUAL(x, y) درست است اگر و تنها اگر زیردرخت‌های x و y هم شکل و هم کلیدها یکسان داشته باشند.

شروع اجرا

a

∅

b

∅

c

∅

same—

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

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

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

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

A list

[8, 4, 12, 2, 6, 10]

B list

[8, 12, 4, 10, 6, 2]

Call stack

  1. copy_and_compare()خط 8
گام ۱ از ۳۲۴
خط سیاه = copy_node, same_key · خط نارنجی = گام کلیدیbuilt: 0/1 · copy_node: 0/6 · copied: 0/1 · same_key: 0/6 · compared: 0/1
    توضیح

    کپی

    یک درخت دودویی را با پیمایش پیش‌ترتیب کپی می‌کنیم: گره‌ی تازه با همان کلید بساز، بعد زیردرخت چپ و راست را به صورت بازگشتی کپی کن و به آن وصل کن. هر گره یک بار کپی می‌شود: O(n).

    برابری

    دو درخت برابرند اگر هر دو تهی باشند، یا ریشه‌هایشان کلید یکسان داشته باشند و زیردرخت‌های چپ و راستشان هم (به صورت بازگشتی) برابر باشند. به محض اولین تفاوت (در شکل یا کلید) جواب «نه» است.

    نکته

    یک مجموعه کلید با ترتیب‌های درج متفاوت می‌تواند به درخت جستجوی دودویی یکسان یا متفاوت برسد؛ پیش‌تنظیم‌ها هر دو حالت را نشان می‌دهند.

    ورودی

    A و B ترتیب درج کلیدها در دو درخت جستجوی دودویی a و b اند.