مثل بقیه درخت ها ما هیچ وقت یه گره با دو فرزند رو حذف نمی کنیم به جاش یه جانشین پیدا می کنیم که بزگترین گره دو زیر درخت چپ یا کوچکترین گره دو زیر درخت راست می تونه باشه بعد جاش رو اون جدیده عوض می کنیم و گرهی که جایگذین شده رو حذف می کنیم این گره جدید مطمئنا یه فرزند یا بدونه فرزند هست امتحان کنید متوجه می شید چرا
آقا آرش این روش حذف که شما گفتی فقط در هرم حداکثر به کار نمیره؟!!!
خب عنصر قبلی تو پیمایس indorder می شه بزگترین تو زیر درخت چپ و عنصر بعدی می شه کوچکترین تو زیر درخت چپ
در پیمایش inorder یک درخت نخی عنصر قبلی و بعدی چه جوری میتونن بزرگترین و کوچکترین تو زیر درخت چپ باشن؟مگه در چیدن عناصر در درخت نخی ترتیب خاصی رو رعایت میکنیم؟شاید عنصری که پیمایش شده خودش بزرگترین یا کوچکترین در زیر درخت چپ باشه!!!
آره منظورم داده هاشون هست روش پیدا کردنش هم خیلی ساده است برای پیدا کردن بزرگترین عنصر تو زیر درخت چپ یه قدم به چپ برید تا جایی که ممکنه و به نخ بر نمی خوردید به راست حرکت کنید هر جایی که به جای لینک واقعی نخ داشتید اون گره بزرگترین گره تو زیر درخت چپ هست روش پیدا کردن کوچکترین تو زیر درخت راست هم همیطوری یه قدم بع راست و بعد تا جای ممکن به چپ حرکت کنید
بازم مثل قسمت بالا توجیهی نداره که آخرین عنصر در زیر درخت سمت چپ بزرگترین عنصر باشه !!ولی در درخت جستجو دودوئی این حرف رو میتونیم بزنیم اونم برعکس چیزی که شما گفتی!یعنی اگه در زیر درخت سمت چپ پایین بریم تا زمانی که left child صفر بشه اون عنصر کوچکترین عنصر هست.
و به طور کلی اگه یه درخت bst رو به صورت inorder پیمایش کنیم اعداد به صورت صعودی مرتب میشن.
در کل نظر من اینه که درخت نخی رو به دید یه قابلیت نگاه کنین یعنی ما در درخت نخی میایم برای اینکه تعداد اشاره گر های واقعی رو افزایش بدیم میایم و از اتصلات تهی برای ارتباط با دیگر گره ها استفاده میکنیم.(طبق قوانین پرلیس و تورنتن).در درخت نخی دودوئی نخ برای برگ ها تعریف شده و به فرض اینکه بخوایم گره رو از درخت حذف کنیم باید از برگ ها حذف بشه و بعد از حذف باید دو تا تغیر در پدر اون گره ایجاد بکنیم یکی لینک و دیگری true کردن یکی از thread ها(بسته به این که فرزند چپ حذف شده یا فرزند راست)
این که میگم باید یکی از برگ ها باشه بخاطر اینه که اگه شما بیایی و پدر یکی از برگ ها رو حذف کنی لینک اون برگ به هم میخوره و دردسر داره شدنش شاید بشه!!
ولی بازم میگم هنوز شک دارم بشه از درخت نخی عنصری رو حذف کرد اگه هم بشه این کار رو کرد از نظر مرتبه زمانی توجیه نداره...