درخت جستجوی دودویی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Y.samadzadeh (بحث | مشارکت‌ها) ویرایش |
Y.samadzadeh (بحث | مشارکت‌ها) اضافه کردن متن به تعریف برچسب‌ها: همهٔ رده‌ها را حذف کرد ویرایشگر دیداری |
||
خط ۱۹:
== تعریف ==
درخت جستجوی دودویی، نوعی [[درخت دودویی]] است که ممکن است تهی
# از تعدادی [[گره (علوم رایانه)|گره]] تشکیل شده که هر گره دارای یک کلید است. کلیدها منحصربه‌فرد هستند و در درخت کلید تکراری وجود ندارد.
# تمام کلیدهایی که در زیردرخت سمت چپ واقع شده‌اند، کوچکتر از کلید [[گره ریشه]] هستند.
# تمام کلیدهایی که در زیردرخت سمت راست واقع شده‌اند، بزرگتر از کلید گره ریشه هستند.
# زیردرخت سمت راست و زیردرخت سمت چپ خود درختان جستجوی دودویی هستند.
این ویژگی تضمین میکند که [[
در ادامه برخی اصطلاح‌های مهم مربوط به درخت مورد اشاره قرار گرفته است:
* مسیر (path) – منظور از مسیر در یک درخت، یک توالی از گره‌ها در راستای یال‌های درخت است.
* ریشه (Root) – گرهی که در بخش فوقانی درخت قرار دارد، ریشه نامیده میشود. هر درختی تنها یک ریشه دارد و از گره ریشه تنها یک مسیر به هر گره دیگر وجود دارد.
* والد (parent) – هر گرهی به جز گره ریشه یالی به سمت بالا به یک گره دارد، که والد آن گره نامیده میشود.
* فرزند (child) – گرهی که زیر یک گره مفروض قرار دارد و از طریق یالی به سمت پایین به آن وصل شده است، گره فرزند آن نامیده میشود.
* برگ (leaf) – گرهی که هیچ فرزندی دارد، برگ نامیده میشود.
* زیردرخت (Subtree) – به مجموعه فرزندان یک گره، زیردرخت گفته میشود.
* بازدید (Visiting) – منظور از بازدید، بررسی ارزش یک گره است، هنگامی که کنترل روی گره قرار دارد.
* پیمایش (Traversing) – منظور از پیمایش، عبور از میان گره‌های یک درخت با ترتیب خاص است.
* سطوح (Levels) – سطح یک گره نماینده نسل آن فرزند است. اگر گره ریشه در سطح 0 باشد، در این صورت فرزندان آن در سطح 1، نوه‌های آن در سطح 2 و همین طور تا آخر … قرار دارند.
* کلیدها (Keys) – کلید نماینده ارزش یک گره بر مبنای نوع عملیات جستجویی است که قرار است روی گره انجام شود.
== عملیات اصلی بر روی درخت جستجوی دودویی ==
سطر ۳۴ ⟵ ۴۷:
# جستجو کردن و یافتن یک کلید خاص در درخت
# حذف کردن یک کلید از درخت، با حفظ خاصیت درخت
# [[پیمایش درخت]] جستجوی دودویی، به طوری
== جستجو ==
برای پیدا کردن [[گره (علوم رایانه)|گرهی]] با یک کلید خاص مانند key در درخت، ابتدا باید از ریشه درخت شروع کنیم. اگر ریشه تهی باشد، درخت فاقد هر عنصری بوده و جستجو ناموفق خواهد بود. در غیر این صورت، key را با مقدار گره ریشه مقایسه می‌کنیم، اگر برابر بودند، جستجو موفق است و گره ریشه همان گره مورد نظر است. در غیر این صورت، دو حالت پیش خواهد آمد:
# key از گره ریشه
# key
سپس بسته به حالت یک و دو، زیردرخت سمت چپ یا زیردرخت سمت راست را به روش بازگشتی و با استفاده از الگوریتم بالا جستجو می‌کنیم. عمل جستجو در درخت جستجوی دودویی، از مرتبه O(h){{چر}} است که در آن h ارتفاع درخت است. چرا که حداکثر باید به میزان عمق درخت،
<syntaxhighlight lang="c">
node_t search(node_t *root, T value)
{
سطر ۵۵ ⟵ ۶۶:
else if(value <root->key)
else
}
سطر ۶۶ ⟵ ۷۷:
== درج عنصر جدید ==
برای درج کردن یک [[گره (علوم رایانه)|گره]] جدید در درخت جستجوی دودویی، باید گره را طوری درج کرد که خاصیت درخت برهم نخورد و درخت همچنان یک درخت جستجوی دودویی باقی بماند. برای حفظ خاصیت اول (منحصربه‌فرد بودن کلیدها)، باید ابتدا درخت را جستجو کنیم تا مطمئن شویم که عنصر قبلاً در درخت درج نشده‌است. پس از اینکه مطمئن شدیم کلید مورد نظر از قبل در درخت وجود ندارد، می‌توانیم کلید را در درخت درج کنیم. اگر درخت تهی بود، کافیست گره جدید را به عنوان گره ریشه درج کنیم تا عمل درج خاتمه یاد. اگر درخت خالی نبود، کلید جدید را با ریشه مقایسه می‌کنیم، که دو حالت جستجو پیش می‌آید:
# کلید جدید از ریشه کوچکتر است. در این حالت گره باید در زیردرخت سمت چپ درج شود. مراحل بالا را به روش بازگشتی ادامه میدهیم تا مکان مورد نظر در درخت پیدا شود. سپس گره را درج می‌کنیم.
# کلید جدید از ریشه بزرگتر است. در این حالت گره باید در زیردرخت سمت راست درج شود. مراحل بالا را به روش بازگشتی ادامه میدهیم تا مکان مورد نظر در درخت پیدا شود. سپس گره را درج می‌کنیم.
عمل درج در درخت جستجوی دودویی، از مرتبه O(h){{چر}} است.
<syntaxhighlight lang="c">typedef int T
سطر ۱۰۳ ⟵ ۱۱۱:
== حذف یک گره ==
فرض کنید می‌خواهیم گره i را از درخت جستجوی دودویی حذف کنیم. به طوری که P(i){{چر}} نشان‌دهنده والد گره i و C(i){{چر}} نشان‌دهنده فرزند گره i است (چپ یا راست). در مورد حذف یک گره از درخت دودویی، سه حالت مختلف پیش می‌آید:
# i یک گره برگ است.<ref>گره برگ به گرهی می‌گویند که درجه آن صفر باشد. به عبارتی دیگر، هیچ فرزندی نداشته باشد.</ref>
# i یک فرزند دارد.
# i دو فرزند دارد.
در حالت اول، کافیست اشاره‌گر مناسبی (چپ یا راست) از P(i){{چر}} را برابر تهی قرار دهیم، عمل حذف خاتمه می‌یابد. در حالت دوم که i یک فرزند دارد، ابتدا گره i را حذف می‌کنیم، سپس فرزند i یا همان C(i){{چر}} را جانشین گره i می‌کنیم.
در حالتی که i دو فرزند دارد، باید بزرگترین عنصر در زیردرخت چپ یا کوچکترین عنصر در زیردرخت راست را پیدا کرده و سپس آن را با گره i جایگزین و تعویض می‌کنیم. سپس ما این فرایند را با حذف کردن این عنصر جایگزین از زیردرختی که از آن گرفته شده‌است، دنبال می‌کنیم. به عبارتی دیگر، اگر بخواهیم گره N را از درخت حذف کنیم (که این گره دو فرزند دارد)، به جای اینکه خود گره N را پاک کنیم، یا گره بعد از N در پیمایش میانوندی و یا گره قبل از آن را انتخاب می‌کنیم و آن گره را R می‌نامیم. سپس مقادیر N و R را تعویض می‌کنیم و سپس R را از درخت حذف می‌کنیم.▼
[[File:AVL-tree-delete.svg|thumb|500px|left|حذف یک گره با دو فرزند از یک درخت جستجوی دودویی]]
▲در حالتی که i دو فرزند دارد، باید بزرگترین عنصر در زیردرخت چپ یا کوچکترین عنصر در زیردرخت راست را پیدا کرده و سپس آن را با گره i جایگزین و تعویض می‌کنیم. سپس ما این فرایند را با حذف کردن این عنصر جایگزین از زیردرختی که از آن گرفته شده‌است، دنبال می‌کنیم. به عبارتی دیگر، اگر بخواهیم گره N را از درخت حذف کنیم (که این گره دو فرزند دارد)، به جای اینکه خود گره N را پاک کنیم، یا گره بعد از N در پیمایش میانوندی
== پیمایش درخت ==
پیمایش درخت بدین معنی است که به همه عناصر به ترتیب خاصی دسترسی داشته باشیم، بدون اینکه گرهی جا بیفتد یا اینکه گرهی دو بار در دسترس قرار گیرد. درخت جستجوی دودویی یک درخت دودویی است که میتوان آن را به روش‌های معمول پیمایش کرد. اما از آنجا که نحوه قرار گرفتن عناصر در یک درخت جستجوی دودویی، تضمین میکند در هنگام پیمایش درخت به صورت میانوندی، عناصر به ترتیب صعودی در دسترس قرار گیرند، ما این نوع پیمایش را در ادامه بررسی می‌کنیم. درخت جستجوی دودویی
# اگر زیردرخت سمت چپ وجود دارد، آن را به روش میانوندی پیمایش کنید.
# ریشه درخت را ملاقات کنید.
سطر ۱۷۸ ⟵ ۱۴۵:
== انواع ==
درخت جستجوی دودویی گونه‌های مختلفی دارد. [[درخت ای‌وی‌ال]] و [[درخت سرخ-سیاه]] از جمله [[درخت
== جستارهای وابسته ==
سطر ۲۰۶ ⟵ ۱۵۶:
* [[داده ساختار تیریپ]]
* [[درخت جستجوی دودویی بهینه]]
{{Div col end
▲{{پایان چپ‌چین}}== پیوند به بیرون ==
* [https://web.archive.org/web/20110224075255/http://www.algorithmha.ir/post.aspx?no=17 معرفی، درج و حذف از درخت جستجوی دودویی]
سطر ۲۱۷ ⟵ ۱۶۵:
== منابع ==
* {{یادکرد کتاب |نام خانوادگی=هورویتز |نام=الیس |کتاب=ساختمان داده‌ها به زبان سی | ناشر= انتشارات خراسان|سال=۱۳۷۷}}
*سایت فرادرس
* {{یادکرد کتاب |نام خانوادگی= جعفرنژاد قمی|نام= عین‌الله|کتاب=ساختمان داده‌ها در C++{{چر}} | ناشر=انتشارات علوم رایانه |سال=۱۳۹۰}}
سطر ۲۳۰ ⟵ ۱۷۶:
[[رده:درخت‌های دودویی]]
[[رده:ساختمان داده]]
| |||