برگزیده های پرشین تولز

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

sasan_66

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

bloody

کاربر فعال علم و دانش
کاربر فعال
تاریخ عضویت
19 آپریل 2007
نوشته‌ها
1,256
لایک‌ها
17
محل سکونت
IRAN
مطمئنی میشه از درخت نخی دودوئی گرهی رو حذف کرد؟!
 

sasan_66

کاربر تازه وارد
تاریخ عضویت
18 جولای 2006
نوشته‌ها
450
لایک‌ها
0
نميشه؟؟
چرا؟
 

Arash_j13

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

sasan_66

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

Arash_j13

Registered User
تاریخ عضویت
18 فوریه 2005
نوشته‌ها
778
لایک‌ها
2
محل سکونت
مشهد
خب عنصر قبلی تو پیمایس indorder می شه بزگترین تو زیر درخت چپ و عنصر بعدی می شه کوچکترین تو زیر درخت چپ
 

sasan_66

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

Arash_j13

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

bloody

کاربر فعال علم و دانش
کاربر فعال
تاریخ عضویت
19 آپریل 2007
نوشته‌ها
1,256
لایک‌ها
17
محل سکونت
IRAN
مثل بقیه درخت ها ما هیچ وقت یه گره با دو فرزند رو حذف نمی کنیم به جاش یه جانشین پیدا می کنیم که بزگترین گره دو زیر درخت چپ یا کوچکترین گره دو زیر درخت راست می تونه باشه بعد جاش رو اون جدیده عوض می کنیم و گرهی که جایگذین شده رو حذف می کنیم این گره جدید مطمئنا یه فرزند یا بدونه فرزند هست امتحان کنید متوجه می شید چرا
آقا آرش این روش حذف که شما گفتی فقط در هرم حداکثر به کار نمیره؟!!!


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

آره منظورم داده هاشون هست روش پیدا کردنش هم خیلی ساده است برای پیدا کردن بزرگترین عنصر تو زیر درخت چپ یه قدم به چپ برید تا جایی که ممکنه و به نخ بر نمی خوردید به راست حرکت کنید هر جایی که به جای لینک واقعی نخ داشتید اون گره بزرگترین گره تو زیر درخت چپ هست روش پیدا کردن کوچکترین تو زیر درخت راست هم همیطوری یه قدم بع راست و بعد تا جای ممکن به چپ حرکت کنید

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

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

Arash_j13

Registered User
تاریخ عضویت
18 فوریه 2005
نوشته‌ها
778
لایک‌ها
2
محل سکونت
مشهد
آقا آرش این روش حذف که شما گفتی فقط در هرم حداکثر به کار نمیره؟!!!
تا اونجایی که یادمه ما تو هرم همیشه از ریشه حذف می کنیم و به بقیه گره ها کاری نداریم
در پیمایش inorder یک درخت نخی عنصر قبلی و بعدی چه جوری میتونن بزرگترین و کوچکترین تو زیر درخت چپ باشن؟مگه در چیدن عناصر در درخت نخی ترتیب خاصی رو رعایت میکنیم؟شاید عنصری که پیمایش شده خودش بزرگترین یا کوچکترین در زیر درخت چپ باشه!!!

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

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

bloody

کاربر فعال علم و دانش
کاربر فعال
تاریخ عضویت
19 آپریل 2007
نوشته‌ها
1,256
لایک‌ها
17
محل سکونت
IRAN
تا اونجایی که یادمه ما تو هرم همیشه از ریشه حذف می کنیم و به بقیه گره ها کاری نداریم
فرمایش شما کاملا صحیحه!


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

Arash_j13

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

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

bloody

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

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

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

sasan_66

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

Arash_j13

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

خوب منظور من از درخت نخي درخت معمولي دودويي هستش كه ترتيب داده ها برخلاف درخت هايي مثل BSTاصلا مهم نيست
حالا خودم يه چيزي نوشتم كه ترتيب پيمايش inorder رو حفظ كنه
بايد يه چند تايي تست كنم تا در همه شرايط ببينم درست جواب ميده يا نه
موفق باشید
 
بالا