زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۰۷:۲۵ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

الگوریتم حذف عنصر کیمنه از BST - کتاب داده ساختار ها

subtitle
ارسال:
  

هاتف پرسیده:

الگوریتم حذف عنصر کیمنه از BST - کتاب داده ساختار ها

سلام
توی کتاب داده ساختار های دکتر قدسی، الگوریتم زیر برای حذف عنصر کمینه آورده شده:


و روند کار رو توی این شکل هم نشون داده:


توی توضیحات گفته شده عنصر کمینه t هست که در آخرین مرحله بهش میرسیم، برای حذف کافی است که دستور [tex]r\rightarrow right®[/tex]
انجام شود
در صورتی که من فکر میکنم این جلمه اشتباهه و باید مینوشت [tex]r\rightarrow right( left®) )[/tex] و اینطور که اینجا گفته شده اون گره t حذف نمیشه!
به نظرم توی اون الگوریتم هم باید بین خط ۵ و ۶ دستور:
[tex]left( parent®)\leftarrow right®[/tex]
باید اضافه بشه تا درست کار کنه!
نظر شما چیه؟
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

azk84 پاسخ داده:

RE: الگوریتم حذف عنصر کیمنه از BST - کتاب داده ساختار ها

الگوریتم درسته کاملاً.

توی الگوریتم فرض شده که فراخوانی تابع با مرجع انجام میشه (Call by reference)، بنابراین درون تابع، متغیر اشاره‌گر r (که داره به محل گره جاری اشاره می‌کنه) در واقع خود متغیر اشاره‌گر چپ پدر گره‌ی جاری هستش که از فراخوانی قبلی به اینجا رسیده! بنابراین اضافه کردن left(parent)->right غلط نیست، ولی کاملاً بیهوده است! (چی در اومد! :دی).

در مورد (r->right(left هم منظورتونو راستش نفهمیدم، چون اگه r ما left داشته باشه که اصلاً وارد این قسمت کد نمیشه چون شرط ورودش null بودن left هستش.
مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

هاتف پاسخ داده:

RE: الگوریتم حذف عنصر کیمنه از BST - کتاب داده ساختار ها

(۱۳ شهریور ۱۳۹۲ ۱۰:۴۰ ب.ظ)azk84 نوشته شده توسط:  الگوریتم درسته کاملاً.

توی الگوریتم فرض شده که فراخوانی تابع با مرجع انجام میشه (Call by reference)، بنابراین درون تابع، متغیر اشاره‌گر r (که داره به محل گره جاری اشاره می‌کنه) در واقع خود متغیر اشاره‌گر چپ پدر گره‌ی جاری هستش که از فراخوانی قبلی به اینجا رسیده! بنابراین اضافه کردن left(parent)->right غلط نیست، ولی کاملاً بیهوده است! (چی در اومد! :دی).

در مورد (r->right(left هم منظورتونو راستش نفهمیدم، چون اگه r ما left داشته باشه که اصلاً وارد این قسمت کد نمیشه چون شرط ورودش null بودن left هستش.
احتمالا ایراد من مربوط به همون توضیح اولی شما درباره call by reference هست! راستش جملات سطر دوم و سوم تون کمی گیج کنندس!
گفتید r داره به محل گره ی جاری اشاره میکنه؟ من فرض میکنم منظورتون از گره ی جاری همونی گره ی بالایی توی تصویر هست، در این صورت طبق این تصویر t فرزند چپ نداره ولی r هر دو رو داره!
من عرض کردم در این لحظه برای حذف گره ی t باید:
۱- lchild گره ای که r بهش اشاره میکنه رو برابر rchild گره ی t کنیم (این کار عملا گره ی t رو از درخت حذف میکنه)
۲- گره ی t رو Free کنیم!
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Aseman7 پاسخ داده:

RE: الگوریتم حذف عنصر کیمنه از BST - کتاب داده ساختار ها

نقل قول: مطمئن هستید؟ این کد بلافاصله بعد از اون شکل اومده و جدا از م نیستند که باهم فرق کنند، جایی هم اشاره ای به اینکه اینها با هم متفاوت باشند نکرده و به نظرم این خیلی بعیده!



بله مشخص است ؛ من خودم کتاب رو دارم می بینم .
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Aseman7 پاسخ داده:

RE: الگوریتم حذف عنصر کیمنه از BST - کتاب داده ساختار ها

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

۰
ارسال:
  

azk84 پاسخ داده:

RE: الگوریتم حذف عنصر کیمنه از BST - کتاب داده ساختار ها

همون‌طور که Aseman7 هم اشاره کرد، شکل کمی گمراه‌کننده‌است و سعی کن با تصور خودت بدون شکل ببینی چی میشه ;-)

منظورم از خط‌های ۲ و ۳ اینه:
r یک متغیر اشاره‌گر هستش که درونش آدرس گره‌ی جاری (گره‌ای که کمینه هستش و فرزند چپ نداره و می‌خوایم حذف شه) قرار داره.
این r در واقع همون ورودی تابع هستش. این ورودی تابع هم از فراخوانی بازگشتی همین تابع در مرحله‌ی قبل اومده که قطعاً پارامتری که اونجا به عنوان ورودی فراخوانی بازگشتی داده شده، [tex]left[r][/tex] بوده. بنابراین، چون فراخوانی با ارجاع هستش، پس r ما توی تابع، خود [tex]left[parent[r]][/tex] خواهد بود!

فکر کنم بازم بد گفتم، ولی امیدوارم بتونین دیکد کنین حرفمو Undecided
مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Aseman7 پاسخ داده:

RE: الگوریتم حذف عنصر کیمنه از BST - کتاب داده ساختار ها

همون طور که در کتاب هم معلومه این شکل (در ص ۲۲۴ ) مربوط به توضیحات ص قبل است(ص ۲۲۳ ) و اصلا" هم گمراه کننده نیست.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

azk84 پاسخ داده:

RE: الگوریتم حذف عنصر کیمنه از BST - کتاب داده ساختار ها

(۱۳ شهریور ۱۳۹۲ ۱۱:۵۱ ب.ظ)Aseman7 نوشته شده توسط:  همون طور که در کتاب هم معلومه این شکل (در ص ۲۲۴ ) مربوط به توضیحات ص قبل است(ص ۲۲۳ ) و اصلا" هم گمراه کننده نیست.

آها خوب من نگاه به کتاب نکردم، ببخشید :دی
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

هاتف پاسخ داده:

RE: الگوریتم حذف عنصر کیمنه از BST - کتاب داده ساختار ها

(۱۳ شهریور ۱۳۹۲ ۱۱:۲۹ ب.ظ)azk84 نوشته شده توسط:  همون‌طور که Aseman7 هم اشاره کرد، شکل کمی گمراه‌کننده‌است و سعی کن با تصور خودت بدون شکل ببینی چی میشه ;-)

منظورم از خط‌های ۲ و ۳ اینه:
r یک متغیر اشاره‌گر هستش که درونش آدرس گره‌ی جاری (گره‌ای که کمینه هستش و فرزند چپ نداره و می‌خوایم حذف شه) قرار داره.
این r در واقع همون ورودی تابع هستش. این ورودی تابع هم از فراخوانی بازگشتی همین تابع در مرحله‌ی قبل اومده که قطعاً پارامتری که اونجا به عنوان ورودی فراخوانی بازگشتی داده شده، [tex]left[r][/tex] بوده. بنابراین، چون فراخوانی با ارجاع هستش، پس r ما توی تابع، خود [tex]left[parent[r]][/tex] خواهد بود!
فکر کنم بازم بد گفتم، ولی امیدوارم بتونین دیکد کنین حرفمو Undecided

دستتون درد نکنه فهمیدم Smile
یعنی چندین و چند بار همون توضیحات اول شما رو خوندم و متوجه شدم بالاخره. ممنون.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال: #۱۰
  

azk84 پاسخ داده:

RE: الگوریتم حذف عنصر کیمنه از BST - کتاب داده ساختار ها

(۱۴ شهریور ۱۳۹۲ ۰۷:۵۷ ب.ظ)هاتف نوشته شده توسط:  
(13 شهریور ۱۳۹۲ ۱۱:۲۹ ب.ظ)azk84 نوشته شده توسط:  همون‌طور که Aseman7 هم اشاره کرد، شکل کمی گمراه‌کننده‌است و سعی کن با تصور خودت بدون شکل ببینی چی میشه ;-)

منظورم از خط‌های ۲ و ۳ اینه:
r یک متغیر اشاره‌گر هستش که درونش آدرس گره‌ی جاری (گره‌ای که کمینه هستش و فرزند چپ نداره و می‌خوایم حذف شه) قرار داره.
این r در واقع همون ورودی تابع هستش. این ورودی تابع هم از فراخوانی بازگشتی همین تابع در مرحله‌ی قبل اومده که قطعاً پارامتری که اونجا به عنوان ورودی فراخوانی بازگشتی داده شده، [tex]left[r][/tex] بوده. بنابراین، چون فراخوانی با ارجاع هستش، پس r ما توی تابع، خود [tex]left[parent[r]][/tex] خواهد بود!
فکر کنم بازم بد گفتم، ولی امیدوارم بتونین دیکد کنین حرفمو Undecided

دستتون درد نکنه فهمیدم Smile
یعنی چندین و چند بار همون توضیحات اول شما رو خوندم و متوجه شدم بالاخره. ممنون.

خوشحالم که توضیحاتم به دردتون خورد :-). خواهش می‌کنم ;-)
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  حذف اکانت Alireza_1387 ۴ ۵,۱۹۶ ۱۴ آذر ۱۴۰۱ ۰۸:۲۱ ب.ظ
آخرین ارسال: shirin.kh90
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۱۰۸ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  ساختمان داده و پایگاه داده پارسه امیدوار ۴ ۳,۹۶۳ ۱۲ خرداد ۱۳۹۹ ۰۸:۰۳ ب.ظ
آخرین ارسال: marvelous
  حذف درس برای خواندن کنکور ارشد sima84 ۴ ۴,۴۱۶ ۲۶ اردیبهشت ۱۳۹۹ ۰۹:۰۰ ب.ظ
آخرین ارسال: عزیز دادخواه
Smile دانلود فیلم های آموزش پایگاه داده-دکتر حق جو دانشگاه علم و صنعت ایران Bakhtabad ۱۹ ۲۸,۸۷۵ ۱۸ شهریور ۱۳۹۸ ۰۱:۰۸ ق.ظ
آخرین ارسال: keshvari9
  افزایش واگرایی الگوریتم های مبتنی بر جمعیت moslem73421 ۲ ۲,۷۷۴ ۰۵ شهریور ۱۳۹۸ ۱۰:۵۳ ب.ظ
آخرین ارسال: cpt.mazi
  دانلود آموزش تصویری کلاس درس تحلیل و طراحی الگوریتم های پیشرفته دانشگاه فردوسی jazana ۱۳ ۱۲,۷۵۲ ۱۰ خرداد ۱۳۹۸ ۰۵:۴۲ ب.ظ
آخرین ارسال: Valipourh20
  خلاصه داده الگوریتم boshbosh ۷ ۱۰,۱۲۸ ۲۲ بهمن ۱۳۹۷ ۱۲:۳۷ ق.ظ
آخرین ارسال: sajjad_s84
Question تفاوت تعداد مقایسه های مورد نیاز در الگوریتم های متفاوت porseshgar ۰ ۱,۹۲۴ ۱۵ بهمن ۱۳۹۷ ۱۲:۳۳ ب.ظ
آخرین ارسال: porseshgar
  حذف از b tree کمک لطفا Sanazzz ۰ ۱,۶۳۲ ۱۱ بهمن ۱۳۹۷ ۰۹:۳۴ ب.ظ
آخرین ارسال: Sanazzz

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close