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

نکات - درخت دودویی ویژه

ارسال:
  

Masoud05 پرسیده:

نکات - درخت دودویی ویژه

منتظر ارسال شماییم!!!

۳
ارسال:
  

yaser_ilam_com پاسخ داده:

نکات - درخت دودویی ویژه

(Red-Black Trees (RBT


  1. درختهای قرمز و سیاه نوعی درخت جستجوی دودویی است که هر گره آن علاوه بر فیلدهای دیگر، یک بیت رنگ نیز دارد
  2. بیت رنگ دوحالته (قرمز یا سیاه) است
  3. هدف از این بیت، تضمین توازن نسبی درخت است
  4. در درخت جستجوی دودویی، عملیات جستجو ، افزودن و حذف گره هزینه ای متناسب با عمق درخت دارند.
  5. عمق درخت متوازن با N گره از مرتبه O(log N) است.
  6. عمق درخت نامتوازن با N گره از مرتبه O(N) است.
  7. RBT = BST + 1 color bit
  8. تمام برگهای تهی ( فرزندانی که وجود ندارند،) به رنگ سیاه هستند
  9. برای مشخص نمودن برگهای تهی ، یک گره کمکی nil می سازیم و از آن به جای تمام فرزندان تهی درخت استفاده می کنیم.
  10. ریشه درخت سیاه است
  11. هر گره تهی(null) سیاه است
  12. اگر گرهی قرمز باشد، هر دو فرزند آن سیاه هستند
  13. همه مسیرهایی که از یک گره شروع شده و به برگ می رسند، دقیقا دارای تعداد مساوی گره سیاه هستند.


فایل‌(های) پیوست شده
درخت قرمز و سیاه.ppt
اندازه فایل: ۵۸۷/۵ KB

۳
ارسال:
  

Masoud05 پاسخ داده:

RE: نکات - درخت دودویی ویژه

نکته زیر رو توی بخشی کنکور دکتری هم گزاشته بودم اما گفتم شاید بچه های کارشناسی به اونجا سر نزنن ، پس اینجا هم آوردمش :

Treap یک درخت دودویی است که هر نود آن دارای یک کلید با خاصیت BST و یک اولویت با خاصیت Heap ( مینیمم یا ماکسیمم ) است . یعنی یک پیمایش inorder روی کلید ها ، کلید ها را بصورت مرتب برمیگرداند . اولویت گره ها هم که مثل Heap است

نکته ۱: شکل Treap منحصر بفرد است و وابسته به ترتیب درج و حذف نیست
نکته ۲: یک Treap لزوماً یک درخت کامل نمی باشد اما متمایل به حالت موازنه است .

۲
ارسال:
  

yaser_ilam_com پاسخ داده:

RE: نکات - درخت دودویی ویژه

درخت های نخی دودویی

  • تعداد اتصالات تهی در یک درخت دودویی بیشتر از تعداد اشاره گرهای غیرتهی است.
  • در یک درخت دودویی تعداد n+1 اتصال از کل اتصالات آن یعنی ۲n، تهی است. اگر از اتصالات تهی برای ارتباط با دیگر گره های یک درخت استفاده شود در این صورت درخت را درخت نخی می نامند.
  • برای ایجاد اتصالات نخی از قوانین زیر استفاده می شود:
  • اگر ptr -> left_child تهی باشد، آن را طوری تغییر می دهیم که به گره ای که در پیمایش inorder، قبل از ptr قرار دارد، اشاره کند.
  • اگر ptr -> right_child تهی باشد، آن را طوری تغییر می دهیم که به گره ای که در پیمایش inorder، بعد از ptr قرار دارد، اشاره کند.
  • هنگامی که درختی را در حافظه نمایش می دهیم، بایستی بتوانیم بین اتصالات نخی و واقعی تفاوتی قائل شویم. این کار را با افزودن دو فیلد اضافی به هر گره انجام می دهیم که آن ها را right_thread، left_thread می نامیم.
  • مقدار این دو فیلد از نوع Boolean می باشد. اگر مقدار اشاره گر Right_child پوچ (NULL) نباشد مقدار right_thread = false می شود، در غیر این صورت right_thread = true خواهد بود به این معنی که اشاره گر راست به گره بعدی در پیمایش inorder اشاره می نماید نه به فرزند راست. مقدار left_thread نیز به همین روش مقدار می گیرد


پیمایش inorder یک درخت نخی دودویی

  • برای هر گره مانند ptr، در یک درخت دودویی، چنانچه ptr->right_thread = TRUE باشد، طبق تعریف گره بعدی ptr در پیمایش inorder، گره ptr->right_childمی باشد.
  • در غیر این صورت گره بعدی ptr، با پایین رفتن روی مسیر فرزندان چپ ptr از طرف فرزند سمت راست ptr تا وقتی که به گره ای با وضعیت left_thread = TRUE برسیم، تعیین می شود.
  • تابع in_successor بدون استفاده از پشته، گره بعدی در پیمایش inorder را در یک درخت نخی دودویی پیدا می کند.
  • برای پیمایش inorder می توانیم با فراخوانی مکرر تابع in_successor تمام گره ها را بازیابی کنیم.

نقل قول:
کد:
threaded_pointer  in_successor (threaded_pointer tree)
{
/* find  the  inorder  successor  of  tree  in  a threaded  binary  tree */
    threaded_pointer  temp ;
    temp = tree -> right_child ;
    if  (! tree -> right_thread)
        while  (! temp -> left_thread)
            temp = temp -> left_child ;
    return  temp ;
}

نقل قول: تابع پیمایش Inorder درخت نخی دودویی
کد:
Void  tinorder (threaded_pointer  tree)
{
/* traverse  the  threaded  binary  tree  inorder */
    threaded_pointer  temp = tree;
    while(true){
        temp = in_successor (temp);
        if  (temp == tree)  return;
        else
             cout << temp -> data << “   “;
    }
}


منبع : مهدی ایل بیگی
دانشگاه آزاد اسلامی دماوند


فایل‌(های) پیوست شده




موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  جزوه خلاصه نکات مهم فصول ابتدایی درس مهندسی نرم افزار Happiness.72 ۱ ۳,۸۰۷ ۱۳ خرداد ۱۴۰۱ ۰۶:۲۸ ب.ظ
آخرین ارسال: M o h m m @ d
  نکات کنکوری روز خواستگاری Fardad-A ۳۷ ۳۴,۷۶۶ ۰۵ دى ۱۳۹۸ ۰۶:۳۳ ب.ظ
آخرین ارسال: Behnam‌
  نکات کتاب طراحی الگوریتم نارنجی پوران پژوهش(نوشته ی خود آقای یوسفی) Milad_Hosseini ۱ ۴,۹۷۱ ۱۵ آبان ۱۳۹۷ ۰۶:۳۷ ب.ظ
آخرین ارسال: asdasdasdasd
  نکات کلیدی در چاپ کاتالوگ (قسمت اول) melinaa ۰ ۱,۹۱۵ ۰۴ شهریور ۱۳۹۷ ۱۰:۲۸ ق.ظ
آخرین ارسال: melinaa
Brick میتینگ رایگان شروع دوره آنلاین برنامه نویسی تجاری با #C ویژه ورود به بازار کار one hacker alone ۰ ۲,۳۷۴ ۲۹ تیر ۱۳۹۷ ۰۷:۲۸ ق.ظ
آخرین ارسال: one hacker alone
Lightbulb نکات کاربردی جهت پایان نامه/مقاله نویسی αɾια ۱۳ ۸,۸۵۷ ۱۹ فروردین ۱۳۹۷ ۰۹:۴۶ ب.ظ
آخرین ارسال: nlp@2015
  [نکات زندگی] ۱۰ شرایط خطرناک برای ازدواج ! farazin ۱۷ ۱۸,۶۰۸ ۲۳ دى ۱۳۹۶ ۰۲:۴۴ ب.ظ
آخرین ارسال: WILL
  [نکات زندگی] مـرا همـانگـونه کـه هستـم دوسـت داشتـه بـاش! good-wishes ۶ ۹,۷۶۲ ۲۳ دى ۱۳۹۶ ۱۰:۱۴ ق.ظ
آخرین ارسال: royka
  [نکات زندگی] زبانش را بشناسید تا حرف دلش را بفهمید good-wishes ۱ ۳,۴۶۵ ۰۶ دى ۱۳۹۶ ۱۲:۳۹ ق.ظ
آخرین ارسال: αɾια
Question بحث درس مباحث ویژه در مهندسی نرم افزار ؟؟ coder1984 ۶ ۱۹,۷۳۳ ۰۵ دى ۱۳۹۶ ۱۱:۳۱ ق.ظ
آخرین ارسال: αɾια

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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