زمان کنونی: ۰۹ فروردین ۱۴۰۳, ۱۱:۰۶ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1

ارسال:
  

Mr.R3ZA پرسیده:

بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1

با سلام
بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1 چه مرتبه ای میتونه داشته باشه؟؟؟
باتشکر
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

Alisalar پاسخ داده:

RE: بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1

سلام
اگه مقادیر کلیدها صحیح باشند که میشه باکت سورت زدو توی زمان n مرتبشون کرد و توی زمان n هم bst بسازیم
پس داریم تتای n+n که همون n میشه
اگه مقادیر کلیدها صحیح نباشه که کمتر از nlgn نمیشه قطعا مگر اینکه کلیدها از قبل مرتب باشن
منتظر به چالش کشیده شدن هستمSmile
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

عزیز دادخواه پاسخ داده:

RE: بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1

به نظرم در حالتی که همه کلید ها رو داشته باشیم و بعد inorder کنیم که درست نیست چون در این صورت ارتفاعش لگاریتمی میشه.
اگر کلید ها رو یکی یکی درج کنیم که میشه n*h. که با توجه به اینکه ارتفاع درخت رو n گرفتید پس مرتبه زمانی ان به توان دو میشه.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

عزیز دادخواه پاسخ داده:

RE: بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1

ممنونم به نظرم حرف شما درست تره. بله اگه بشه با مرتبه n مرتب کرد مرتبه زمانیش کمتر میشه.
ممنونم از جوابتون.

البته یک نکته رو بگم که ممنون میشم نظرتون رو بگید این روشی که دوستمون گفتند n میشه به نظر من روش غیر عملیه که حتما باید در مرحله اول همه داده ها موجود باشند که بتونیم با مرتبه n مرتبشون کنیم. درسته این حرف؟
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Mr.R3ZA پاسخ داده:

RE: بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1

من که هنوز متوجه نشدم؟؟
آیا کسی هست که بتونه بهتر توضیح بده؟
نقل قول این ارسال در یک پاسخ

ارسال:
  

Alisalar پاسخ داده:

RE: بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1

سلام
ساخت bst دو حالت داره
حالت اول اینه که تمام کلیدها رو در ابتدا داشته باشیم یعنی n تا کلید به ما بدن بگن باهاشون bst بساز
حالت دوم اینه که تمام کلیدها رو با هم ندن و به تدریج کلیدها سر و کلشون پیدا بشه (مثل خیلی از کنفرانسها و کلاسها و جلساتی که توی ایران برگزار میشهWink)

در حالت اول کلیدها رو در زمان (O(nlgnمرتب می کنیم ، خوب حالا باید با این کلیدای مرتب شده درخت بسازیم
صورت سوال گفته درخت به ارتفاع n-1 یعنی همون درخت مورب که هر سطحش فقط یه گره داره
کارمون سادس ، کلیدهای مرتب شده رو به ترتیب (صعودی یا نزولیش فرق نمیکنه) زیر هم درج می کنیم که میشه از مرتبه (teta(n
پس کل عملیات شد مرتب سازی + درج گره ها
یعنی (teta(nlgn + n که با روش ماکسیمم گیری برابر میشه با (teta(nlgn
البته اگر مقادیر کلیدها تمامشون اعداد صحیح باشن میشه از روش مرتب سازی bucket sort استفاده کرد که یه روش مرتب سازی غیرمقایسه ای هست و عمل مرتب سازی رو در زمان (teta(n انجام میده که در این صورت میشه bst رو توی زمان (teta(n ایجاد کرد

روش دوم یه کم پیچیدگی داره اجازه بدین بیشتر فکر کنم یا از دوستان بپرسم بعدا پاسخش رو ارسال کنم
طبق معمول منتظر به چالش کشیده شدن هستم
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Alisalar پاسخ داده:

RE: بهترین زمان برای ساخت یک درخت BST با nکلید و ارتفاع دقیقا n-1

حالت دوم که کلیدها به تدریج از راه میرسند
باید n کلید رو توی bst درج کنیم عمل درج در bst بدین صورته که عنصر مورد نظر رو جستجو می کنیم اگر پیدا شد که نیاز به درج نیست ولی اگر پیدا نشد باید در همون نقطه ای که عمل جستجو به پایان رسیده یه گره جدید ایجاد کنیم و مقدار موردنظر رو توی اون گره قرار بدیم این عمل از مرتبه (O(lgn هست چون درحالت متوسط ارتفاع bst از مرتبه lgn هست و جستجو هم نهایتا به اندازه ارتفاع درخت ، گره ها رو بررسی میکنه
پس درج n گره در حالت متوسط (O(nlgn و در بدترین حالت که گره ها مرتب شده هستند و ارتفاع درخت n-1 هست برابر میشه با n^2
اما اینجا یه مشکلی هست گره ها به تدریج وارد میشن و ممکنه bst هر شکلی پیدا کنه ولی ما باید درختمون مورب باشه پس بعد از هر عمل درج ممکنه لازم باشه بعضی گره ها رو دوران بدیم یعنی (O(n تا دوران داریم که مرتبه اونا رو نمی دونم فقط می دونم هر عمل دوران سه تا اشاره گر رو تغییر میده
اگر هر عمل دوران رو از مرتبه (teta(1 فرض کنیم n تا دوران میشه از مرتبه (teta(n که چون لزوما تمام درج ها به دوران نیاز ندارن داریم (O(n
پس کل عملیات میشه (O(nlgn + n که همون (O(nlgn هست

دوستان اگه نظری درمورد دوران دارن خوشحال میشم راهنمایی کنن
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۳,۸۳۴ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  درخواست تصحیح (تعویق) زمان کنکور ارشد ۱۴۰۱ s.gg ۱ ۱۴ ۲۳ بهمن ۱۴۰۱ ۰۷:۴۳ ب.ظ
آخرین ارسال: HamidReza1
  بهترین منبع برای درس شبکه ارشد msnmkh ۲ ۱,۱۹۰ ۱۲ دى ۱۴۰۱ ۱۲:۵۵ ق.ظ
آخرین ارسال: پشتکار
Question بهترین منبع ساختمان داده برای کنکور ارشد marvelous ۱۰ ۱۱,۲۹۳ ۱۵ آذر ۱۴۰۱ ۰۷:۵۶ ب.ظ
آخرین ارسال: msnmkh
  بهترین منبع درسی و کلاس به صورت افلاین برای کنکور ارشد nrgs_h99 ۰ ۱,۲۹۹ ۱۱ مرداد ۱۴۰۱ ۰۱:۵۲ ب.ظ
آخرین ارسال: nrgs_h99
  نظر شما راجب بهترین موسسه برای کنکور ارشد کامپیوتر vahid_sh@hotmail.com ۶۵ ۳۹,۵۰۶ ۰۲ بهمن ۱۴۰۰ ۱۲:۵۴ ب.ظ
آخرین ارسال: Hadi7590
  تولدت مبارک به انگلیسی + بهترین معادل انگلیسی cyruskingsolomon ۰ ۱,۴۸۵ ۰۶ خرداد ۱۴۰۰ ۰۳:۲۱ ب.ظ
آخرین ارسال: cyruskingsolomon
  تعویق زمان کنکور ارشد sima84 ۰ ۱,۴۷۳ ۱۸ اردیبهشت ۱۴۰۰ ۰۱:۰۵ ب.ظ
آخرین ارسال: sima84
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۱۰۷ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۶۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close