درخت جستجوی دودویی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ربات: حذف از رده:ویکی‌سازی رباتیک |
SerendiPity (بحث | مشارکت‌ها) |
||
خط ۲:
|نام = درخت جستجوی دودویی
|نوع = درخت
|اختراع توسط =
|سال اختراع =
|میانگین فضا = O(n)
|فضا در بدترین حالت = O(n)
خط ۲۳:
# تمام کلیدهایی که در زیردرخت سمت چپ واقع شده‌اند، کوچکتر از کلید [[گره ریشه]] هستند.
# تمام کلیدهایی که در زیردرخت سمت راست واقع شده‌اند، بزرگتر از کلید گره ریشه هستند.
# زیردرخت سمت راست و زیردرخت سمت چپ خود درختان جستجوی دودویی هستند.
این ویژگی تضمین می‌کند که [[پیمایش میان‌ترتیب]] یک درخت جستجوی دودویی، کلیدها را به ترتیب صعودی نمایش می‌دهد.
== عملیات اصلی بر روی درخت جستجوی دودویی ==
معمولاً عملیات زیر بر روی یک درخت جستجوی دودویی تعریف می‌شود:
# ایجاد یک درخت جستجوی خالی
# آزمایش خالی بودن درخت
# درج کردن یک کلید جدید در درخت، بدون برهم خوردن خاصیت درخت
# جستجو کردن و یافتین یک کلید خاص در درخت
# حذف کردن یک کلید از درخت، با حفط خاصیت درخت
# [[پیمایش درخت]] جستجوی دودویی، به طوری تمام گره‌ها دقیقاً یک بار مورد دسترسی قرار گیرند.
== جستجو ==
برای پیدا کردن [[گره (علوم رایانه)|گرهی]] با یک کلید خاص مانند key در درخت، ابتدا باید از ریشه درخت شروع کنیم. اگر ریشه تهی باشد، درخت فاقد هر عنصری بوده و جستجو ناموفق خواهد بود. در غیر این صورت، key را با مقدار گره ریشه مقایسه می‌کنیم، اگر برابر بودند، جستجو موفق است و گره ریشه همان گره مورد نظر است. در غیر این صورت، دو حالت پیش خواهد آمد:
# key از گره ریشه کوچکتر است. در این حالت، هیچ عنصری در زیردرخت سمت راست وجود ندارد که مقدار کلید آن برابر با key
# key بزرگتر از گره ریشه است. در این حالت، هیچ عنصری در زیردرخت سمت چپ وجود ندارد که مقدار کلید آن برابر با key
سپس بسته به حالت یک و دو، زیردرخت سمت چپ یا زیردرخت سمت راست را به روش بازگشتی و با استفاده از الگوریتم بالا جستجو می‌کنیم. عمل جستجو در درخت جستجوی دودویی، از مرتبه O(h){{چر}} است که در آن h ارتفاع درخت است. چرا که حداکثر باید به میزان عمق درخت، به طرف پایین حرکت کنیم.
<source lang="c">
node_t search(node_t *root, T value)
{
if(NULL != root)
{
}
return NULL;
}
</source>
خط ۹۸:
== حذف یک گره ==
فرض کنید می‌خواهیم گره i را از درخت جستجوی دودویی حذف کنیم. به طوری که P(i){{چر}} نشان‌دهنده والد گره i و C(i){{چر}} نشان‌دهنده فرزند گره i است (چپ یا راست). در مورد حذف یک گره از درخت دودویی، سه حالت مختلف پیش می‌آید:
# i یک گره برگ است.
# i یک فرزند دارد.
# i دو فرزند دارد.
خط ۱۰۹:
پیمایش درخت بدین معنی است که به همه عناصر به ترتیب خاصی دسترسی داشته باشیم، بدون اینکه گرهی جا بیفتد یا اینکه گرهی دوبار در دسترس قرار گیرد. درخت جستجوی دودویی یک درخت دودویی است که می‌توان آن را به روش‌های معمول پیمایش کرد. اما از آنجا که نحوه قرار گرفتن عناصر در یک درخت جستجوی دودویی، تضمین می‌کند در هنگام پیمایش درخت به صورت میانوندی، عناصر به ترتیب صعودی در دسترس قرار گیرند، ما این نوع پیمایش را در ادامه بررسی می‌کنیم. درخت جستجوی دودویی به روش پیش‌ترتیب و پس‌ترتیب هم می‌توان پیمایش کرد، اما این نوع پیمایش‌ها در یک درخت جستجوی دودویی بیهوده هستند. پیمایش میانودی بدین شکل تعریف می‌شود:
# اگر زیردرخت سمت چپ وجود دارد، آن را به روش میانوندی پیمایش کنید.
# ریشه درخت را ملاقات کنید.
# اگر زیردرخت سمت راست وجود دارد، آن را به روش میانوندی پیمایش کنید.
خط ۱۱۷:
void inorder(node_t *root)
{
if(!root)
{
}
</source>
== انواع ==
درخت جستجوی دودویی گونه‌های مختلفی دارد. [[درخت ای‌وی‌ال]] و [[درخت سرخ-سیاه]] از جمله [[درخت دودوییا خودمتوازن|درختان دودویی خودمتوازن]] هستند. [[درخت اسپلی]] نوعی درخت دودویی است که عناصری که مکرراً مورد استفاده قرار می‌گیرند را به صورت خودکار به ریشه درخت نزدیک می‌کند تا دسترسی به
== پیوند به بیرون ==
خط ۱۴۰:
== منابع ==
* {{یادکرد کتاب |نام خانوادگی=هورویتز |نام=الیس |کتاب=ساختمان داده‌ها به زبان سی | ناشر= انتشارات خراسان|سال=۱۳۷۷}}
* {{یادکرد کتاب |نام خانوادگی= جعفرنژاد قمی|نام=
{{ساختمان داده‌ها}}
| |||