AlgoVerse

درخت دودویی نخ‌کشی‌شده

پیوندهای راست خالی درخت را به جانشین میان‌ترتیب هر گره وصل می‌کند (نخ)؛ بعد پیمایش میان‌ترتیب بدون پشته و بدون بازگشت انجام می‌شود.

در درخت دودویی با n گره، n + 1 پیوند تهی هست. Perlis و Thornton پیشنهاد کردند این پیوندها هدر نروند: پیوند راست تهی هر گره به جانشین میان‌ترتیب آن اشاره کند. به این پیوندها نخ (thread) می‌گویند. (نسخه‌ی کامل، پیوندهای چپ تهی را هم به پیشینِ میان‌ترتیب وصل می‌کند.)

ادامه‌ی توضیح ↓
ورودی:
n=7خروجی PDF

درخت جستجوی هفت‌گره‌ای؛ سه نخ کشیده می‌شود (۳→۶، ۷→۱۵ و ۱۷→۱۸) و پیمایش ۳ ۶ ۷ ۱۵ ۱۷ ۱۸ ۲۰ را بدون پشته می‌دهد.

  1. class Node:
  2. def __init__(self, key):
  3. self.key = key
  4. self.left = None
  5. self.right = None
  6. self.thread = None # used only when right is empty: the inorder successor
  9. def threaded(root):
  10. # Phase 1: an inorder walk; every node with an empty right link gets a thread to its successor.
  11. stack = []
  12. prev = None
  13. node = root
  14. while node is not None or stack:
  15. if node is not None:
  16. stack.append(node)
  17. node = node.left
  18. else:
  19. node = stack.pop()
  20. if prev is not None and prev.right is None:
  21. prev.thread = node
  22. prev = node
  23. node = node.right
  24. # Phase 2: inorder again, with no stack: follow a thread, or go right and then all the way left.
  25. out = []
  26. node = root
  27. while node is not None and node.left is not None:
  28. node = node.left
  29. while node is not None:
  30. out.append(node.key)
  31. if node.right is None:
  32. node = node.thread
  33. else:
  34. node = node.right
  35. while node.left is not None:
  36. node = node.left
  37. return out

ناوردا: در پیمایش، هر گره‌ای که پیوند راست ندارد با نخش مستقیماً به گره‌ی بعدی میان‌ترتیب می‌رسد.

شروع اجرا

36715171820

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

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

root object

  • key = 15
  • left = Node(key=6, left=Node(key=3, left=None, right=None, thread=None), right=Node(key=7, left=None, right=None, thread=None), thread=None)
  • right = Node(key=18, left=Node(key=17, left=None, right=None, thread=None), right=Node(key=20, left=None, right=None, thread=None), thread=None)
  • thread = None

Call stack

  1. threaded()خط 9
گام ۱ از ۱۲۰
خط سیاه = thread, visit · خط نارنجی = گام کلیدیthread: 0/3 · start_walk: 0/1 · down_left: 0/3 · visit: 0/7 · by_thread: 0/4 · go_right: 0/3
    توضیح

    ایده

    در درخت دودویی با n گره، n + 1 پیوند تهی هست. Perlis و Thornton پیشنهاد کردند این پیوندها هدر نروند: پیوند راست تهی هر گره به جانشین میان‌ترتیب آن اشاره کند. به این پیوندها نخ (thread) می‌گویند. (نسخه‌ی کامل، پیوندهای چپ تهی را هم به پیشینِ میان‌ترتیب وصل می‌کند.)

    پیمایش بدون پشته

    با نخ‌ها، از هر گره گره‌ی بعدی میان‌ترتیب راحت پیدا می‌شود:

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

    پس پیمایش میان‌ترتیب بدون پشته و بدون بازگشت انجام می‌شود.

    در عمل

    باید بدانیم پیوند راست یک گره فرزند واقعی است یا نخ. کتاب‌ها برای این یک بیت پرچم در هر گره نگه می‌دارند؛ اینجا نخ در فیلد جدای thread است. نخ‌ها با خط‌چین کشیده شده‌اند.