با عرض سلام خدمت تمامی اساتید گرام
دوستان گرامی این فرمول شدید ابهام در بنده ایجاد کرده
ممنون میشوم لطف بفرمایید و توضیح دهید ..
در کتاب CLRS آمده که در هر هیپ با N عنصر حداکثر (N / 2^(h+1 گره با ارتفاع h وجود دارد ؛
به ازای n=12 و برای ارتفاع ۱ برای این فرمول مقدار ۳ بدست می آید حال اگر ارتفاع را از ریشه حساب کنیم در ارتفاع ۱ که مشخصا حداکثر ۲ گره وجود دارد ولی اگر مانند CLRS ارتفاع را از برگ ها به سمت بالا حساب کنیم در ارتفاع ۱ از سطح برگ ها یا به عبارتی سطح یکی مانده به آخر حداکثر ۴ گره وجود دارد .
دوستان من که حسابی گیج شدم ممنون میشم کسی من را درباره این فرمول راهنمایی کند...
(۰۵ دى ۱۳۹۲ ۰۴:۲۲ ب.ظ)zerocool_ir نوشته شده توسط: با عرض سلام خدمت تمامی اساتید گرام
دوستان گرامی این فرمول شدید ابهام در بنده ایجاد کرده
ممنون میشوم لطف بفرمایید و توضیح دهید ..
در کتاب CLRS آمده که در هر هیپ با N عنصر حداکثر (N / 2^(h+1 گره با ارتفاع h وجود دارد ؛
به ازای n=12 و برای ارتفاع ۱ برای این فرمول مقدار ۳ بدست می آید حال اگر ارتفاع را از ریشه حساب کنیم در ارتفاع ۱ که مشخصا حداکثر ۲ گره وجود دارد ولی اگر مانند CLRS ارتفاع را از برگ ها به سمت بالا حساب کنیم در ارتفاع ۱ از سطح برگ ها یا به عبارتی سطح یکی مانده به آخر حداکثر ۴ گره وجود دارد .
دوستان من که حسابی گیج شدم ممنون میشم کسی من را درباره این فرمول راهنمایی کند...
این چیزی که تو کتاب CLRS اومده کاملا درسته. شما وقتی درخت هیپی با ۱۲ گره رسم کنی تعداد گره‌های با ارتفاع ۱ میشه ۳ تا که با فرمول CLRS مطابقت داره. گره‌ی چهارم سطح یکی مونده به آخر ارتفاعش صفره نه یک.
(۰۶ دى ۱۳۹۲ ۱۲:۲۱ ق.ظ)mfXpert نوشته شده توسط:(05 دى ۱۳۹۲ ۰۴:۲۲ ب.ظ)zerocool_ir نوشته شده توسط: با عرض سلام خدمت تمامی اساتید گرام
دوستان گرامی این فرمول شدید ابهام در بنده ایجاد کرده
ممنون میشوم لطف بفرمایید و توضیح دهید ..
در کتاب CLRS آمده که در هر هیپ با N عنصر حداکثر (N / 2^(h+1 گره با ارتفاع h وجود دارد ؛
به ازای n=12 و برای ارتفاع ۱ برای این فرمول مقدار ۳ بدست می آید حال اگر ارتفاع را از ریشه حساب کنیم در ارتفاع ۱ که مشخصا حداکثر ۲ گره وجود دارد ولی اگر مانند CLRS ارتفاع را از برگ ها به سمت بالا حساب کنیم در ارتفاع ۱ از سطح برگ ها یا به عبارتی سطح یکی مانده به آخر حداکثر ۴ گره وجود دارد .
دوستان من که حسابی گیج شدم ممنون میشم کسی من را درباره این فرمول راهنمایی کند...
این چیزی که تو کتاب CLRS اومده کاملا درسته. شما وقتی درخت هیپی با ۱۲ گره رسم کنی تعداد گره‌های با ارتفاع ۱ میشه ۳ تا که با فرمول CLRS مطابقت داره. گره‌ی چهارم سطح یکی مونده به آخر ارتفاعش صفره نه یک.
خب برای n=12 درست در می آید ولی برای n=13 باز هم گره ی چهارم سطح یکی مونده به آخر که ارتفاعش صفر هست ولی از آنجایی که این فرمول در حد بالا قرار می گیرید تعداد گره های با ارتفاع ۱ میشه ۴ تا !!!
(۰۵ دى ۱۳۹۲ ۰۴:۲۲ ب.ظ)zerocool_ir نوشته شده توسط: با عرض سلام خدمت تمامی اساتید گرام
دوستان گرامی این فرمول شدید ابهام در بنده ایجاد کرده
ممنون میشوم لطف بفرمایید و توضیح دهید ..
در کتاب CLRS آمده که در هر هیپ با N عنصر حداکثر (N / 2^(h+1 گره با ارتفاع h وجود دارد ؛
به ازای n=12 و برای ارتفاع ۱ برای این فرمول مقدار ۳ بدست می آید حال اگر ارتفاع را از ریشه حساب کنیم در ارتفاع ۱ که مشخصا حداکثر ۲ گره وجود دارد ولی اگر مانند CLRS ارتفاع را از برگ ها به سمت بالا حساب کنیم در ارتفاع ۱ از سطح برگ ها یا به عبارتی سطح یکی مانده به آخر حداکثر ۴ گره وجود دارد .
دوستان من که حسابی گیج شدم ممنون میشم کسی من را درباره این فرمول راهنمایی کند...
فرمول درسته
برای n=13وقتی آخرین گره سطح یکی مونده به آخر، هیچ فرزندی نداره در عمل ارتفاعش صفره و وباعث میشه که پدرش ارتفاع یک بشه و ارتفاع ریشه از این نود ۲باشه.
نکته اینجاست که شما ارتفاع رو به عنوان ارتفاع کل درخت در نظر میگیرید.در صورتی که هر نود ارتفاع خاص خودشو داره.تو تعریف درخت طولانی ترین مسیر از ریشه به برگ میشه ارتفاعه اما ممکنه ارتفاعات متفاوتی هم باشه ولی بزرگترینش میشه ارتفاع درخت.
تو این فرمول منظور از ارتفاع مثلا ۲ یعنی نودهایی که از برگ ۲ نود فاصله دارن، ممکنه سطحشون نابرابر باشه.
موفق باشید
(۱۲ دى ۱۳۹۲ ۱۰:۳۰ ب.ظ)zerocool_ir نوشته شده توسط: خب برای n=12 درست در می آید ولی برای n=13 باز هم گره ی چهارم سطح یکی مونده به آخر که ارتفاعش صفر هست ولی از آنجایی که این فرمول در حد بالا قرار می گیرید تعداد گره های با ارتفاع ۱ میشه ۴ تا !!!ببینید این فرمول داره میگه حداکثر برابر با ۴ میشه. حالا اگر شما برای درختی با n=13 گره تعداد گره‌های با ارتفاع h=1 رو بشمارید می‌بینید این تعداد برابر با ۳ هست. فرمول هم میگه تعداد گره‌های با ارتفاع h=1 حداکثر برابر با ۴ هستش. خوب ۳ هم که کوچکتر از ۴ هستش و در نتیجه فرمول همچنان درسته!
(۱۲ دى ۱۳۹۲ ۱۱:۴۷ ب.ظ)Fot30 نوشته شده توسط:(05 دى ۱۳۹۲ ۰۴:۲۲ ب.ظ)zerocool_ir نوشته شده توسط: با عرض سلام خدمت تمامی اساتید گرام
دوستان گرامی این فرمول شدید ابهام در بنده ایجاد کرده
ممنون میشوم لطف بفرمایید و توضیح دهید ..
در کتاب CLRS آمده که در هر هیپ با N عنصر حداکثر (N / 2^(h+1 گره با ارتفاع h وجود دارد ؛
به ازای n=12 و برای ارتفاع ۱ برای این فرمول مقدار ۳ بدست می آید حال اگر ارتفاع را از ریشه حساب کنیم در ارتفاع ۱ که مشخصا حداکثر ۲ گره وجود دارد ولی اگر مانند CLRS ارتفاع را از برگ ها به سمت بالا حساب کنیم در ارتفاع ۱ از سطح برگ ها یا به عبارتی سطح یکی مانده به آخر حداکثر ۴ گره وجود دارد .
دوستان من که حسابی گیج شدم ممنون میشم کسی من را درباره این فرمول راهنمایی کند...
فرمول درسته
برای n=13وقتی آخرین گره سطح یکی مونده به آخر، هیچ فرزندی نداره در عمل ارتفاعش صفره و وباعث میشه که پدرش ارتفاع یک بشه و ارتفاع ریشه از این نود ۲باشه.
نکته اینجاست که شما ارتفاع رو به عنوان ارتفاع کل درخت در نظر میگیرید.در صورتی که هر نود ارتفاع خاص خودشو داره.تو تعریف درخت طولانی ترین مسیر از ریشه به برگ میشه ارتفاعه اما ممکنه ارتفاعات متفاوتی هم باشه ولی بزرگترینش میشه ارتفاع درخت.
تو این فرمول منظور از ارتفاع مثلا ۲ یعنی نودهایی که از برگ ۲ نود فاصله دارن، ممکنه سطحشون نابرابر باشه.
موفق باشید
نه من متوجه بودم که ارتفاع هر نود ممکنه با دیگری فرق کند اگر سوال اول من را بخوانید متوجه می شوید ولی سوال من اینه که اینجا برای n=13 طبق این فرمول باید ۴ تا گره ارتفاع ۱ داشته باشیم خب من ۳ تاش رو پیدا کردم ولی اون یکی دیگه شاید خیالی باشد ؟؟