AlgoVerse

درخت آماره‌ی ترتیبی (OS-Select و OS-Rank)

درخت جستجویی که هر گره اندازه‌ی زیردرختش را نگه می‌دارد؛ با آن، i-امین کوچک‌ترین کلید و رتبه‌ی هر کلید در O(h) پیدا می‌شود.

اگر هر گره‌ی درخت جستجو اندازه‌ی زیردرختش (size) را هم نگه دارد، می‌توانیم آماره‌های ترتیبی را بدون پیمایش کل درخت پیدا کنیم. این یک نمونه‌ی افزودن به ساختار داده (augmenting) است (CLRS فصل ۱۷).

ادامه‌ی توضیح ↓
ورودی:
A 1×12 · i=5 · k=38خروجی PDF

۱۲ کلید؛ پنجمین کوچک‌ترین ۱۹ است و رتبه‌ی ۳۸، ۱۰ است. عدد کوچک زیر هر گره اندازه‌ی زیردرخت آن است.

  1. class Node:
  2. def __init__(self, key):
  3. self.key = key
  4. self.left = None
  5. self.right = None
  6. self.size = 1 # the number of nodes in this subtree
  9. def os_tree(A, i, k):
  10. root = build(A[0])
  11. found = select(root, i)
  12. r = rank(root, k)
  13. return [found, r]
  16. def size(x):
  17. if x is None:
  18. return 0
  19. return x.size
  22. def select(x, i):
  23. # The i-th smallest key: the root of a subtree is its (size(left) + 1)-th smallest.
  24. while x is not None:
  25. r = size(x.left) + 1
  26. if i == r:
  27. return x.key
  28. if i < r:
  29. x = x.left
  30. else:
  31. i = i - r
  32. x = x.right
  33. return None
  36. def rank(root, k):
  37. # How many keys are ≤ k: add up the left subtrees (and nodes) we pass on the way right.
  38. r = 0
  39. x = root
  40. while x is not None:
  41. if k < x.key:
  42. x = x.left
  43. elif k > x.key:
  44. r = r + size(x.left) + 1
  45. x = x.right
  46. else:
  47. r = r + size(x.left) + 1
  48. return r
  49. return None
  52. def build(keys):
  53. # An ordinary search tree, with each node's size updated on the way down.
  54. root = None
  55. for key in keys:
  56. node = Node(key)
  57. if root is None:
  58. root = node
  59. continue
  60. p = root
  61. while True:
  62. p.size = p.size + 1
  63. if key < p.key:
  64. if p.left is None:
  65. p.left = node
  66. break
  67. p = p.left
  68. else:
  69. if p.right is None:
  70. p.right = node
  71. break
  72. p = p.right
  73. return root

ناوردا: x.size = size(x.left) + size(x.right) + 1 برای هر گره؛ در OS-SELECT، جواب همیشه i-امین کلید زیردرخت x است.

شروع اجرا

∅

i5
r—
found—

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

i5
k38

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

A list

[26, 17, 41, 14, 21, 30, 47, 10, 16, 19, 28, 38]

Call stack

  1. os_tree()خط 9
گام ۱ از ۳۱۷
خط سیاه = selected, ranked · خط نارنجی = گام کلیدیbuilt: 0/1 · at: 0/4 · go_left: 0/2 · go_right: 0/1 · found: 0/1 · selected: 0/1 · rank_right: 0/2 · rank_left: 0/1 · rank_found: 0/1 · ranked: 0/1
    توضیح

    ایده

    اگر هر گره‌ی درخت جستجو اندازه‌ی زیردرختش (size) را هم نگه دارد، می‌توانیم آماره‌های ترتیبی را بدون پیمایش کل درخت پیدا کنیم. این یک نمونه‌ی افزودن به ساختار داده (augmenting) است (CLRS فصل ۱۷).

    OS-SELECT(x, i)

    ریشه‌ی هر زیردرخت، size(left) + 1-امین کوچک‌ترین کلید آن است. اگر i همین است، جواب ریشه است؛ اگر کمتر است به چپ برو؛ وگرنه به راست برو و دنبال (i − r)-امین بگرد.

    OS-RANK(k)

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

    نگه داشتن اندازه‌ها

    در درج، اندازه‌ی گره‌های مسیر یکی زیاد می‌شود؛ در چرخش‌ها (درخت قرمز-سیاه) فقط اندازه‌ی دو گره عوض می‌شود. پس با درخت متوازن همه‌ی عمل‌ها O(log n) می‌مانند.

    ورودی

    A ترتیب درج کلیدها، i رتبه‌ای که می‌خواهیم و k کلیدی که رتبه‌اش را می‌خواهیم.