سلام، سوال رو پیوست کردم پاسخ گزینه ی دوم هست، کسی میتونه این سوال رو تشریح کنه؟
![[تصویر: 241986_problem_algorithm_100_92.gif]](https://img.manesht.ir/241986_problem_algorithm_100_92.gif)
نمیدونم شاید این راهی که میگم درست باشه: هر بار مقدار فرزندان چپ و راست گره پدر رو با مقدار گره پدر جمع کنید و مجموع رو در فرزندان بنویسید و این کار رو در مورد فرزندان هم تکرار کنید...سر آخر مجموع هر مسیر در برگ ها قرار گرفته و بین برگ ها باید بزرگترین رو پیدا کنیم...بخش اول این کار n بیشتر طول نمی کشه چون nا گره بیشتر نداریم و هر بار بین هر دو گره یه جمع داریم...بخش دوم کارم که پیدا کردن بزرگترین کلیده ..
dfs بزن با هر پایین رفتن مقدار گره جدید رو به sum اضافه و با هر بازگشتی کم در گره های برگ هم max رو چک کن
حتی اگه نامتوازن بود باز همون گزینه ی ۲ میشد
برگ ها رو یک بار ملاقات n/2+ و گره ها رو حداکثر دو بار n/2*2=n پس گزینه ی ۲
فکر کنم اینجوری بشه حلش کرد
پیمایش postorder انجام می دیم روی درخت
در پس ترتیب ==> فرزند چپ - فرزند راست و بعد ریشه ملاقات میشه
هر بار موقع ملاقات یک گره، مقدار فرزندان چپ و راستش رو مقایسه می کنیم و اونی که بیشتره رو به مقدارش(پدر) اضافه می کنیم
یعنی: مقدار پدر = ماکس مقدار فرزندانش + مقدار اولیه اش
اینجوری در نهایت وقتی پیمایش تموم بشه و به ریشه برسیم، هر گره دارای طول بزرگترین زیر مسیر از خودش به برگهاست تا اینجا [tex]O(n)[/tex]
حالا طولانی ترین مسیر میشه :
طولانی ترین مسیر در زیر درخت راست ریشه + ریشه + طولانی ترین مسیر در زیر درخت چپ ریشه
که میشه در زمان [tex]O(logn)[/tex] دوتا زیر مسیر چپ و راست رو بدست آورد
پس در نهایت مرتبه زمانی میشه [tex]O(n)[/tex]
(۰۸ بهمن ۱۳۹۲ ۱۰:۲۹ ق.ظ)izadan11 نوشته شده توسط: dfs بزن با هر پایین رفتن مقدار گره جدید رو به sum اضافه و با هر بازگشتی کم در گره های برگ هم max رو چک کن
حتی اگه نامتوازن بود باز همون گزینه ی ۲ میشد
برگ ها رو یک بار ملاقات n/2+ و گره ها رو حداکثر دو بار n/2*2=n پس گزینه ی ۲
منظورش از ریشه به برگ هست یا مثلا از برگ سمت چپ به برگ سمت راست هم میشه؟ اصولا این متوازن بودن چه کمیکی میکنه تا مثلا روی درخت معمولی میزدیم.؟
(۱۰ بهمن ۱۳۹۲ ۰۴:۴۸ ب.ظ)Riemann نوشته شده توسط: منظورش از ریشه به برگ هست یا مثلا از برگ سمت چپ به برگ سمت راست هم میشه؟ اصولا این متوازن بودن چه کمیکی میکنه تا مثلا روی درخت معمولی میزدیم.؟
به نظرم کل مسیرها رو باید در نظر بگیریم ، چون نگفته مسیر از ریشه به برگ
کمکی نمی کنه! چون جواب بهینه [tex]O(n)[/tex] بدست میآد برامون فرقی نداره عمق n باشه یا log n
(۱۰ بهمن ۱۳۹۲ ۰۵:۵۶ ب.ظ)farhangian نوشته شده توسط: طولانی ترین مسیر مسیریه که از سمت چپ ترین عنصر درخت شروع بشه و به سمت راست ترین عنصر ختم بشه.
بر چه اساسی؟؟
حتی اگر بدون توجه به صورت سوال ، درخت رو AVL فرض کنیم هم این جمله صادق نیست !
(۱۰ بهمن ۱۳۹۲ ۰۴:۴۸ ب.ظ)Riemann نوشته شده توسط:(08 بهمن ۱۳۹۲ ۱۰:۲۹ ق.ظ)izadan11 نوشته شده توسط: dfs بزن با هر پایین رفتن مقدار گره جدید رو به sum اضافه و با هر بازگشتی کم در گره های برگ هم max رو چک کن
حتی اگه نامتوازن بود باز همون گزینه ی ۲ میشد
برگ ها رو یک بار ملاقات n/2+ و گره ها رو حداکثر دو بار n/2*2=n پس گزینه ی ۲
منظورش از ریشه به برگ هست یا مثلا از برگ سمت چپ به برگ سمت راست هم میشه؟ اصولا این متوازن بودن چه کمیکی میکنه تا مثلا روی درخت معمولی میزدیم.؟
طولانی ترین اگه قرار باشه از برگ به برگ حساب کنیم از چپ ترین به راست ترین گره نیست ممکنه از هر برگی به یه برگ دیگه باشه که ما تو dfs ماکس چپ رو با ماکس راست جمع می کنیم و با ماکس تا الان مقایسه می کنیم
متوازن بودن اصلا ملاک نیست
این که خیلی راحته. از ریشه شروع میکنیم و وزن مسیر هر گره رو حساب میکنیم تا به برگها برسیم. چون همه گره ها بررسی میشن میشه ۲
Sent from my SM-T210R using Tapatalk
(۱۰ بهمن ۱۳۹۲ ۱۰:۰۴ ب.ظ)hoomanab نوشته شده توسط: این که خیلی راحته. از ریشه شروع میکنیم و وزن مسیر هر گره رو حساب میکنیم تا به برگها برسیم. چون همه گره ها بررسی میشن میشه ۲
Sent from my SM-T210R using Tapatalk
اگه منظورتون برگ هست.
هر مسیر گره، حداکثر lgn تا گره توی مسیرش داره و این که شما میشگی مشه یه چیزی تو مایه lgn x lgn میشه فکر کنم .
نه منظورم اینه باید n تا گره پیمایش شن تا اندازه مسیر هر کدوم به دست بیاد
Sent from my SM-T210R using Tapatalk