تو کتاب طورانی در قسمت حذف از درخت جستجوی دودویی گفته:
اگه گره‌ای که می‌خواهیم حذف کنیم دو فرزند داشت باید ابتدا گره مابعد یا ماقبل آن‌را در پیمایش 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;
{
{
۱ 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;
{
تا دستور ۲ کافیه دیگه بقیش واسه چیه
گره مابعد کوچکترین گره‌ای است که از گره‌ای که می‌خواهیم حذف کنیم بزرگتره
اصلا از دو به بعدشو نمی‌فهمم
اگه کسی ازش سردرآورد لطفا واسم توضیح بده
تا خط ۲ حالتی رو داره توضیح میده که ما دنبال گره ای هستیم که فرزند راست داره که در اون صورت به زیرشاخه راست میریم و min رو پیدا میکنیم
از خط ۲ به بعد حالتی هست که درخت فرزند راست نداره برای همین باید به پدر گره بره . حالا اگه x فرزند راست گره پدر باشه، گره پدر از x کوچکتر هست واسه همین پدر x رو برابر با خود x قرار میدیم و همین عمل رو تکرار می کنیم! این تکرار تا جایی ادامه پیدا می کنه که x فرزند چپ پدرش باشه! اون موقع پدر x می شه گره ما بعد x اولیه!
اگه شکل این حالت رو بکشی راحت متوجه می شه.
اگه جاییش رو نفهمیدی بگو بیشتر بگم.
(۱۹ شهریور ۱۳۸۹ ۰۴:۱۲ ب.ظ)sina_n نوشته شده توسط: اگه گره‌ای که می‌خواهیم حذف کنیم دو فرزند داشت باید ابتدا گره مابعد یا ماقبل آن‌را در پیمایش inorderپیدا کنیم و اونو به جای این گره بزاریم
فقط یه چیزی رو باید اضافه کنم که این الگوریتم، الگوریتم کلی پیدا کردم گره مابعد در درخت جستجوی دودویی هست و ربطی به شرطی که برای حذف در جمله قبلش( دو فرزند داشته باشه) گفتید نداره.
این شکل رو هم نگاه کن. تو این شکل خط های قرمز که از گره به گره های سمت راستش کشیده شده successor گره رو نشون میده
![[تصویر: exampl2.gif]](http://cg.scs.carleton.ca/~luc/1997notes/topic20/exampl2.gif)
این شکل رو هم بررسی کن. تو این شکل خط های قرمز که از هر گره به سمت راست خارج شده به گره successor اشاره داره:
این شکل رو هم بررسی کن. تو این شکل خط های قرمز که از هر گره به سمت راست خارج شده به گره successor اشاره داره:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
دوست عزیز الگوریتم غلط می باشد و ابهامات زیادی دارد.