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

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

ارسال:
  

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 << “   “;
    }
}


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


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




موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  نحوه یافتن پیمایش پس ترتیب یک درخت با داشتن پیمایش پیش ترتیب آن miss_samira ۲ ۲,۴۹۳ ۰۸ اسفند ۱۳۹۳ ۰۹:۵۶ ب.ظ
آخرین ارسال: shayesteb
  سوالاتی در مورد درخت Heap hejran_ha ۴ ۷,۷۰۷ ۱۵ مهر ۱۳۹۱ ۰۶:۰۴ ب.ظ
آخرین ارسال: hejran_ha
  ساخت درخت هیپ به روش جوانترین پدر shadi ۶ ۵,۴۷۶ ۱۷ شهریور ۱۳۹۱ ۱۱:۱۴ ب.ظ
آخرین ارسال: mfXpert
  با عناصر تکراری در درخت هافمن چه می کنید؟ bijibuji ۱۳ ۳,۶۲۳ ۰۸ تیر ۱۳۹۱ ۰۶:۲۵ ق.ظ
آخرین ارسال: Masoud05
  نکات - مفاهیم اولیه درخت Masoud05 ۵ ۸,۵۰۶ ۰۶ تیر ۱۳۹۱ ۰۱:۰۰ ب.ظ
آخرین ارسال: cormen
  نکات - لیست پیوندی Masoud05 ۴ ۸,۲۰۵ ۲۱ خرداد ۱۳۹۱ ۱۲:۰۰ ب.ظ
آخرین ارسال: liliana
  [نکات] آرایه - صف و پشته Masoud05 ۳ ۹,۶۶۷ ۰۲ اردیبهشت ۱۳۹۱ ۰۱:۴۳ ق.ظ
آخرین ارسال: yaser_ilam_com
  نکات - مرتب سازی Masoud05 ۱ ۵,۹۶۱ ۲۰ فروردین ۱۳۹۱ ۰۸:۲۴ ب.ظ
آخرین ارسال: yaser_ilam_com
  تعداد درخت های دودویی که پیمایش های Pre و Post آن داده شده است netsupport ۵ ۲,۷۲۳ ۰۲ بهمن ۱۳۹۰ ۰۶:۰۱ ب.ظ
آخرین ارسال: fatima1537
  یک سوال از درخت Aurora ۱۲ ۴,۵۵۰ ۰۸ دى ۱۳۹۰ ۰۲:۰۲ ق.ظ
آخرین ارسال: Lantern

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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