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. همه مسیرهایی که از یک گره شروع شده و به برگ می رسند، دقیقا دارای تعداد مساوی گره سیاه هستند.
    

• تعداد اتصالات تهی در یک درخت دودویی بیشتر از تعداد اشاره گرهای غیرتهی است.
  

• در یک درخت دودویی تعداد 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 نیز به همین روش مقدار می گیرد
  

• برای هر گره مانند 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 << “   “;
    }
}