خسته نباشید.توی pdf سوم ساختمان اقای یوسفی صفحه ۱۱ یه سوال داره که میخواد یه BTree درست کنه و گفته فرض کنید a<b<c<d. میشه بگید متن کامل سوال چیه و جوابشم یه توضیح بدید.
ممنون
a b c d دیتاهامون هستند، که طبق سوال مقدار a کمترین و d بیشترین هست، سوال فقط شکل درخت رو بدون دیتاها بهمون داده، حالا میگه با این شکل و طبق دیتاها، حالا به چند ترتیب دیتاها رو توو درخت بچینیم که به اون شکل دربیاد و bst باشه
روش حل اینطوره که اول میایم دیتاهارو خودمون توو درخت میچینیم، چطوری؟ شکل میگه که دوعدد هستن که کوچکتر از ریشه هستن و یک عدد بزرگتر از ریشه، پس c ریشه هست، حالا بقیه مقادیرم توو درخت میزاریم
خب کار ما شروع میشه، اول همیشه باید ریشه گذاشته شه، اوکی؟ خب بعدش میگیم ترتیب زیر درخت چپ باید حتما رعایت شه، یعنی مسلما اول aمیاد بعد b ، حلله؟ خب پس تا الان شد c a b ، میمونه d، این جناب d میتونه بلافاصله بعد از c بیاد و یا بلافاصله بعد از a، یا بزاره a و b که اومدن ، بعد اونا بیاد، چقدر زیبا و شیرین
پس چند حالت شد؟
c d a b
c a d b
c a b d
یعنی تو شکل اولیه ما a,b,c,d رو توی نودها قرار ندادیم؟فقط شکل درخت هستش؟
اگه اینجوریه گرفتم چی شد.
(۱۲ مرداد ۱۳۹۳ ۰۸:۲۱ ب.ظ)miladcr7 نوشته شده توسط: یعنی تو شکل اولیه ما a,b,c,d رو توی نودها قرار ندادیم؟فقط شکل درخت هستش؟
صورت سوال نداده، اما اگرم گذاشته بود تاثیر خاصی نداشت، حرف اصلیه سوال اینه به چند حالت میشه اینارو توو این شکل چید به شرطی که کوچیک بزرگیش اونطوری باشه، بودن یا نبودن دیتاها توو شکل قسمت ابتداییه سواله که ببینه اصلن بلدی bst چیه یا نه تا بتونی توو شکل بچینیشون
گرفتم چی شد.میشه توی مثال پایینش اون قسمت فاکتوریل رو هم یه توضیح بدید
یه سوال دیگه :توی ساخت درخت دودویی با حداقل ارتفاع که ۱۰ نود داره یه بار با فرض کامل بودن درخت یه بار هم با فرض کامل نبودن درخت حل کردیم که این دو حالتو با هم جمع کردیم.درست گفتم؟
(۱۲ مرداد ۱۳۹۳ ۰۸:۳۳ ب.ظ)miladcr7 نوشته شده توسط: گرفتم چی شد.میشه توی مثال پایینش اون قسمت فاکتوریل رو هم یه توضیح بدیدخب حالا توو پایینی اول ریشه یعنی d میاد. بعد میدونیم که b a c مثل یه بسته ای هستن که باید حتما به همین ترتیب بیان(اما a و c میتونن جا به جاشن اما b حتما باید قبلشون بیاد). همینطور زیر درخت راستیه. همشون باید مثل اون بسته ای که کشیدم به ترتیب باشن( اما i میتونه یا بعد از h بیاد یا بعد از g یا بعد از f) اوهوم؟ خب ریشه که کلا باید اول بیاد. بغیر از ریشه ۸ دیتای دیگه هستن که حالتاش میشه ۸! اما طبق حرفی که واسه اون بسته ها گفتم، باید از بین حالات کمشون کنیم و دیگه اصل شمارشو این حرفاس. یس؟ اون ۲ هم که نوشتم برای جابه جاییه a و c هست. اون ۳ اخرم برای جابه جاییه i
امیدوارم متوجه شده باشی
مرسی گرفتم.فکر کنم باید استاد شید روش توضیح دادنتون هم خوبه هم خیلی جالب.سوال دومی که پرسیدم برای درخت با حداقل ارتفاع علتشو درست گفتم؟
نمیدونم سوال دوم کجاست:دی
اینم سوال دوم:
توی ساخت درخت دودویی با حداقل ارتفاع که ۱۰ نود داره یه بار با فرض کامل بودن درخت یه بار هم با فرض کامل نبودن درخت حل کردیم که این دو حالتو با هم جمع کردیم.درسته؟
(۱۳ مرداد ۱۳۹۳ ۱۰:۵۹ ق.ظ)miladcr7 نوشته شده توسط: اینم سوال دوم:
توی ساخت درخت دودویی با حداقل ارتفاع که ۱۰ نود داره یه بار با فرض کامل بودن درخت یه بار هم با فرض کامل نبودن درخت حل کردیم که این دو حالتو با هم جمع کردیم.درسته؟
نه لزوما کامل، چون کامل باید حتما برگها از چپ چینده شن، اما فرض کردیم سه سطح اول نودها کامل شدن، و میمونه سه نود در ٨ جای باقی مونده در سطح اخر
و چون سطح اخر ما فقط سه تا میخوایم و ٨ تا جا داشتیم، گفتیم اگه از سطر یکی مونده به اخر یه نود کم کنیم حالا سطر اخر ٤ تا میخواد در ٦ تا جا، دیگه بیشتر نمیتونیم نود از سطح یکی مونده به اخر کم کنیم، و در نهایت باهم جمع زدیم
بله بله مرسی از توضیحتون
سلام.توی پیاده سازی درخت دودویی با لیس پیوندی ما برای هر نودی ۲ تا اشاره گر چپ و راست میتونیم داشته باشیم.یعنی برای n نود ۲n اشاره گر داریم.از طرفی توی هر درخت با n نود n-1 یال هم دارم.حالا سوال من اینه این محاسبه ای که ما انجام دادیم :
[tex]2n-(n-1)=n 1[/tex]
تعداد لینک های تهی رو به دست اوردیم یا تعداد لینک های غیرتهی؟
(۱۳ مرداد ۱۳۹۳ ۰۴:۵۸ ب.ظ)miladcr7 نوشته شده توسط: سلام.توی پیاده سازی درخت دودویی با لیس پیوندی ما برای هر نودی ۲ تا اشاره گر چپ و راست میتونیم داشته باشیم.یعنی برای n نود ۲n اشاره گر داریم.از طرفی توی هر درخت با n نود n-1 یال هم دارم.حالا سوال من اینه این محاسبه ای که ما انجام دادیم :
[tex]2n-(n-1)=n 1[/tex]
تعداد لینک های تهی رو به دست اوردیم یا تعداد لینک های غیرتهی؟
تعداد کل اشاره گرها : ۲n
تعداد اشاره گرهای مورد استفاده (پر): n-1
تعداد اشاره گرهای خالی :n+1
مرسی.حدس میزدم.اخه توی جزوه با تیتر تعداد لینکهای غیرتهی بود پرسیدم
(۱۳ مرداد ۱۳۹۳ ۰۶:۱۸ ب.ظ)miladcr7 نوشته شده توسط: مرسی.حدس میزدم.اخه توی جزوه با تیتر تعداد لینکهای غیرتهی بود پرسیدم
خواهش میکنم به نظر من آدم چیزی را که شک داره باید بپرسه تا کامل متوجه بشه