سلام دوستان
در مورد سوال ۳۷ آی تی ۹۲ که در مورد حذف و درج یه عنصر دلخواه و همچنین کاهش یه مقدار خاص از یکی از عناصر درخت هست و سوال شده که چنتا از این موارد رو میشه با (o(log n انجام داد.
پاسخ هر سه مورد یعنی گزینه ی ۴ هست و من روی حذف یه عنصر دلخواه از درخت شک دارم که log n باشه و اگر میگفت حذف یه عنصر از درخت میشد بگی چون قطعا ریشه باید حذف بشه زمان log n هست اما حالا که گفته یه عنصر دلخواه باید اول درخت رو با زمان n بگردی تا عنصر رو پیدا کنی بعد در زمان log n حذف کنی که میشه (O(n
دوستان کسی میدونه چرا گزینه ۴ شده؟ و گزینه ی ۳ یعنی ۲ مورد درست نیست؟
حرف شما درسته مثلا اگه بگه ۴ را از این درخت خذف کنید، اول باید توی برگا با O(n) پیداش کنیم بعد خذفش کنیم و با lgn تا هم درخت رو آپ دیت کنیم، ولی درخت چون کامل هست پس توی ارایه به سبک هیپ ذخیره شده و این جا اگه به ما بگن که مثلا A[10] رو حذف کن صرف نظر از مقدارش این با lg n میشه. اون چیزی که توی ذهن شما هست فکر کنم بشه حذف یک عنصر مشخص.
حذف عنصر دلخوا پیچیدگی O n Log n داره ولی اینجا
تو صورت سوال گفته که اعداد توی برگها ذخیره شدن
(۰۸ آذر ۱۳۹۲ ۰۲:۵۸ ب.ظ)Riemann نوشته شده توسط: حرف شما درسته مثلا اگه بگه ۴ را از این درخت خذف کنید، اول باید توی برگا با O(n) پیداش کنیم بعد خذفش کنیم و با lgn تا هم درخت رو آپ دیت کنیم، ولی درخت چون کامل هست پس توی ارایه به سبک هیپ ذخیره شده و این جا اگه به ما بگن که مثلا A[10] رو حذف کن صرف نظر از مقدارش این با lg n میشه. اون چیزی که توی ذهن شما هست فکر کنم بشه حذف یک عنصر مشخص.
ممنون. فک میکنم تمام نکته اش توی این که گفته عناصر در برگ ها هستند و فقط کافیه عمق درخت رو با log n پیمایش کرد و بعدش هم با یه تغییر لینک گره مورد نظر حذف میشه و من به این موضوع دقت نکرده بودم.البته درخت های هیپ کلا کامل هستند و این موضوع مهمی نیست و تاثیری توی جواب نداره
ممنون دوست عزیز مشکل حل شد