در این جلسه تیم کدگیت را با آموزش درخت جستجوی دودویی در سی پلاس پلاس با همراهی کنید. پیش نیاز این قسمت شامل موارد زیر است:
قبل از ایتکه توضیحات را آغاز کنم باید بگوییم که توضیحات الگوریتمی این آموزش از سایت www.algorithmha.ir گرفته شده است.
درخت دودویی
درختی است که هر گره آن دارای حداکثر دو گره فرزند است که به آنها فرزند راست و چپ گره گفته می‌شود. به همین ترتیب زیردرختی که فرزند راست در رأس آن قرار دارد زیردرخت راست و زیردرختی که فرزند چپ در رأس آن قرار دارد زیردرخت چپ گره نامیده می‌شوند.
درخت جستجوی دودویی
درختی دودویی است که برای هر گره آن شروط زیر برقرار هستند:
1- مقادیر تمامی گره‌های زیردرخت راست – در صورت وجود – از مقدار گره بزرگتر هستند.
2- مقادیر تمامی گره‌های زیردرخت چپ – در صورت وجود – از مقدار گره کوچکتر هستند.
با توجه به چنین تعریفی، واضح است که فرزندان چپ و راست یک گره در صورت وجود به ترتیب مقداری کمتر و بیشتر از مقدار خود گره دارند.
کاربرد درخت جستجوی دودویی
مهمترین کاربرد چنین درختی از نام آن مشخص است. این درخت با توجه به تعریف آن برای انجام عملیات جستجو مناسب است. فرض کنید در مجموعه اعداد درخت فوق به دنبال عدد 6 هستیم. ابتدا 6 را با مقدار گره رأس یعنی5 مقایسه می‌کنیم. این گره، گره مورد نظر ما نیست. عدد 6 هم از عدد 5 بزرگتر است. در نتیجه با توجه به تعریف درخت جستجوی دودویی، مطمئن هستیم که اگر گرهی با مقدار6 وجود داشته باشد، به طور حتم در زیردرخت راست گره 5 است. پس به سمت راست حرکت کرده و عدد 6 را با 8 مقایسه می‌کنیم. باز هم به گره مطلوب نرسیدیم. اما با توجه به اینکه 6 از 8 کوچکتر است، به زیردرخت چپ گره 8 مراجعه می‌کنیم. در این مرحله به گره با مقدار 6 می‌رسیم که گره مطلوب ما است.
اگر در حین جستجو مجبور به حرکت به سمتی شدیم که زیردرختی وجود ندارد، به این معنی است که گره مورد نظر در درخت وجود ندارد.
عملیات‌های اصلی بر روی درخت جستجوی دودویی
معمولاً عملیات زیر بر روی یک درخت جستجوی دودویی تعریف می‌شود:
- ایجاد یک درخت جستجوی خالی
- آزمایش خالی بودن درخت
- درج کردن یک کلید جدید در درخت، بدون برهم خوردن خاصیت درخت
- جستجو کردن و یافتن یک کلید خاص در درخت
- حذف کردن یک کلید از درخت، با حفط خاصیت درخت
- پیمایش درختجستجوی دودویی، به طوری تمام گره‌ها دقیقاً یک بار مورد دسترسی قرار گیرند.
درج گره جدید در درخت جستجوی دودویی
زمانی که اقدام به درج یک گره جدید در درخت جستجوی دودویی می‌کنیم، باید محل مناسبی برای این گره پیدا کنیم. برای یافتن محل مناسب، فرض می‌کنیم که چنین گرهی در درخت وجود دارد و عملیات جستجو را برای آن انجام می‌دهیم. در نهایت به طور حتم به گرهی خواهیم رسید که حداقل یکی از فرزندان آن تهی است (چرا؟). این گره والد گره جدید خواهد بود.
برای مثال فرض کنید می‌خواهیم گرهی با مقدار 7 را به درخت فوق اضافه کنیم:
و اگر گرهی با مقدار صفر درج کنیم:
زمانی که قصد ساخت یک درخت جستجوی دودویی را داریم، ترتیب درج مقادیر تاثیر مستقیمی در عمق درخت و سرعت اجرای عملیات جستجو خواهد داشت. اگر مجموعه اعداد وارد شده از قبل مرتب باشند، درخت به دست آمده از عمق n خواهد بود که در هر لایه‌ی آن تنها یک گره وجود دارد:
حذف گره از درخت جستجوی دودویی
حذف گره از درخت جستجوی دودویی پیچیده‌گی‌هایی دارد که گاهی گره را تنها با علامت‌گذاری حذف می‌کنند. به عبارت دیگر در این حالت هر گره درخت شامل فیلدی است که وضعیت حذف آن را مشخص می‌کند. اگر گرهی را با استفاده از تغییر مقدار این فیلد حذف کنیم، در عمل حافظه آن آزاد نشده و تغییری در ساختار درخت ایجاد نمی‌شود. اما در پردازش‌های آتی، این گره را در نظر نمی‌گیریم. اما گاهی نیاز است که گره به طور کامل حذف شده و حافظه‌ی مصرفی آن نیز آزاد شود.
هر گره در درخت جستجوی دودویی ممکن است در یکی از سه وضعیت زیر باشد:
- گره فاقد فرزند است: یعنی گره مذکور یک برگ است. در چنین حالتی به راحتی می‌توان گره را حذف کرده و فضای مصرفی آن را آزاد کرد.
2.گره دارای یک فرزند است: در این حالت گره فرزند را جایگزین گره مذکور می‌کنیم. به عبارت ساده‌تر، بین والد گره و فرزند گره ارتباط مستقیم برقرار کرده و گره مطلوب را حذف می‌کنیم.
3.گره دارای دو فرزند است: این حالت کمی پیچیده‌تر از حالت‌های قبلی است. ابتدا گرهی با کوچک‌ترین مقدار در زیردرخت راست گره را پیدا می‌کنیم. درج این گره به جای گره قبلی شروط درخت جستجوی دودویی را به هم نمی‌زند (چرا؟). در نتیجه می‌توان به راحتی آن را جایگزین کرد.
گرهی که جایگزین می‌شود به طور حتم فرزند چپ ندارد (چرا؟). اما ممکن است فرزند راست داشته باشد. در این حالت عمل حذف طی دو مرحله انجام می‌شود. ابتدا گره جایگزین از محل خود بنا به حالت شماره‌ی 2حذف می‌شود. سپس گره اصلی با جایگزین شدن این گره حذف می‌گردد. حال نوبت به پیاده سازی درخت دودویی جستجو در سی پلاس پلاس رسیده است.
پیاده سازی درخت جستجوی دودویی در سی پلاس پلاس
برای پیاده سازی درخت دودویی در سی پلاس پلاس ابتدا باید یک Struct برای نگهداری مقدار هر گره و فرزندان چپ و راست آن داشته باشیم.Struct به نام Node همین کار را برای ما می‌کند.
struct node {
int key;
struct node *left, *right;
};
Node شامل سه فیلد key و left و righ است که به ترتیب مقدار گره و فرزندان چپ و راست آن را نشان می‌دهد.
بعد از ساخت هر گره نیاز به ساخت درخت است برای این کار توابع insert و newNode نوشتیم. در زیر پیاده سازی این توابع آورده شده است:
struct node *newNode(int item) {
struct node *temp = (struct node *) malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
struct node* insert(struct node* node, int key) {
if (node == NULL)
return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
return node;
}
درخت ما نیاز به یک ریشه دارد که با آن به بقیه گره ها دسترسی پیدا کنیم. ما در Main برنامه root را در درخت برای ارجاع به ریشه قرار دادیم. کد درج در درخت را در Struct به نام insert قرار دادیم. NewNode نیز برای ساخت یک گره جدید استفاده می‌شود.
پیمایش درخت جستجوی دودویی در سی پلاس پلاس
در این قسمت به توضیح درباره انواع پیمایش ها نخواهیم پرداخت و شما میتوانید در لینک اطلاعات کسب کنید.در زیر کد پیمایشinorder در درخت دودویی آمده است. ما از این کد برای پیمایش درخت جستجوی دودویی در سی پلاس پلاس در برنامه خود استفاده کردیم.
void inorder(struct node *root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}
تست برنامه درخت جستجوی دودویی در سی پلاس پلاس
این قسمت برای کد خود یک main مینویسیم. کد زیر main برنامه درخت جستجوی دودویی است.
int main() {
struct node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
inorder(root);
return 0;
}
خروجی برنامه به صورت زیر می‌باشد(خروجی پیمایش inorder درخت ما است):
20 30 40 50 60 70 80
