حذف یک نود در درخت دودویی یا باینری سرچ

[zoghal]

من روش و الگوریتم حذف یک نود در bts رو میخوام

یعنی وقتی یک نود که دارای 2 فرزند هست وقتی حذف میشه فرزند ها به چه صورت به درخت متصل میشود؟

[someCoder]

من روش و الگوریتم حذف یک نود در bts رو میخوام

یعنی وقتی یک نود که دارای 2 فرزند هست وقتی حذف میشه فرزند ها به چه صورت به درخت متصل میشود؟

در این صورت حذف نمیشه گره و براش جانشین پیدا میکنی. یا بزرگترن عنصر در زیر درخت سمت چپ یا کوچکترین عنصر در زیر درخت سمت راست.
روش فرمولی پیدا کردنش هم اینه: مثلا اگر بزرگترن عنصر در زیر درخت سمت چپ رو بخوای: یک قدم به چپ، تا جایی که جا داره به راست!

[zoghal]

من دقیقا منظور شما رو نفهمیدم.
نکته این که یادم رفت بگم این هست که درخت مرتب شده است

زمانی که نودی حذف میشود بزرگ ترین فرزندش باید جایگزین نود حذف شده قرار بگیره؟!
حالا فرزند دیگر به چه ترتیبی به درخت اصلی وصل میشه
در نظر داشته باشید که نودی که جایگزین میشه خود دارای 2 فرزند می باشد.

[someCoder]

نکته این که یادم رفت بگم این هست که درخت مرتب شده استوقتی میگی BST یعنی همین دیگه.


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

مثال:
http://i7.tinypic.com/6gvrc74.gif

13 میخواد حذف بشه. از زیر درخت چپ، بزرگترن عنصر برای جایگزینی باهاش پیدا میشه!
بازم نفهمیدی در خدمتم

[zoghal]

ممنون از جوابتون
لازم بذکر هست که تو کتاب نوشته که کوچیکتر به سمت چپ و بزرگتر به سمت راست

اگر پایه رو بر این اساس قرار دهیم
این مسئله درست حل شده است؟
http://i16.tinypic.com/6b1hlk4.jpg
در این درخت 25 حذف میشود
http://i14.tinypic.com/541wb2v.jpg


آیا درست اعمال شده؟

[someCoder]

لازم بذکر هست که تو کتاب نوشته که کوچیکتر به سمت چپ و بزرگتر به سمت راستمن جلسه اول سال اول دبستان تو درس ریاضی غایب بود. برای همین هم چپ و راست رو قاطی میکنم! اگر اشتباه گفتم خودت بگیر مطلب رو :چشمک:

در مورد سوالت: اگر 25 رو میخوای حذف کنی:
در صورت جایگزینی از درخت سمت راست: کوچکترین در این زیردرخت: 27
http://i14.tinypic.com/6biwpvo.png

در صورت جایگزینی از درخت سمت چپ: بزرگترین در این زیردرخت: 23
http://i13.tinypic.com/4uv064o.png

[tarane_khani]

سلام:منم مثله شما الگوریتم حذف از bst رو میخوام بنویسم ولی نمیتونم و حتما باید به استادم تحویل بدم میشه یا خود الگوریتم رو بذارید یا راهنمایی کنید
ممنون میشم