زمان کنونی: ۰۶ دى ۱۴۰۳, ۰۲:۲۶ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

پیدا کردن گره مابعد در حذف از درخت جستجوی دودویی

ارسال:
  

sina_n پرسیده:

پیدا کردن گره مابعد در حذف از درخت جستجوی دودویی

تو کتاب طورانی در قسمت حذف از درخت جستجوی دودویی گفته:

اگه گره‌ای که می‌خواهیم حذف کنیم دو فرزند داشت باید ابتدا گره مابعد یا ماقبل آن‌را در پیمایش inorder‌پیدا کنیم و اونو به جای این گره بزاریم

برای پیدا کردن گره مابعد این کد رو داده

Tree_Successor(x)
{
۱ if right[x]!= nil
۲ then return Tree _Minimum(right[x]);
۳ y = parent[x];
۴ while y!= nil and x = right[y];
۵ x = y;
۶ y = parent[y];
۷ return y;
{


تا دستور ۲ کافیه دیگه بقیش واسه چیه

گره مابعد کوچکترین گره‌ای است که از گره‌ای که می‌خواهیم حذف کنیم بزرگتره

اصلا از دو به بعدشو نمی‌فهمم

اگه کسی ازش سردرآورد لطفا واسم توضیح بده

نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

luna پاسخ داده:

پیدا کردن گره مابعد در حذف از درخت جستجوی دودویی

تا خط ۲ حالتی رو داره توضیح میده که ما دنبال گره ای هستیم که فرزند راست داره که در اون صورت به زیرشاخه راست میریم و min رو پیدا میکنیم
از خط ۲ به بعد حالتی هست که درخت فرزند راست نداره برای همین باید به پدر گره بره . حالا اگه x فرزند راست گره پدر باشه‌، گره پدر از x کوچکتر هست واسه همین پدر x رو برابر با خود x قرار میدیم و همین عمل رو تکرار می کنیم! این تکرار تا جایی ادامه پیدا می کنه که x فرزند چپ پدرش باشه! اون موقع پدر x می شه گره ما بعد x اولیه!
اگه شکل این حالت رو بکشی راحت متوجه می شه.
اگه جاییش رو نفهمیدی بگو بیشتر بگم.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

luna پاسخ داده:

پیدا کردن گره مابعد در حذف از درخت جستجوی دودویی

(۱۹ شهریور ۱۳۸۹ ۰۴:۱۲ ب.ظ)sina_n نوشته شده توسط:  اگه گره‌ای که می‌خواهیم حذف کنیم دو فرزند داشت باید ابتدا گره مابعد یا ماقبل آن‌را در پیمایش inorder‌پیدا کنیم و اونو به جای این گره بزاریم

فقط یه چیزی رو باید اضافه کنم که این الگوریتم، الگوریتم کلی پیدا کردم گره مابعد در درخت جستجوی دودویی هست و ربطی به شرطی که برای حذف در جمله قبلش( دو فرزند داشته باشه) گفتید نداره.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

luna پاسخ داده:

پیدا کردن گره مابعد در حذف از درخت جستجوی دودویی

این شکل رو هم نگاه کن. تو این شکل خط های قرمز که از گره به گره های سمت راستش کشیده شده successor گره رو نشون میده

[تصویر:  exampl2.gif]
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

luna پاسخ داده:

پیدا کردن گره مابعد در حذف از درخت جستجوی دودویی

این شکل رو هم بررسی کن. تو این شکل خط های قرمز که از هر گره به سمت راست خارج شده به گره successor اشاره داره:
[تصویر:  exampl2.gif]
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

luna پاسخ داده:

پیدا کردن گره مابعد در حذف از درخت جستجوی دودویی

این شکل رو هم بررسی کن. تو این شکل خط های قرمز که از هر گره به سمت راست خارج شده به گره successor اشاره داره:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

csharpisatechnology پاسخ داده:

پیدا کردن گره مابعد در حذف از درخت جستجوی دودویی

دوست عزیز الگوریتم غلط می باشد و ابهامات زیادی دارد.
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۴,۹۲۴ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  حذف اکانت Alireza_1387 ۴ ۵,۸۱۷ ۱۴ آذر ۱۴۰۱ ۰۸:۲۱ ب.ظ
آخرین ارسال: shirin.kh90
  پیدا کردن دستگیره manager_66 ۵ ۵,۱۹۴ ۲۸ آذر ۱۴۰۰ ۱۲:۴۴ ب.ظ
آخرین ارسال: blackhalo1989
  تا به حال شده خدا فرصت زندگی کردن دوباره رو بهت بده؟مرگ از جلوی چشمات رد شده؟ abraham ۲۱ ۱۶,۳۱۷ ۲۰ دى ۱۳۹۹ ۱۰:۵۶ ب.ظ
آخرین ارسال: raam
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۶۵۶ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۷۹۸ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  جایی برای پیدا کردن توابع آماده جاوااسکریپت f.b ۷ ۴,۶۶۰ ۲۰ آذر ۱۳۹۹ ۰۴:۰۸ ب.ظ
آخرین ارسال: calm
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۴۲۱ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  عمق درخت ???? rad.bahar ۱ ۲,۴۴۰ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  پیدا کردن موضوع پایان نامه k1.technology ۲ ۸,۱۷۸ ۲۱ خرداد ۱۳۹۹ ۱۲:۵۴ ب.ظ
آخرین ارسال: bankabzar

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close