حذف گره از درخت نخي

شروع موضوع توسط sasan_66 ‏24 ژوئن 2007 در انجمن خانواده C++ , C

  1. sasan_66

    sasan_66 کاربر تازه وارد

    تاریخ عضویت:
    ‏18 جولای 2006
    نوشته ها:
    450
    تشکر شده:
    0
    براي حذف گرهي ار درخت نخي در صورتي كه خود اون گره 2 فرزند چپ و راست داره و فرزندان هم خودشون فرزند چپ وراست دارند چه طوريه؟
    كدش رو نميخوام
    مي خوام بدونم با حذف گره فرزند چپش به جاش ميشينه يا راستش؟
    اون فرزندي كه باقي مونده كجا ميره؟
     
  2. برترین مرکز خرید و فروش وب سایت
  3. bloody

    bloody کاربر فعال علم و دانش کاربر فعال

    تاریخ عضویت:
    ‏19 آپریل 2007
    نوشته ها:
    1,226
    تشکر شده:
    14
    محل سکونت:
    IRAN
    مطمئنی میشه از درخت نخی دودوئی گرهی رو حذف کرد؟!
     
  4. sasan_66

    sasan_66 کاربر تازه وارد

    تاریخ عضویت:
    ‏18 جولای 2006
    نوشته ها:
    450
    تشکر شده:
    0
    نميشه؟؟
    چرا؟
     
  5. Arash_j13

    Arash_j13 Registered User

    تاریخ عضویت:
    ‏18 فوریه 2005
    نوشته ها:
    778
    تشکر شده:
    2
    محل سکونت:
    مشهد
    مثل بقیه درخت ها ما هیچ وقت یه گره با دو فرزند رو حذف نمی کنیم به جاش یه جانشین پیدا می کنیم که بزگترین گره دو زیر درخت چپ یا کوچکترین گره دو زیر درخت راست می تونه باشه بعد جاش رو اون جدیده عوض می کنیم و گرهی که جایگذین شده رو حذف می کنیم این گره جدید مطمئنا یه فرزند یا بدونه فرزند هست امتحان کنید متوجه می شید چرا
     
  6. sasan_66

    sasan_66 کاربر تازه وارد

    تاریخ عضویت:
    ‏18 جولای 2006
    نوشته ها:
    450
    تشکر شده:
    0
    امروز قيل از اين كه شما اين جواب رو بدين از يه نفر پرسيدم كه گفت توي درخت هاي نخي دودوئي بايد پيمايش inorder قبل از حذف با بعد از حذف يكي باشه
     
  7. Arash_j13

    Arash_j13 Registered User

    تاریخ عضویت:
    ‏18 فوریه 2005
    نوشته ها:
    778
    تشکر شده:
    2
    محل سکونت:
    مشهد
    خب عنصر قبلی تو پیمایس indorder می شه بزگترین تو زیر درخت چپ و عنصر بعدی می شه کوچکترین تو زیر درخت چپ
     
  8. خرید بیت کوین
  9. sasan_66

    sasan_66 کاربر تازه وارد

    تاریخ عضویت:
    ‏18 جولای 2006
    نوشته ها:
    450
    تشکر شده:
    0
    آقا آرش منظورتون رو از بزرگترين و كوچكترين نمي فهمم!!
    منظورتون داده هاشونه؟
     
  10. Arash_j13

    Arash_j13 Registered User

    تاریخ عضویت:
    ‏18 فوریه 2005
    نوشته ها:
    778
    تشکر شده:
    2
    محل سکونت:
    مشهد
    آره منظورم داده هاشون هست روش پیدا کردنش هم خیلی ساده است برای پیدا کردن بزرگترین عنصر تو زیر درخت چپ یه قدم به چپ برید تا جایی که ممکنه و به نخ بر نمی خوردید به راست حرکت کنید هر جایی که به جای لینک واقعی نخ داشتید اون گره بزرگترین گره تو زیر درخت چپ هست روش پیدا کردن کوچکترین تو زیر درخت راست هم همیطوری یه قدم بع راست و بعد تا جای ممکن به چپ حرکت کنید
     
  11. bloody

    bloody کاربر فعال علم و دانش کاربر فعال

    تاریخ عضویت:
    ‏19 آپریل 2007
    نوشته ها:
    1,226
    تشکر شده:
    14
    محل سکونت:
    IRAN
    آقا آرش این روش حذف که شما گفتی فقط در هرم حداکثر به کار نمیره؟!!!


    در پیمایش inorder یک درخت نخی عنصر قبلی و بعدی چه جوری میتونن بزرگترین و کوچکترین تو زیر درخت چپ باشن؟مگه در چیدن عناصر در درخت نخی ترتیب خاصی رو رعایت میکنیم؟شاید عنصری که پیمایش شده خودش بزرگترین یا کوچکترین در زیر درخت چپ باشه!!!

    بازم مثل قسمت بالا توجیهی نداره که آخرین عنصر در زیر درخت سمت چپ بزرگترین عنصر باشه !!ولی در درخت جستجو دودوئی این حرف رو میتونیم بزنیم اونم برعکس چیزی که شما گفتی!یعنی اگه در زیر درخت سمت چپ پایین بریم تا زمانی که left child صفر بشه اون عنصر کوچکترین عنصر هست.
    و به طور کلی اگه یه درخت bst رو به صورت inorder پیمایش کنیم اعداد به صورت صعودی مرتب میشن.

    در کل نظر من اینه که درخت نخی رو به دید یه قابلیت نگاه کنین یعنی ما در درخت نخی میایم برای اینکه تعداد اشاره گر های واقعی رو افزایش بدیم میایم و از اتصلات تهی برای ارتباط با دیگر گره ها استفاده میکنیم.(طبق قوانین پرلیس و تورنتن).در درخت نخی دودوئی نخ برای برگ ها تعریف شده و به فرض اینکه بخوایم گره رو از درخت حذف کنیم باید از برگ ها حذف بشه و بعد از حذف باید دو تا تغیر در پدر اون گره ایجاد بکنیم یکی لینک و دیگری true کردن یکی از thread ها(بسته به این که فرزند چپ حذف شده یا فرزند راست)
    این که میگم باید یکی از برگ ها باشه بخاطر اینه که اگه شما بیایی و پدر یکی از برگ ها رو حذف کنی لینک اون برگ به هم میخوره و دردسر داره شدنش شاید بشه!!
    ولی بازم میگم هنوز شک دارم بشه از درخت نخی عنصری رو حذف کرد اگه هم بشه این کار رو کرد از نظر مرتبه زمانی توجیه نداره...
     
  12. Arash_j13

    Arash_j13 Registered User

    تاریخ عضویت:
    ‏18 فوریه 2005
    نوشته ها:
    778
    تشکر شده:
    2
    محل سکونت:
    مشهد
    تا اونجایی که یادمه ما تو هرم همیشه از ریشه حذف می کنیم و به بقیه گره ها کاری نداریم
    درسته من سوال رو کامل نخوندم فکر کردم منظورشون درخت جستجوری دودویی هست که در اون صورت این گفته درسته
    ببین وقتی شما همش به چپ برید کوچکترین عنصر تو زیر درخت چپ رو پیدا می کنید ولی کوچکترین عنصور تو زیر درخت چپ به در ما نمی خوره ما بزرگترین عنصر تو زیر درخت چپ رو می خواییم که می شه یه قدم به چپ و بعد تا جایی که به نخ نرسیم به راست این عنصر که می شه بزگترین تو زیر درخت راست تو پیمایش inorder تو درخت جستجوی دو دویی همیشه قبل از ریشه می یاد
    و عنصر بعد ریشه هم می شه کوچکترین عنصر تو زیر درخت راست که روش به دست اوردنش برعکس بزگرتین تو زیر درخت چپ هست

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

    bloody کاربر فعال علم و دانش کاربر فعال

    تاریخ عضویت:
    ‏19 آپریل 2007
    نوشته ها:
    1,226
    تشکر شده:
    14
    محل سکونت:
    IRAN
    فرمایش شما کاملا صحیحه!


    میشه یکم بیشتر توضیح بدی ؟!!برای حذف باید بزرگترین عنصر رو پیدا کنیم!
     
  14. Arash_j13

    Arash_j13 Registered User

    تاریخ عضویت:
    ‏18 فوریه 2005
    نوشته ها:
    778
    تشکر شده:
    2
    محل سکونت:
    مشهد
    دقت کنید که این که باید بزگترین رو در BST پیدا کنیم به این خاطر هست که ما بعد حذف نباید پیمایش inorder رو خراب کنیم خو به نظر شما عنصر قبل از عنصری که می خواد حذف بشه کدوم مگه نه اینکه از بزرگترین عنصر تو تمام عناصری هست که از این عضو کوچکتره؟

    اگه هم یه درخت دودویی معمولی باشه باز هم نباید پیمایش Inorder رو بهم بزنیم اگه شما راهی دیگه لی بلد هستید که بشه پیمایش Inorder رو حفط کردید بگید
     
  15. bloody

    bloody کاربر فعال علم و دانش کاربر فعال

    تاریخ عضویت:
    ‏19 آپریل 2007
    نوشته ها:
    1,226
    تشکر شده:
    14
    محل سکونت:
    IRAN
    :blink: یعنی وقتی میخوایم یه عنصر از BST حذف کنیم باید بزرگترین عنصر باشه؟ اول شما میگفتی باید بزرگترین تو زیر درخت سمت چپ رو پیدا کنیم!بالاخره نفهمیدم چی شد

    منظورت اینه که شرط حذف کردن عنص بهم نخوردن پیمایش inorder درخت هست ؟
     
  16. sasan_66

    sasan_66 کاربر تازه وارد

    تاریخ عضویت:
    ‏18 جولای 2006
    نوشته ها:
    450
    تشکر شده:
    0
    خوب منظور من از درخت نخي درخت معمولي دودويي هستش كه ترتيب داده ها برخلاف درخت هايي مثل BSTاصلا مهم نيست
    حالا خودم يه چيزي نوشتم كه ترتيب پيمايش inorder رو حفظ كنه
    بايد يه چند تايي تست كنم تا در همه شرايط ببينم درست جواب ميده يا نه
     
  17. Arash_j13

    Arash_j13 Registered User

    تاریخ عضویت:
    ‏18 فوریه 2005
    نوشته ها:
    778
    تشکر شده:
    2
    محل سکونت:
    مشهد
    بله وقتی ما عنصری رو حذف می کنمی نباید پیمایش رو بهم بریزیم برای همین به اونکاری که گفتم نیاز هست

    موفق باشید
     
عسل طبیعی و گرده گل ایرانیavanak  همکاری در فروش