صفحه‌ها: ۱ ۲
سلام
دوستان لطفا راهنمایی کنید، تعداد درختان دودویی با n گره (((با ارتفاع h))) چقدره؟
(۰۶ شهریور ۱۳۹۳ ۰۸:۰۵ ب.ظ)!!! نوشته شده توسط: سلام
دوستان لطفا راهنمایی کنید، تعداد درختان دودویی با n گره (((با ارتفاع h))) چقدره؟
سلام دوست عزیز
تعدادشون برابر [tex]\binom{2n}{n}/(n 1)[/tex] هست
سلام همون رابطه ای میشه که دوستمون نوشته.عدد کاتالان میشه
(۰۶ شهریور ۱۳۹۳ ۰۸:۰۵ ب.ظ)!!! نوشته شده توسط: سلامعدد کاتالان نمیشه!
دوستان لطفا راهنمایی کنید، تعداد درختان دودویی با n گره (((با ارتفاع h))) چقدره؟
(۰۷ شهریور ۱۳۹۳ ۱۱:۵۱ ق.ظ)Riemann نوشته شده توسط:(06 شهریور ۱۳۹۳ ۰۸:۰۵ ب.ظ)!!! نوشته شده توسط: سلامعدد کاتالان نمیشه!
دوستان لطفا راهنمایی کنید، تعداد درختان دودویی با n گره (((با ارتفاع h))) چقدره؟
سلام.دوست عزیز با n کلید متمایز میتونیم [tex]\frac{1}{n 1}(^{2n}_n)[/tex] درخت جست و جوی دودویی بسازیم که همون عدد کاتالان هستش
سلام
دوستان کاتالان تعداد کل درخت های دودویی با N کلید رو نشون میده که حالا ارتفاع درش مهم نیست.
اتفاقا خودم به جوابش رسیدم (البته همین الان)
تعداد درخت های دودویی با n گره و با ارتفاع h:
تعداد انتخاب های گره های سطح آخر از تعداد کل گره هایی که میتونه در سطح آخر باشه. پس داریم:
واسه بدست آوردن گره هایی که در سطح h ام استاول کل گره های سطوح ۱ تا h-1 رو بدست میاریم بعد از کل گره ها n کم می کنیم:
[tex]x=n-(2^{h-1}-1)[/tex]
حالا ترکیب این مقدار از تعداد کل گره هایی که میتونه در سطح آخر باشه:
[tex]\binom{2^{h-1}}{x}[/tex]
دوستان اگه ایده دیگه ای به ذهنتون رسید یا اگه پیشنهادی دارید بگید لطفا.
(۰۷ شهریور ۱۳۹۳ ۱۲:۱۱ ب.ظ)!!! نوشته شده توسط: سلام
دوستان کاتالان تعداد کل درخت های دودویی با N کلید رو نشون میده که حالا ارتفاع درش مهم نیست.
اتفاقا خودم به جوابش رسیدم (البته همین الان)
تعداد درخت های دودویی با n گره و با ارتفاع h:
تعداد انتخاب های گره های سطح آخر از تعداد کل گره هایی که میتونه در سطح آخر باشه. پس داریم:
واسه بدست آوردن گره هایی که در سطح h ام استاول کل گره های سطوح ۱ تا h-1 رو بدست میاریم بعد از کل گره ها n کم می کنیم:
[tex]x=n-(2^{h-1}-1)[/tex]
حالا ترکیب این مقدار از تعداد کل گره هایی که میتونه در سطح آخر باشه:
[tex]\binom{2^{h-1}}{x}[/tex]
دوستان اگه ایده دیگه ای به ذهنتون رسید یا اگه پیشنهادی دارید بگید لطفا.
بله درست میگید عدد کاتالان ارتفاع رو در نظر نمیگیره.من حواسم به این نبود که ارتفاع رو هم میخواد.توی این رابطه ای که نوشتید میشه بگید برای ۳ کلید متمایز به ارتفاع ۲ چند درخت دودویی به دست میاره؟
(۰۷ شهریور ۱۳۹۳ ۱۲:۳۷ ب.ظ)miladcr7 نوشته شده توسط: بله درست میگید عدد کاتالان ارتفاع رو در نظر نمیگیره.من حواسم به این نبود که ارتفاع رو هم میخواد.توی این رابطه ای که نوشتید میشه بگید برای ۳ کلید متمایز به ارتفاع ۲ چند درخت دودویی به دست میاره؟
ببخشید این فرمولی که با کلی تفکر
بدست آوردم ماله درخت جستجوی دودویی است. حالا فکر کنم برای درخت دودویی هم به این صورت میشه بدست آورد.
تو این فرمول تعداد درخت های جستجوی دودویی رو بدست آوردیم. یعنی تعداد کل درخت هایی که میشه با ارتفاع h و با n گره داشت.
حالا به ازای هر یک از این درخت ها می تونیم به n! این n مقدار را درون کلیدها جا بدیم.
در نتیجه تعداد درخت های دودویی با n گره و ارتفاع h میشه:
تعداد درخت های جستجوی دودویی با n گره و ارتفاع h * n!
یکم زیادی پیچیده شد، نظرتون چیه؟
(۰۷ شهریور ۱۳۹۳ ۰۱:۱۱ ب.ظ)!!! نوشته شده توسط:(07 شهریور ۱۳۹۳ ۱۲:۳۷ ب.ظ)miladcr7 نوشته شده توسط: بله درست میگید عدد کاتالان ارتفاع رو در نظر نمیگیره.من حواسم به این نبود که ارتفاع رو هم میخواد.توی این رابطه ای که نوشتید میشه بگید برای ۳ کلید متمایز به ارتفاع ۲ چند درخت دودویی به دست میاره؟
ببخشید این فرمولی که با کلی تفکر
حالا فکر کنم برای درخت دودویی هم به این صورت میشه بدست آورد.
تو این فرمول تعداد درخت های جستجوی دودویی رو بدست آوردیم. یعنی تعداد کل درخت هایی که میشه با ارتفاع h و با n گره داشت.
حالا به ازای هر یک از این درخت ها می تونیم به n! این n مقدار را درون کلیدها جا بدیم.
در نتیجه تعداد درخت های دودویی با n گره و ارتفاع h میشه:
تعداد درخت های جستجوی دودویی با n گره و ارتفاع h * n!
یکم زیادی پیچیده شد، نظرتون چیه؟
ببخشید منظور من هم همون درخت جست و جوی دودویی بودش.حالا توی این رابطه ای که نوشتید میشه بگید برای ۳ کلید متمایز به ارتفاع ۲ چند درخت جست و جوی دودویی به دست میاره؟
(۰۷ شهریور ۱۳۹۳ ۰۱:۴۸ ب.ظ)miladcr7 نوشته شده توسط: ببخشید منظور من هم همون درخت جست و جوی دودویی بودش.حالا توی این رابطه ای که نوشتید میشه بگید برای ۳ کلید متمایز به ارتفاع ۲ چند درخت جست و جوی دودویی به دست میاره؟
آها، با سه کلید متمایز به ارتفاع ۲ میتونیم ۱ نوع BST داشته باشیم.
تو فرمول هم اگه بخواییم جایگذاری کنیم میشه:
[tex]\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[/tex]
(۰۷ شهریور ۱۳۹۳ ۰۱:۵۲ ب.ظ)!!! نوشته شده توسط:(07 شهریور ۱۳۹۳ ۰۱:۴۸ ب.ظ)miladcr7 نوشته شده توسط: ببخشید منظور من هم همون درخت جست و جوی دودویی بودش.حالا توی این رابطه ای که نوشتید میشه بگید برای ۳ کلید متمایز به ارتفاع ۲ چند درخت جست و جوی دودویی به دست میاره؟
آها، با سه کلید متمایز به ارتفاع ۲ میتونیم ۱ نوع BST داشته باشیم.
تو فرمول هم اگه بخواییم جایگذاری کنیم میشه:
[tex]\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[/tex]
خب به نظرتون با ۳ کلید متمایز تعداد درخت های جستجوی دودویی به ارتفاع ۲ برابر ۴ تا نیستش؟
(۰۷ شهریور ۱۳۹۳ ۰۲:۰۱ ب.ظ)miladcr7 نوشته شده توسط: خب به نظرتون با ۳ کلید متمایز تعداد درخت های جستجوی دودویی به ارتفاع ۲ برابر ۴ تا نیستش؟
متوجه نمیشم، خب ۱۴،۲۰،۱۰۰ سه کلید متمایز هستند، میشه لطفا بگید چجوری میشه ۴ تا درخت متمایز (به ارتفاع ۲) داشت؟
(۰۷ شهریور ۱۳۹۳ ۰۲:۰۵ ب.ظ)!!! نوشته شده توسط:(07 شهریور ۱۳۹۳ ۰۲:۰۱ ب.ظ)miladcr7 نوشته شده توسط: خب به نظرتون با ۳ کلید متمایز تعداد درخت های جستجوی دودویی به ارتفاع ۲ برابر ۴ تا نیستش؟
متوجه نمیشم، خب ۱۴،۲۰،۱۰۰ سه کلید متمایز هستند، میشه لطفا بگید چجوری میشه ۴ تا درخت متمایز (به ارتفاع ۲) داشت؟
یه بار ۱۴ رو ریشه فرض کنید یه بار هم ۱۰۰ رو ریشه فرض کنید
(۰۷ شهریور ۱۳۹۳ ۰۲:۱۴ ب.ظ)miladcr7 نوشته شده توسط: یه بار ۱۴ رو ریشه فرض کنید یه بار هم ۱۰۰ رو ریشه فرض کنید
اونموقع میشه به ارتفاع ۳، فکر کنم شما ریشه رو ۰ فرض کردین. درسته!؟
و یه چیز دیگه، اون فرمولی که نوشته بودم مربوط به تعداد درخت دودویی با n گره و با ارتفاع h بود نه درخت جستجوی دودویی. من یکم آره
(بدون توجه به کلیدها) چون در مسائل بویژه عدد کاتالان، مقادیر کلیدها مد نظر نیست و فقط تعداد اشکال (درخت دودویی با n گره) مد نظر است که حالا اگه بگه با n گره و با ارتفاع h (به ارتفاع هم محدود بشه مسئله) اون موقع این فرمول جواب میده.ویرایش: در فرمول بالا ریشه رو یک گرفته ام.
(۰۷ شهریور ۱۳۹۳ ۰۲:۲۵ ب.ظ)!!! نوشته شده توسط:(07 شهریور ۱۳۹۳ ۰۲:۱۴ ب.ظ)miladcr7 نوشته شده توسط: یه بار ۱۴ رو ریشه فرض کنید یه بار هم ۱۰۰ رو ریشه فرض کنید
اونموقع میشه به ارتفاع ۳، فکر کنم شما ریشه رو ۰ فرض کردین. درسته!؟
و یه چیز دیگه، اون فرمولی که نوشته بودم مربوط به تعداد درخت دودویی با n گره و با ارتفاع h بود نه درخت جستجوی دودویی. من یکم آره
ویرایش: در فرمول بالا ریشه رو یک گرفته ام.
خب ریشه که ارتفاعش صفره.چجوری یک گرفتین؟
در ضمن با این شرایط که شما در نظر گرفتی اگه برای ۳کلید متمایز به ارتفاع ۳ بخوایم تعداد درخت جستجوی دودویی رو به دست بیاریم جوابتون ترکیب ۰ از ۴ میشه که برابر ۱ هستش