تالار گفتمان مانشت

سوال 52 کنکور سال 84 که میگه چند حالت عناصر با کلیدهای a<b<c<d را میتوان وارد یک درخت دودوئی جست وجوی تهی کرد تا درختی به شکل زیر ایجاد شود ...

1-4
3-2
3-2
4-1


برای من یه ابهام وجود داره اینکه مگه تودرخت جستجوی دودویی هر پدر از گره سمت چپ خود بزرگتر واز سمت راستی خود کوچکتر نیست ..از اونجایی که کلید هارو a<b<c<d در نظر گرفته این تصور وجود داره که کلید d بزرگترین بعد c,b , a هست پس تنها در حالتی که b پدر باشه a سمت چپ و d سمت راست و پدر گره c که سمت چپ باشه درخت ساخته میشه این 3 حالت که جایگشت کلیدهای a, d نسبت به هم جابجاپذیرند رو نمی فهمم ...لطفا اگه میتونید این مسئله رو برای من شرح بدید شاید اصلا صورت سوال رو خوب متوجه نشدم

برای انتخاب ریشه 4 حالت داریم بعد میتونیم درختها رو به صورت اریب از راست‌، چپ و به صورت ساده بچینبم اینکه میگه برای چیدن a , d بعد از B چند حالت داریم یکی اینه که a , d در دو طرف B باشند یا اینکه یک بار D را در سمت راست بگذاریم و a را در سمت چپ d بگذاریم. یا اینکه a را در سمت چپ B و d را سمت راست a بگذاریم و ........

همان طور که در سوال اومده a کوچکترین و d بزرگترین است و این دو گره نمی تونه ریشه باشه(درخت اریب می شه و bst نمی شه) و چون در فرم درختی که خود سوال داده 2 گره در سمت راست و یک گره در سمت چپ ریشه هست پس دو گره بزرگتر از ریشه باید در سمت راست قرار گیرد پس فقط می تواند b ریشه باشد و سه حالت برای چیدن این در خت هست.
badc
bdac
bdca
والد همیشه زودتر می آید (b) و a چون کوچکتر از همه است , مهم نیست که کجا باشه وباید فقط بعد از b بیاد و
و d بزرگتر از c هست باید زودتر از c بیاد
امیدوارم کمکت کرده باشم

فکر کنم مشکلی نداشته باشه اریب بشه؟؟؟!!!

ممنون خانم arezoo.j

اما ابهام من هنوز برطرف نشده مگه درخت جستجوی دودوئی هر گره سمت چپ درخت از پدر کوچکتر نیست واینجور که شما هم استدلال کردید اینه که گرها بارعایت کوچکتر بزرگتری قرار گرفتن چطوره که میگید a چون کوچکتر از همه است , مهم نیست که کجا باشه این یعنی چی متوجه نمیشم از یک طرفa<b<c<d واز طرف دیگه تحلیل شما ؟ از دوستان دیگه اگر کسی میتونه کمک کنه ...

هر پدر از گره سمت چپ خود بزرگتر و از سمت راستی خود کوچکتره.

گفتن a چون کوچکتره نمیتونه ریشه باشه چون اینجوری فقط سمت راستش میتونه گره قرار بگیره.

من فکر می کنم شما سوال رو اشتباه فهمیدین!
ما تو این سوال فقط یه مدل می تونیم درخت رو درست کنیم که همون مدلی هست که خودتون گفتین!
تو این سوال داره میگه چجوری ورودی باید بدیم که این درخت درست شه
یعنی اول حتما باید b رو بیاریم
بعدش a یا d
ورودی هامون این طوری میشه
bdac
bdca
badc
که سه حالت میشه

(19 مهر 1389 11:52 ق.ظ)afagh1389 نوشته شده توسط: [ -> ]فکر کنم مشکلی نداشته باشه اریب بشه؟؟؟!!!

اون موقع دیگه bst نیست

---

(19 مهر 1389 11:29 ب.ظ)bahar نوشته شده توسط: [ -> ]ممنون خانم arezoo.j

چطوره که میگید a چون کوچکتر از همه است , مهم نیست که کجا باشه این یعنی چی متوجه نمیشم از یک طرفa<b<c<d واز طرف دیگه تحلیل شما ؟ از دوستان دیگه اگر کسی میتونه کمک کنه ...

منظوره من اینه که فرزند سمت چپ b تنها a هست و a باید بعد از b بیاد
و c فرزند d هست و باید بعد از اون بیاد
ما طبق قانون پدر و فرزندی گره‌ها رو می چینیم.
حالا اگه با توجه به دو نکته بالا گره‌ها رو بچینی می بینی که سه حالت داریم
اگه متوجه نشدی voice طورانی جلسه چهارمو گوش کن

سلام میشه این سوال و جواب بدین امتحان دارم.
ایادنباله های postorder وinorder یک درخت دودویی, ان درخت را منحصر به فرد تعریف کنید(با اثبات پاسخ)
mer30

در حالت کلی اینو بگم که ترتیب ورود برای ساخت یک درخت میتونه درختها را به شکلهای متفاوتی نشون بده پس باید با این ترتیب حالتهای مختلف را چک کنید
یکبار 3421
یکبار دیگر 2341 ووو......

1- اول اینکه با وجود شکل سوال کاملا گویاست که تنها عنصری که می تواند در ریشه قرار بگیرد b است چون قرار گرفتن سایر عناصر به عنوان ریشه BST درختی را که بوجود میاره یا اریب به چپ یا اریب به راست یا اینکه مشابه شکل سوال نیست .

2- بعد از b عناصر a یا d می تواند به عنوان عنصر بعدی BST در نظر گرفته شود .
2-1 - اگر ورودی به شکل bd باشد با توجه به ترتیب عناصر هم c و هم a می توانند بلافاصله وارد BST شوند که دو حالت bdac و bdca را بوجود میاره.
2-2- اگر ورودی به شکل ba باشد با توجه به شکل اگر ابتدا c و سپس d وارد BST شوند مطابق شکل غلط است .
2-3- اگر ورودی به شکل ba باشد با توجه به شکل اگر ابتدا d و سپس c وارد BST شوند حالت سوم یعنی badc را بوجود میاره.

---

شکل 3-2

توی ساخت درخت دودویی نکته مهم اینه که ریشه هر زیر درخت ار فرزندانش زودتر بیاد.و میدونیم مه تربیت اومدن فرزنداش اگه خود اونها ریشه نباشن مهم نیست. یه جیز دیگه:چرا میگید درخت اریب bst نیست؟درخت اریب یک در خت bst با بیشترین ارتفاع ممکن است

اینجا سوال یه شکل داشته که نگذاشتن و به خاطر اینکه درخت توی شکل اریب نیست اینجوری گفتن.
البته اگه Balanced BST داشته باشیم دیگه نمیتونه اریب باشه.