درخت‌های جستجوی دودویی: پرس‌وجو، درج، و حذف کارآمد

ویژگی درخت-جستجوی-دودویی

یک Binary Search Tree (BST) با استفاده از همان ساختار گره درخت دودویی معرفی‌شده پیش‌تر در این مجموعه سازمان‌دهی می‌شود، اما با یک محدودیت ترتیبی حیاتی به نام Binary-Search-Tree Property (ویژگی درخت-جستجوی-دودویی): برای هر گره x، هر کلید در زیردرخت چپ x کمتر یا مساوی کلید x است، و هر کلید در زیردرخت راست x بزرگ‌تر یا مساوی کلید x است.

مثال یک BST معتبر:
              8
            /   \
           3     10
          / \      \
         1   6      14
            / \     /
           4   7   13

بررسی: هر نواده چپ ≤ اسلاف خودش است،
هر نواده راست ≥ اسلاف خودش است

این ویژگی ترتیبی چیزی است که جستجوی کارآمد را ممکن می‌کند: در هر گره، مقایسه کلید هدف با کلید گره فعلی بلافاصله تعیین می‌کند کدام یک زیردرخت می‌تواند احتمالاً آن را داشته باشد، و زیردرخت دیگر را کاملاً از بررسی حذف می‌کند.

پرس‌وجوی یک درخت جستجوی دودویی

جستجوی یک کلید

TREE-SEARCH(x, k):
  اگر x == NIL یا k == x.key:
      x را برگردان
  اگر k < x.key:
      TREE-SEARCH(x.left, k) را برگردان
  در غیر این صورت:
      TREE-SEARCH(x.right, k) را برگردان

در هر گام، جستجو دقیقاً یک مسیر از ریشه به‌سمت یک برگ را دنبال می‌کند، و کلید هدف را مقایسه می‌کند و بر همین اساس به چپ یا راست شاخه می‌کند. این یعنی زمان اجرا متناسب با طول مسیر دنبال‌شده است، که حداکثر ارتفاع درخت h است، که زمان اجرای O(h) می‌دهد.

یافتن حداقل و حداکثر

به‌دلیل ویژگی درخت-جستجوی-دودویی، عنصر حداقل همیشه با دنبال کردن اشاره‌گرهای چپ تا حد ممکن پیدا می‌شود، و حداکثر با دنبال کردن اشاره‌گرهای راست تا حد ممکن.

TREE-MINIMUM(x):
  تا زمانی که x.left ≠ NIL:
      x = x.left
  x را برگردان

TREE-MAXIMUM(x):
  تا زمانی که x.right ≠ NIL:
      x = x.right
  x را برگردان

هر دو عملیات در زمان O(h) اجرا می‌شوند، و یک مسیر واحد از گره داده‌شده تا یک برگ را دنبال می‌کنند.

یافتن جانشین

Successor (جانشین) یک گره، گره‌ای با کوچک‌ترین کلید بزرگ‌تر از کلید گره داده‌شده است — اساساً، "عنصر بعدی" اگر درخت به ترتیب مرتب‌شده صاف می‌شد. یافتن آن نیازمند دو حالت است.

TREE-SUCCESSOR(x):
  اگر x.right ≠ NIL:
      TREE-MINIMUM(x.right) را برگردان
  y = x.p
  تا زمانی که y ≠ NIL و x == y.right:
      x = y
      y = y.p
  y را برگردان

اگر x یک زیردرخت راست داشته باشد، جانشینش صرفاً حداقل آن زیردرخت راست است — کوچک‌ترین مقداری که همچنان بزرگ‌تر از x است. اگر x زیردرخت راستی نداشته باشد، جانشین با بالا رفتن در درخت تا یافتن اسلافی که فرزند چپ والد خودش باشد پیدا می‌شود — آن والد جانشین است. این عملیات نیز در زمان O(h) اجرا می‌شود.

درج یک کلید جدید

درج از همان منطق مقایسه‌ای جستجو پیروی می‌کند، و در درخت پایین می‌رود تا موقعیت خالی درست برای گره جدید پیدا شود، سپس آن را در آنجا به‌عنوان یک برگ متصل می‌کند.

TREE-INSERT(T, z):
  y = NIL
  x = T.root
  تا زمانی که x ≠ NIL:
      y = x
      اگر z.key < x.key:
          x = x.left
      در غیر این صورت:
          x = x.right
  z.p = y
  اگر y == NIL:
      T.root = z          // درخت خالی بود
  در غیر این صورت اگر z.key < y.key:
      y.left = z
  در غیر این صورت:
      y.right = z

از آنجا که درج صرفاً یک مسیر واحد از ریشه تا برگ را پیش از اتصال گره جدید پیمایش می‌کند، در زمان O(h) اجرا می‌شود، مطابق با جستجو و سایر عملیات‌های پرس‌وجو.

حذف یک کلید: جزئی‌ترین عملیات

حذف ظریف‌تر از درج است چون حذف یک گره ممکن است زیردرخت‌هایش را قطع کند، و ساختار درخت باید با دقت تعمیر شود. سه حالت متمایز باید در نظر گرفته شوند.

حالت ۱: گره هیچ فرزندی ندارد

صرفاً گره را با به‌روزرسانی والدش که دیگر به آن اشاره نکند حذف کن.

حالت ۲: گره دقیقاً یک فرزند دارد

گره را از درخت جدا کن با اتصال والدش مستقیماً به فرزند تکش، که به‌طور مؤثر فرزند را ترفیع می‌دهد تا جای گره حذف‌شده را بگیرد.

حالت ۳: گره دو فرزند دارد

این حالت جزئی‌ترین است. گره نمی‌تواند صرفاً جدا شود، چون دو زیردرخت دارد که هر دو باید در جایی متصل باقی بمانند. راه‌حل استاندارد جانشین گره را پیدا می‌کند (که، همان‌طور که بالا نشان داده شد، باید حداکثر یک فرزند داشته باشد، چون حداقل زیردرخت راست است و بنابراین فرزند چپی ندارد)، و از آن جانشین برای جایگزینی موقعیت گره حذف‌شده استفاده می‌کند.

برای حذف یک گره z با دو فرزند:
1. y = TREE-SUCCESSOR(z) را پیدا کن، که درون زیردرخت راست z قرار دارد
2. اگر y فرزند راست مستقیم z نباشد:
     ابتدا y را از موقعیت فعلی‌اش جدا کن (حالت ۱ یا ۲ بالا)،
     چون y حداکثر یک فرزند دارد (فرزند راستش)
     سپس y را در جای z قرار بده، که هر دو فرزند z را به y می‌دهد
3. اگر y فرزند راست مستقیم z باشد:
     صرفاً y را در جای z قرار بده، فرزند چپ اصلی z را نگه دار
     (y از قبل به‌درستی زیردرخت راست خودش را حفظ می‌کند)

استفاده از جانشین برای جایگزینی گره حذف‌شده به‌طور خودکار ویژگی درخت-جستجوی-دودویی را حفظ می‌کند: جانشین، طبق تعریف، کوچک‌ترین کلید بزرگ‌تر از هر کلید در زیردرخت چپ گره حذف‌شده و کوچک‌تر از هر کلید باقی‌مانده در زیردرخت راستش است، پس دقیقاً در موقعیت خالی‌شده جا می‌شود.

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

از آنجا که حذف شامل حداکثر تعداد ثابتی عملیات TREE-SUCCESSOR و به‌روزرسانی اشاره‌گر است، هرکدام محدودشده به O(h)، کل رویه حذف در زمان O(h) اجرا می‌شود.

وابستگی حیاتی به ارتفاع درخت

هر عملیاتی که در این مقاله پوشش داده شد — جستجو، حداقل، حداکثر، جانشین، درج، و حذف — در زمانی متناسب با ارتفاع درخت h اجرا می‌شود، نه مستقیماً تعداد عناصر n. این تمایز حیاتی است: اگر درخت اتفاقاً متوازن باشد، با ارتفاع Θ(log n)، هر عملیات در زمان Θ(log n) اجرا می‌شود، که با کارایی بهترین ساختارهای مبتنی بر مقایسه مطابقت دارد. اما اگر درخت نامتوازن شود — برای مثال، اگر عناصر به ترتیب از‌قبل‌مرتب‌شده درج شوند، که یک درخت تولید می‌کند که اساساً به یک لیست پیوندی تبدیل می‌شود — ارتفاع می‌تواند به Θ(n) رشد کند، و هر عملیات به Θ(n) کند می‌شود، نه بهتر از یک پیمایش لیست پیوندی ساده.

چرا این درخت‌های جستجوی متوازن را انگیزه می‌دهد

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