AlgoVerse

یکریختی درخت‌ها

بررسی می‌کند آیا دو درخت ریشه‌دار با جابه‌جا کردن فرزندان به هم تبدیل می‌شوند: به هر زیردرخت از پایین به بالا یک نام متعارف می‌دهد و نام دو ریشه را مقایسه می‌کند.

دو درخت ریشه‌دار یکریخت‌اند اگر بشود با جابه‌جا کردن فرزندان گره‌ها (و نادیده گرفتن برچسب‌ها) یکی را به دیگری تبدیل کرد.

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

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 isomorphic(A, B):
  9. a = build(A[0])
  10. b = build(B[0])
  11. name_a = name(a)
  12. name_b = name(b)
  13. same = name_a == name_b
  14. return same
  17. def name(node):
  18. # The canonical name of a subtree: its children's names in sorted order, wrapped in brackets.
  19. if node is None:
  20. return ""
  21. first = name(node.left)
  22. second = name(node.right)
  23. if first > second:
  24. first, second = second, first
  25. s = "(" + first + second + ")"
  26. return s
  29. def build(keys):
  30. # A binary search tree from the keys in this insertion order; only its shape matters here.
  31. root = None
  32. for k in keys:
  33. node = Node(k)
  34. if root is None:
  35. root = node
  36. continue
  37. p = root
  38. while True:
  39. if k < p.key:
  40. if p.left is None:
  41. p.left = node
  42. break
  43. p = p.left
  44. else:
  45. if p.right is None:
  46. p.right = node
  47. break
  48. p = p.right
  49. return root

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

شروع اجرا

a

∅

b

∅

name_a—
name_b—
same—

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

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

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

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

A list

[5, 3, 8, 2, 4, 1]

B list

[5, 7, 2, 8, 6, 9]

Call stack

  1. isomorphic()خط 8
گام ۱ از ۳۲۴
خط سیاه = named_a, named_b · خط نارنجی = گام کلیدیbuilt: 0/1 · named: 0/12 · reorder: 0/3 · named_a: 0/1 · named_b: 0/1 · compared: 0/1
    توضیح

    مسئله

    دو درخت ریشه‌دار یکریخت‌اند اگر بشود با جابه‌جا کردن فرزندان گره‌ها (و نادیده گرفتن برچسب‌ها) یکی را به دیگری تبدیل کرد.

    ایده: نام متعارف (Aho–Hopcroft–Ullman)

    به هر زیردرخت از پایین به بالا یک نام می‌دهیم:

    • درخت تهی نام تهی دارد،
    • نام یک گره = ( + نام فرزندانش به ترتیب مرتب + ).

    مرتب کردن نام فرزندان یعنی ترتیب چپ و راست اهمیتی ندارد. دو درخت یکریخت‌اند اگر و تنها اگر نام ریشه‌هایشان یکی باشد.

    هزینه

    با رشته‌ها، ساختن نام‌ها می‌تواند O(n²) باشد؛ نسخه‌ی AHU به جای رشته به هر نام یک عدد صحیح می‌دهد و به O(n) می‌رسد.

    ورودی

    A و B ترتیب درج کلیدها در دو درخت جستجوی دودویی‌اند؛ فقط شکل این درخت‌ها مقایسه می‌شود.