درخت جستجوی دودویی: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
نجات ۱ منبع و علامتزدن ۰ بهعنوان مرده.) #IABot (v2.0 |
بدون خلاصۀ ویرایش |
||
خط ۶۴:
== درج عنصر جدید ==
برای درج کردن یک [[گره (علوم رایانه)|گره]] جدید در درخت جستجوی دودویی، باید گره را طوری درج کرد که خاصیت درخت برهم نخورد و درخت همچنان یک درخت جستجوی دودویی باقی بماند. برای حفظ خاصیت اول (منحصربهفرد بودن کلیدها)، باید ابتدا درخت را جستجو کنیم تا مطمئن شویم که عنصر قبلاً در درخت درج نشدهاست. پس از اینکه مطمئن شدیم کلید مورد نظر از قبل در درخت وجود ندارد، میتوانیم کلید را در درخت درج کنیم. اگر درخت تهی بود، کافیست گره جدید را به عنوان گره ریشه درج کنیم تا عمل درج خاتمه یاد. اگر درخت خالی نبود، کلید جدید را با ریشه مقایسه میکنیم، که دو حالت جستجو پیش میآید:
# کلید جدید از ریشه کوچکتر است. در این حالت گره باید در زیردرخت سمت چپ درج شود. مراحل بالا را به روش بازگشتی ادامه میدهیم تا مکان مورد نظر در درخت پیدا شود. سپس گره را درج میکنیم.
# کلید جدید از ریشه بزرگتر است. در این حالت گره باید در زیردرخت سمت راست درج شود. مراحل بالا را به روش بازگشتی ادامه میدهیم تا مکان مورد نظر در درخت پیدا شود. سپس گره را درج میکنیم.
|