سلام همون رابطه ای میشه که دوستمون نوشته.عدد کاتالان میشه

(۰۶ شهریور ۱۳۹۳ ۰۸:۰۵ ب.ظ)!!! نوشته شده توسط:  سلام

دوستان لطفا راهنمایی کنید، تعداد درختان دودویی با n گره (((با ارتفاع h))) چقدره؟

سلام دوست عزیز

تعدادشون برابر $\binom{2n}{n}/(n 1)$ هست

(۰۶ شهریور ۱۳۹۳ ۰۸:۰۵ ب.ظ)!!! نوشته شده توسط:  سلام

دوستان لطفا راهنمایی کنید، تعداد درختان دودویی با n گره (((با ارتفاع h))) چقدره؟

عدد کاتالان نمیشه!

(۰۷ شهریور ۱۳۹۳ ۱۱:۵۱ ق.ظ)Riemann نوشته شده توسط:  

(06 شهریور ۱۳۹۳ ۰۸:۰۵ ب.ظ)!!! نوشته شده توسط:  سلام

دوستان لطفا راهنمایی کنید، تعداد درختان دودویی با n گره (((با ارتفاع h))) چقدره؟

عدد کاتالان نمیشه!

سلام.دوست عزیز با n کلید متمایز میتونیم $\frac{1}{n 1}(^{2n}_n)$ درخت جست و جوی دودویی بسازیم که همون عدد کاتالان هستش

سلام

دوستان کاتالان تعداد کل درخت های دودویی با N کلید رو نشون میده که حالا ارتفاع درش مهم نیست.

اتفاقا خودم به جوابش رسیدم (البته همین الان)

تعداد درخت های دودویی با n گره و با ارتفاع h:
تعداد انتخاب های گره های سطح آخر از تعداد کل گره هایی که میتونه در سطح آخر باشه. پس داریم:
واسه بدست آوردن گره هایی که در سطح h ام استاول کل گره های سطوح ۱ تا h-1 رو بدست میاریم بعد از کل گره ها n کم می کنیم:
$x=n-(2^{h-1}-1)$

حالا ترکیب این مقدار از تعداد کل گره هایی که میتونه در سطح آخر باشه:
$\binom{2^{h-1}}{x}$

دوستان اگه ایده دیگه ای به ذهنتون رسید یا اگه پیشنهادی دارید بگید لطفا.

(۰۷ شهریور ۱۳۹۳ ۱۲:۱۱ ب.ظ)!!! نوشته شده توسط:  سلام

دوستان کاتالان تعداد کل درخت های دودویی با N کلید رو نشون میده که حالا ارتفاع درش مهم نیست.

اتفاقا خودم به جوابش رسیدم (البته همین الان)

تعداد درخت های دودویی با n گره و با ارتفاع h:
تعداد انتخاب های گره های سطح آخر از تعداد کل گره هایی که میتونه در سطح آخر باشه. پس داریم:
واسه بدست آوردن گره هایی که در سطح h ام استاول کل گره های سطوح ۱ تا h-1 رو بدست میاریم بعد از کل گره ها n کم می کنیم:
$x=n-(2^{h-1}-1)$

حالا ترکیب این مقدار از تعداد کل گره هایی که میتونه در سطح آخر باشه:
$\binom{2^{h-1}}{x}$

دوستان اگه ایده دیگه ای به ذهنتون رسید یا اگه پیشنهادی دارید بگید لطفا.

بله درست میگید عدد کاتالان ارتفاع رو در نظر نمیگیره.من حواسم به این نبود که ارتفاع رو هم میخواد.توی این رابطه ای که نوشتید میشه بگید برای ۳ کلید متمایز به ارتفاع ۲ چند درخت دودویی به دست میاره؟

(۰۷ شهریور ۱۳۹۳ ۱۲:۳۷ ب.ظ)miladcr7 نوشته شده توسط:  بله درست میگید عدد کاتالان ارتفاع رو در نظر نمیگیره.من حواسم به این نبود که ارتفاع رو هم میخواد.توی این رابطه ای که نوشتید میشه بگید برای ۳ کلید متمایز به ارتفاع ۲ چند درخت دودویی به دست میاره؟

ببخشید این فرمولی که با کلی تفکر بدست آوردم ماله درخت جستجوی دودویی است.

حالا فکر کنم برای درخت دودویی هم به این صورت میشه بدست آورد.

تو این فرمول تعداد درخت های جستجوی دودویی رو بدست آوردیم. یعنی تعداد کل درخت هایی که میشه با ارتفاع h و با n گره داشت.

حالا به ازای هر یک از این درخت ها می تونیم به n! این n مقدار را درون کلیدها جا بدیم.

در نتیجه تعداد درخت های دودویی با n گره و ارتفاع h میشه:
تعداد درخت های جستجوی دودویی با n گره و ارتفاع h * n!

یکم زیادی پیچیده شد، نظرتون چیه؟

(۰۷ شهریور ۱۳۹۳ ۰۱:۱۱ ب.ظ)!!! نوشته شده توسط:  

(07 شهریور ۱۳۹۳ ۱۲:۳۷ ب.ظ)miladcr7 نوشته شده توسط:  بله درست میگید عدد کاتالان ارتفاع رو در نظر نمیگیره.من حواسم به این نبود که ارتفاع رو هم میخواد.توی این رابطه ای که نوشتید میشه بگید برای ۳ کلید متمایز به ارتفاع ۲ چند درخت دودویی به دست میاره؟

ببخشید این فرمولی که با کلی تفکر بدست آوردم ماله درخت جستجوی دودویی است.

حالا فکر کنم برای درخت دودویی هم به این صورت میشه بدست آورد.

تو این فرمول تعداد درخت های جستجوی دودویی رو بدست آوردیم. یعنی تعداد کل درخت هایی که میشه با ارتفاع h و با n گره داشت.

حالا به ازای هر یک از این درخت ها می تونیم به n! این n مقدار را درون کلیدها جا بدیم.

در نتیجه تعداد درخت های دودویی با n گره و ارتفاع h میشه:
تعداد درخت های جستجوی دودویی با n گره و ارتفاع h * n!

یکم زیادی پیچیده شد، نظرتون چیه؟

ببخشید منظور من هم همون درخت جست و جوی دودویی بودش.حالا توی این رابطه ای که نوشتید میشه بگید برای ۳ کلید متمایز به ارتفاع ۲ چند درخت جست و جوی دودویی به دست میاره؟

(۰۷ شهریور ۱۳۹۳ ۰۱:۴۸ ب.ظ)miladcr7 نوشته شده توسط:  ببخشید منظور من هم همون درخت جست و جوی دودویی بودش.حالا توی این رابطه ای که نوشتید میشه بگید برای ۳ کلید متمایز به ارتفاع ۲ چند درخت جست و جوی دودویی به دست میاره؟

آها، با سه کلید متمایز به ارتفاع ۲ میتونیم ۱ نوع BST داشته باشیم.

تو فرمول هم اگه بخواییم جایگذاری کنیم میشه:
$\binom{2^{h-1}}{n-(2^{h-1}-1)}=\binom{2^{2-1}}{3-(2^{2-1}-1)}=\binom{2^1}{3-(2^1-1)}=\binom{2}{3-1}=\binom{2}{2}=\frac{2!}{2!(2-2)!}=\frac{2!}{2!0!}=1$

(۰۷ شهریور ۱۳۹۳ ۰۱:۵۲ ب.ظ)!!! نوشته شده توسط:  

(07 شهریور ۱۳۹۳ ۰۱:۴۸ ب.ظ)miladcr7 نوشته شده توسط:  ببخشید منظور من هم همون درخت جست و جوی دودویی بودش.حالا توی این رابطه ای که نوشتید میشه بگید برای ۳ کلید متمایز به ارتفاع ۲ چند درخت جست و جوی دودویی به دست میاره؟

آها، با سه کلید متمایز به ارتفاع ۲ میتونیم ۱ نوع BST داشته باشیم.

تو فرمول هم اگه بخواییم جایگذاری کنیم میشه:
$\binom{2^{h-1}}{n-(2^{h-1}-1)}=\binom{2^{2-1}}{3-(2^{2-1}-1)}=\binom{2^1}{3-(2^1-1)}=\binom{2}{3-1}=\binom{2}{2}=\frac{2!}{2!(2-2)!}=\frac{2!}{2!0!}=1$

خب به نظرتون با ۳ کلید متمایز تعداد درخت های جستجوی دودویی به ارتفاع ۲ برابر ۴ تا نیستش؟

(۰۷ شهریور ۱۳۹۳ ۰۲:۰۱ ب.ظ)miladcr7 نوشته شده توسط:  خب به نظرتون با ۳ کلید متمایز تعداد درخت های جستجوی دودویی به ارتفاع ۲ برابر ۴ تا نیستش؟

متوجه نمیشم، خب ۱۴،۲۰،۱۰۰ سه کلید متمایز هستند، میشه لطفا بگید چجوری میشه ۴ تا درخت متمایز (به ارتفاع ۲) داشت؟

(۰۷ شهریور ۱۳۹۳ ۰۲:۰۵ ب.ظ)!!! نوشته شده توسط:  

(07 شهریور ۱۳۹۳ ۰۲:۰۱ ب.ظ)miladcr7 نوشته شده توسط:  خب به نظرتون با ۳ کلید متمایز تعداد درخت های جستجوی دودویی به ارتفاع ۲ برابر ۴ تا نیستش؟

متوجه نمیشم، خب ۱۴،۲۰،۱۰۰ سه کلید متمایز هستند، میشه لطفا بگید چجوری میشه ۴ تا درخت متمایز (به ارتفاع ۲) داشت؟

یه بار ۱۴ رو ریشه فرض کنید یه بار هم ۱۰۰ رو ریشه فرض کنید

(۰۷ شهریور ۱۳۹۳ ۰۲:۱۴ ب.ظ)miladcr7 نوشته شده توسط:  یه بار ۱۴ رو ریشه فرض کنید یه بار هم ۱۰۰ رو ریشه فرض کنید

اونموقع میشه به ارتفاع ۳، فکر کنم شما ریشه رو ۰ فرض کردین. درسته!؟

و یه چیز دیگه، اون فرمولی که نوشته بودم مربوط به تعداد درخت دودویی با n گره و با ارتفاع h بود نه درخت جستجوی دودویی. من یکم آره (بدون توجه به کلیدها) چون در مسائل بویژه عدد کاتالان، مقادیر کلیدها مد نظر نیست و فقط تعداد اشکال (درخت دودویی با n گره) مد نظر است که حالا اگه بگه با n گره و با ارتفاع h (به ارتفاع هم محدود بشه مسئله) اون موقع این فرمول جواب میده.

ویرایش: در فرمول بالا ریشه رو یک گرفته ام.

(۰۷ شهریور ۱۳۹۳ ۰۲:۲۵ ب.ظ)!!! نوشته شده توسط:  

(07 شهریور ۱۳۹۳ ۰۲:۱۴ ب.ظ)miladcr7 نوشته شده توسط:  یه بار ۱۴ رو ریشه فرض کنید یه بار هم ۱۰۰ رو ریشه فرض کنید

اونموقع میشه به ارتفاع ۳، فکر کنم شما ریشه رو ۰ فرض کردین. درسته!؟

و یه چیز دیگه، اون فرمولی که نوشته بودم مربوط به تعداد درخت دودویی با n گره و با ارتفاع h بود نه درخت جستجوی دودویی. من یکم آره (بدون توجه به کلیدها) چون در مسائل بویژه عدد کاتالان، مقادیر کلیدها مد نظر نیست و فقط تعداد اشکال (درخت دودویی با n گره) مد نظر است که حالا اگه بگه با n گره و با ارتفاع h (به ارتفاع هم محدود بشه مسئله) اون موقع این فرمول جواب میده.

ویرایش: در فرمول بالا ریشه رو یک گرفته ام.

خب ریشه که ارتفاعش صفره.چجوری یک گرفتین؟
در ضمن با این شرایط که شما در نظر گرفتی اگه برای ۳کلید متمایز به ارتفاع ۳ بخوایم تعداد درخت جستجوی دودویی رو به دست بیاریم جوابتون ترکیب ۰ از ۴ میشه که برابر ۱ هستش

(۰۷ شهریور ۱۳۹۳ ۰۲:۲۹ ب.ظ)miladcr7 نوشته شده توسط:  خب ریشه که ارتفاعش صفره.چجوری یک گرفتین؟
در ضمن با این شرایط که شما در نظر گرفتی اگه برای ۳کلید متمایز به ارتفاع ۳ بخوایم تعداد درخت جستجوی دودویی رو به دست بیاریم جوابتون ترکیب ۰ از ۴ میشه که برابر ۱ هستش

درسته، مشکل یه چیز خیلی بی ارزشه ..

تو ساختمان داده معمولا هم میشه ریشه رو صفر گرفت و هم یک. من هم حتی تو همون فرمول پایه ریشه رو یک گرفته ام و کلا بحث هام با ریشه ۱ بوده. خب شما هم کلا از دید اینکه ریشه تو سطح صفر هست نگاه کردین. اما در کل مشکل خاصی نیست.

پیشنهاد می کنم شما ریشه رو ۱ فرض کنید. بعد فرمول $\binom{2^{h-1}}{n-(2^{h-1}-1)}$ رو برای n گره با ارتفاع h در نظر بگیرید. دقیقا تعداد درختهای دودویی با ارتفاع h و تعداد n گره رو نتیجه خواهد داد.

اگه مشکلی هست بگید لطفا.

حالا اگر هم خواستید ریشه رو صفر بگیرید از این فرمول استفاده کنید:
$\binom{2^h}{n-(2^h-1)}$

(۰۷ شهریور ۱۳۹۳ ۰۲:۴۶ ب.ظ)!!! نوشته شده توسط:  

(07 شهریور ۱۳۹۳ ۰۲:۲۹ ب.ظ)miladcr7 نوشته شده توسط:  خب ریشه که ارتفاعش صفره.چجوری یک گرفتین؟
در ضمن با این شرایط که شما در نظر گرفتی اگه برای ۳کلید متمایز به ارتفاع ۳ بخوایم تعداد درخت جستجوی دودویی رو به دست بیاریم جوابتون ترکیب ۰ از ۴ میشه که برابر ۱ هستش

درسته، مشکل یه چیز خیلی بی ارزشه ..

تو ساختمان داده معمولا هم میشه ریشه رو صفر گرفت و هم یک. من هم حتی تو همون فرمول پایه ریشه رو یک گرفته ام و کلا بحث هام با ریشه ۱ بوده. خب شما هم کلا از دید اینکه ریشه تو سطح صفر هست نگاه کردین. اما در کل مشکل خاصی نیست.

پیشنهاد می کنم شما ریشه رو ۱ فرض کنید. بعد فرمول $\binom{2^{h-1}}{n-(2^{h-1}-1)}$ رو برای n گره با ارتفاع h در نظر بگیرید. دقیقا تعداد درختهای دودویی با ارتفاع h و تعداد n گره رو نتیجه خواهد داد.

اگه مشکلی هست بگید لطفا.

حالا اگر هم خواستید ریشه رو صفر بگیرید از این فرمول استفاده کنید:
$\binom{2^h}{n-(2^h-1)}$

بله میدونم ریشه رو هم ۱ میگیرن.ولی برای کنکور میگن صفر در نظر بگیرید.در ضمن فرمول هاتون هم فکر کنم جابجا هستن.توی فرمول دومی برای ۳ نود با ارتفاع ۲ میشه ترکیب ۰ از ۴ که میشه ۱در صورتی که باید ۴ بده

(۰۷ شهریور ۱۳۹۳ ۰۳:۰۸ ب.ظ)miladcr7 نوشته شده توسط:  بله میدونم ریشه رو هم ۱ میگیرن.ولی برای کنکور میگن صفر در نظر بگیرید.در ضمن فرمول هاتون هم فکر کنم جابجا هستن.توی فرمول دومی برای ۳ نود با ارتفاع ۲ میشه ترکیب ۰ از ۴ که میشه ۱در صورتی که باید ۴ بده

آفرین! حق دارید. فرمول جابجا نیست. این یه اشکال فرموله. البته نه اینکه مشکلی باشه. می تونیم از این فرمول فقط برای درخت های کامل یا پر استفاده کنیم.

پس بهتره به این صورت تصحیح کنیم:

تعداد درخت های دودویی کامل یا پر با n گره و ارتفاع h:
$\binom{2^{h-1}}{n-(2^{h-1}-1)}$

حالا مونده این که یه فرمول کلی پیدا کنیم. من هر موقع وقت کردم حتما روش کار می کنم. شما هم لطفا اگه پیدا کردید اینجا هم بنویسید تا ما هم استفاده کنیم.

راستش من فروم های خارجی رو هم گشتم (قبلا) دنبال این مسئله. ولی نبود. حالا این یه قدم عالی به سوی پیشرفته حالا یه فرمول جامع تر ... نمی دونم .
منتظزتونم ..
مرسی.

بازم سلام
در رابطه با تعداد درخت های دودویی کامل از این روابط استفاده کنیم راحت تره
اگه سطح رو x و ارتفاع رو h در نظر بگیریم
قبول دارید که :$x=h 1$

حالا با فرض اینکه حتی ارتفاع رو هم نداشته باشیم، تعداد سطح درخت دودویی با داشتن n گره میشه:$\lfloor\lg n\rfloor 1$

و تعداد درخت دودویی کامل با x سطح برابر:$2^{x-1}$ هستش

برای اونم یه فکری میکنیم

(۰۷ شهریور ۱۳۹۳ ۰۵:۰۲ ب.ظ)miladcr7 نوشته شده توسط:  بازم سلام
در رابطه با تعداد درخت های دودویی کامل از این روابط استفاده کنیم راحت تره
اگه سطح رو x و ارتفاع رو h در نظر بگیریم
قبول دارید که :$x=h 1$

حالا با فرض اینکه حتی ارتفاع رو هم نداشته باشیم، تعداد سطح درخت دودویی با داشتن n گره میشه:$\lfloor\lg n\rfloor 1$

و تعداد درخت دودویی کامل با x سطح برابر:$2^{x-1}$ هستش

برای اونم یه فکری میکنیم

ببخشید من دقیقا متوجه نشدم این فرمولی که گفتین با مسئله ما چه رتبطی داره. لطفا بیشتر توضیح بدید.

۱) منظورتون از سطح=ارتفاع+۱ چیه؟ دیدگاه شما از واژه های سطح و ارتفاع چیه؟ لطفا توضیح بدید.

۲) سوال اصلی این تاپیک این بود که "تعداد درختهای دودویی با n گره و با ارتفاع h".

--- در کتاب در مورد تعداد درختهای دودویی با n گره بحث شده بود که همان عدد کاتالان میشه.
--- در این تاپیک این مسئله را به سطح h محدود کردیم. یعنی گفتیم با n گره چند درخت دودویی می تونیم بسازیم به شرطی که ارتفاع همه آنها دقیقا h باشه.
--- خب منم اومدم یه فرمولی گفتم که دقیقا برای درخت های دودویی کامل یا پر جواب میده (حالا شاید هم مشکل داره. اما تا حالا که مشکلی نداره). یعنی اومدیم گفتیم اگه درخت رو کامل یا پر در نظر بگیریم. با n گره می تونیم دقیقا همان فرمول قدر درخت دودویی می تونیم داشته باشیم به شرطی که دقیقا ارتفاع هر درخت h باشه.


حالا دو سوال در مباحث بالا بوجود اومد:
۱- آیا ایده بهتری دارید نسبت به فرمولی که نوشتم: یعنی تعداد درخت هایی دودویی کامل یا پر با n گره محدود شده به دقیقا ارتفاع h
۲- و سوال مهم تر اینکه یه فرمول کلی تر می تونیم بنویسیم که محدودیت کامل یا پر بودن رو بتونیم برداریم؟

الان من دقیقا متوجه نشدم که پاسخ شما به کدام دسته مربوط میشه.

بازم مرسی.

+++ فرمولی که نوشتین کمی منحرف شده. داده های ورودی ما همانطور که در عنوان تاپیک هم میبینید n تعداد گره ها و h ارتفاع است و سوالم هم که معلومه. تعداد درخت های دودویی با n گره محدود شده به دقیقا ارتفاع h.

مرسی.