درخت جستجوی دودویی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Y.samadzadeh (بحث | مشارکت‌ها) اضافه کردن دو عکس به درج عنصر |
Y.samadzadeh (بحث | مشارکت‌ها) اضافه کردن سه عکس به حذف گره |
||
خط ۱۰۳:
== حذف یک گره ==
فرض کنید می‌خواهیم گره i را از درخت جستجوی دودویی حذف کنیم. به طوری که P(i){{چر}} نشان‌دهنده والد گره i و C(i){{چر}} نشان‌دهنده فرزند گره i است (چپ یا راست). در مورد حذف یک گره از درخت دودویی، سه حالت مختلف پیش می‌آید:
[[پرونده:Bst-delete-2.jpg|بندانگشتی|حذف گره]]
# i یک گره برگ است.<ref>گره برگ به گرهی می‌گویند که درجه آن صفر باشد. به عبارتی دیگر، هیچ فرزندی نداشته باشد.</ref>
# i یک فرزند دارد.
# i دو فرزند دارد.
<br />
[[پرونده:Bst-delete-3.jpg|بندانگشتی|حذف گره]]
در حالت اول، کافیست اشاره‌گر مناسبی (چپ یا راست) از P(i){{چر}} را برابر تهی قرار دهیم، عمل حذف خاتمه می‌یابد. در حالت دوم که i یک فرزند دارد، ابتدا گره i را حذف می‌کنیم، سپس فرزند i یا همان C(i){{چر}} را جانشین گره i می‌کنیم.
در حالتی که i دو فرزند دارد، باید بزرگترین عنصر در زیردرخت چپ یا کوچکترین عنصر در زیردرخت راست را پیدا کرده و سپس آن را با گره i جایگزین و تعویض می‌کنیم. سپس ما این فرایند را با حذف کردن این عنصر جایگزین از زیردرختی که از آن گرفته شده‌است، دنبال می‌کنیم. به عبارتی دیگر، اگر بخواهیم گره N را از درخت حذف کنیم (که این گره دو فرزند دارد)، به جای اینکه خود گره N را پاک کنیم، یا گره بعد از N در پیمایش میانوندی و یا گره قبل از آن را انتخاب می‌کنیم و آن گره را R می‌نامیم. سپس مقادیر N و R را تعویض می‌کنیم و سپس R را از درخت حذف می‌کنیم.▼
[[پرونده:Bst-delete.jpg|بندانگشتی|216x216پیکسل|حذف گره]]
<br />
[[File:AVL-tree-delete.svg|thumb|500px|left|حذف یک گره با دو فرزند از یک درخت جستجوی دودویی]]
▲در حالتی که i دو فرزند دارد، باید بزرگترین عنصر در زیردرخت چپ یا کوچکترین عنصر در زیردرخت راست را پیدا کرده و سپس آن را با گره i جایگزین و تعویض می‌کنیم. سپس ما این فرایند را با حذف کردن این عنصر جایگزین از زیردرختی که از آن گرفته شده‌است، دنبال می‌کنیم. به عبارتی دیگر، اگر بخواهیم گره N را از درخت حذف کنیم (که این گره دو فرزند دارد)، به جای اینکه خود گره N را پاک کنیم، یا گره بعد از N در پیمایش میانوندی و یا گره قبل از آن را انتخاب می‌کنیم و آن گره را R می‌نامیم. سپس مقادیر N و R را تعویض می‌کنیم و سپس R را از درخت حذف می‌کنیم.
<br />
== پیمایش درخت ==
پیمایش درخت بدین معنی است که به همه عناصر به ترتیب خاصی دسترسی داشته باشیم، بدون اینکه گرهی جا بیفتد یا اینکه گرهی دو بار در دسترس قرار گیرد. درخت جستجوی دودویی یک درخت دودویی است که می‌توان آن را به روش‌های معمول پیمایش کرد. اما از آنجا که نحوه قرار گرفتن عناصر در یک درخت جستجوی دودویی، تضمین می‌کند در هنگام پیمایش درخت به صورت میانوندی، عناصر به ترتیب صعودی در دسترس قرار گیرند، ما این نوع پیمایش را در ادامه بررسی می‌کنیم. درخت جستجوی دودویی را به روش‌های پیش‌ترتیب و پس‌ترتیب هم می‌توان پیمایش کرد، اما این نوع پیمایش‌ها در یک درخت جستجوی دودویی بیهوده هستند. پیمایش میانوندی بدین شکل تعریف می‌شود:
| |||