(۱۹ آذر ۱۳۹۱ ۰۳:۰۴ ق.ظ)azad_ahmadi نوشته شده توسط:  برای حل این سوالی که شما فرمودین، (اینکه i رو زیر درخت سمت راست در نظر بگیریم و بخوایم متناظرش رو در زیر درخت سمت چپ پیدا کنیم) کافیه که علامت به علاوه رو به منها تبدیل کرد. در این صورت متناظر j در زیر درخت چپ بدست می آید.
i-2^log i -1 . (حدپایین لگاریتم در نظر گرفته شود و همچنین -۱ در خارج از حد پایین قرار دارد).
مثلا برای گره ۳۱، که متناظرش گره ۲۳ هست که با جایگذاری در فرمول بالا جواب بدست می آید.
یا مثلا برای گره ۱۴، گره ۱۰ متناظرش است که درست خواهد بود.
(فرمول در کتاب یا جایی نیومده، لااقل من ندیدم، اما ساده ست و با آزمون و خطا بدست میاد).
موفق باشید.

ممنون کامل بود موفق باشید

سلام.
سوال به ظاهر سوال پیچیده ای میاد اما سوال راحت و نکته داری هست.
مبحث درخت در کتاب پوران درختی رو توضیح داده به اسم Deap . مقدار ریشه این درخت خالی است، زیر درخت چپ ریشه minheap و زیر درخت راست ریشه maxheap است. هر نود i در زیر درخت چپ باید مقدارش از نود متناظرش در زیر درخت راست کوچیکتر باشد.
حالا این سوال شما همون پیدا کردن متناظر i در زیر درخت سمت راست هست. فرمولی که بکار برده شده برابر هست با:
i + 2 ^ log i -1 .
دقت کن که logi درون حدپایین قرار گرفته و -۱ بیرون از حد پایین هست. (حد پایین یعنی log9 برابر هست با ۳ و نه ۴).
حالا اگه بجای i مقدار ۱۰۳۰ رو قرار بدیم، جواب میشه ۹^۲ + ۱۰۳۰ که برابر هست با ۱۵۴۲ .

متناظر ریشه وجود نداره، پس هیچوقت متناظر ریشه رو نمی خواد.
موفق باشید.

(۱۹ آذر ۱۳۹۱ ۰۱:۲۰ ق.ظ)azad_ahmadi نوشته شده توسط:  سلام.
سوال به ظاهر سوال پیچیده ای میاد اما سوال راحت و نکته داری هست.
مبحث درخت در کتاب پوران درختی رو توضیح داده به اسم Deap . مقدار ریشه این درخت خالی است، زیر درخت چپ ریشه minheap و زیر درخت راست ریشه maxheap است. هر نود i در زیر درخت چپ باید مقدارش از نود متناظرش در زیر درخت راست کوچیکتر باشد.
حالا این سوال شما همون پیدا کردن متناظر i در زیر درخت سمت راست هست. فرمولی که بکار برده شده برابر هست با:
i + 2 ^ log i -1 .
دقت کن که logi درون حدپایین قرار گرفته و -۱ بیرون از حد پایین هست. (حد پایین یعنی log9 برابر هست با ۳ و نه ۴).
حالا اگه بجای i مقدار ۱۰۳۰ رو قرار بدیم، جواب میشه ۹^۲ + ۱۰۳۰ که برابر هست با ۱۵۴۲ .

متناظر ریشه وجود نداره، پس هیچوقت متناظر ریشه رو نمی خواد.
موفق باشید.

ممنون ، ولی منظورم اینکه تو پاسخنامه زده برای زیر درخت چپ از ریشه با این روش حل میشه ، حالا اگه ما برای زیر درخت راست رو

بخواهیم چطوری باید حلش کنیم؟

ممنون ازشما

این سوال تست کنکور علوم کامپیوتر ۸۵ بوده البته فرمول مربوط به این سوال نه صورت سوال پارسه.
یه حالت دیگه هم هست که اگه گره متناظرش وجود نداشته باشه یا به عبارتی مقدار i + 2 ^ log i -1 از حداکثر تعداد گره بیشتر بشه باید با پدر گره ای که وجود نداره مقایسه بشه.
یعنی با
۲/ i + 2 ^ log i -1

(۱۹ آذر ۱۳۹۱ ۰۱:۱۶ ب.ظ)m_sardaari نوشته شده توسط:  این سوال تست کنکور علوم کامپیوتر ۸۵ بوده البته فرمول مربوط به این سوال نه صورت سوال پارسه.
یه حالت دیگه هم هست که اگه گره متناظرش وجود نداشته باشه یا به عبارتی مقدار i + 2 ^ log i -1 از حداکثر تعداد گره بیشتر بشه باید با پدر گره ای که وجود نداره مقایسه بشه.
یعنی با
۲/ i + 2 ^ log i -1

ممنون از پاسختون
اینجا تو سوال چی رو میخاد الان؟

اینجا گره متناظر در زیر درخت راست رو میخواد.که از این فرمول حساب میشه i + 2 ^( log i) -1
واینکه از کجا بدونیم گره متناظر تو زیر درخت چپ یا راست رو میخواد باید حساب کنیم گره مثلا ۱۰۳۰ تو زیر درخت چپ قرار داره یا راست که با توجه به کامل بودن درخت محاسبه ش کاری نداره.
ولی اگه گفت در deap درصورت عدم وجود گره متناظر باید با کدام گره مقایسه بشه باید با این فرمول حساب بشه
۲/ i + 2 ^ log i -1
این که میگم مقایسه یعنی در deap باید هر گره در زیر درخت چپ ریشه کوچکتر مساوی گره متانظرش در زیر درخت راست ریشه باشه.و با فرمول قبل عنصر متناظر رو بدست میاریم.
اگه تعریف deap رو بخونین تمام اینا براتون بدیهی میشه.
فقط این نکته رو توجه کنین درخت باید کامل باشه.که هیپ و دیپ این خصوصیت رو دارن.