درخت سرخ-سیاه
اضافه کردن

اضافه کردن به وسیلهٔ پیاده‌سازی انجام شده در درخت‌های دودویی و رنگ آمیزی آن‌ها با رنگ قرمز انجام می‌شود. اتفاقی که بعداً می‌افتد بستگی به شیوهٔ رنگ آمیزی گره‌های مجاور بستگی دارد عبارت گره عمو به برادر گره والد اشاره دارد، همانند آنچه که در روابط خانوادگی مطرح است. توجه به موارد زیر لازم است:
. ویژگی ۵ (همهٔ برگ‌ها سیاه هستند (گره‌های nullهم سیاه محسوب می‌شوند)) همیشه باید حفظ شود.
. ویژگی ۳ (فرزندان گره قرمز سیاه هستند) با اضافه کردن گره قرمز و تغییر رنگ گره به سیاه یا چرخش تهدید می‌گردد.
. ویژگی ۴ (همهٔ مسیرها باید دارای تعداد مساوی گره سیاه باشند) با اضافه کردن یک گره سیاه تغییر رنگ فرمز به سیاه یا چرخش تهدید می‌شود
توجه کنید: برچسب‌های N برای گره اضافه شده، P برای والد گره اضافه شده،G برای پدربزرگ گره اضافه شده و U برای عموی گره اضافه شده مورد استفاده می‌شود.
هر مثال شامل شرحی در زیان سی++ می‌باشد:
class RBT{
.
.
.
BinaryNode * grandParent(BinaryNode *n){
if((n!=null) &&( n->parent!=null))
      return n->parent->parent;
   else
      return NULL;
}
BinaryNode * uncle(BinaryNode *n){
BinaryNode *g=grandparent(n);
if(n->pareant==g->left)
    return g->right;
else
    return g->left;
}
}
حالت ۱ :گره جدید N ریشهٔ درخت باشد. در این حالت با تغییر رنگ به سیاه (بخاطر ویژگی ریشه باید سیاه باشد) و در هر مسیر باید یگ گره سیاه وجود داشته باشد اعتبار درخت را حفظ می‌کند.
void insert_case1(BinaryNode *n){
if(n->parent==null)
    n->col=Black;
else
    insert_case2(n);
}
حالت ۲:
اگر گره والد سیاه باشد هیج کدام از دو ویژگی (هردو فرزند قرمز، سیاه هستند و تعداد راه‌های از هر مسیر به برگ دارای تعداد یکسان گره سیاه دارند) مورد تهدید واقع نمی‌شوند ولی فقط وجود دوگره قرمز اعتبار درخت را زیر سؤال می‌برد (حالت ۳).
void insert_case2(BinaryNode *n){
if(n->parent->col==Black)
    return;//درخت همچنان هر پنج ویژگی را دارد.
else
    insert_case3(n);
}
حالت ۳:اگر هردو گره والد و عمو قرمز باشد، هردو به رنگ سیاه در می‌آیند و پدر آن‌ها قرمز در می‌آید. (برابر ویژگی ۴). گره قرمز جدید دارای والد سیاه است. تا آن زمان که هر راه از والد /عمو که به‌طور قطع از پدر بزرگ نیز عبور می‌کند همچنان معتبر می‌باشد. با این وجود G(پدر والد و عمو و پدربزرگ N) باید بررسی شود که آیا ریشه‌است یا خیر (تا به رنگ سیاه درآید (ویژگی ۲) این کار را می‌توان با یک متد بازگشتی انجام داد. حتی می‌توان آن را به صورت یک حلقه نوشت که البته ثابت می‌شود این حلقه دارای تعداد مشخصی انجام عملیات چرخش است.
void insert_case3(BinaryNode *n){
   BinaryNode u=uncle(n);
if((u!=null)&& )u->col==Red){
    n->parent->col=Black;
    u->col=Black;
    g=grandparent(n);
    g->col=Red;
    insert_case1(g);
}else
    insert_case4(n);
}
حالت ۴:اگر والد (p) قرمز باشد ولی عمو سیاه باشد همچنان گره جدید سمت راست p است و p فرزند سمت چپ G است. در این حالت، یک دوران به چپ که نقش گره جدید N را با والدش؛ P تغییر می‌دهد، قابلیت اجرا پیدا می‌کند که در آن والد قبلی با فرزندش جابجا می‌شود سپس والد قبلی که اکنون دوباره برچسب‌گذاری شده با ویژگی همه مسیرها دارای تعدا مساوی گره سیاه هستند؛ سر و کار دارد. چون بر طبق ویژگی ۴ (هر دو فرزند گره قرمز سیاه هستند) همچنان مورد تهدید بی اعتبارشدن درخت همراه است. دوران باعث می‌گردد تا در بعضی از مسیرها (از جمله مسیری که از زیر درخت برچسب‌گذاری شدهٔ ۱)عبور می‌نماید از گره جدیدی که قبلاً مطرح نبوده‌است، عبور می‌کند ولی چون این گره مانند گره قبلی قرمز است، ویژگی ۴ با دوران اعتبار درخت را از بین نمی‌برد.
به همین ترتیب اگر والد (p) قرمز باشد ولی عمو سیاه باشد همچنان گره جدید سمت چپ p است و p فرزند سمت راست G است. در این حالت، یک دوران به راست روی والد(p) انجام می‌شود.
void insert_case4(BinaryNode *n){
   BinaryNode g=grandparent(n);
   if((n== n->parent->right) && (n->parent ==g->left)){
rotate_left(n->parent);
}else if((n== n->parent->left) && (n->parent ==g->right)){
   rotate_right(n->parent);
   n=n->right;

}
    insert_case5(n);
}
حالت ۵:والد قرمز است ولی عمو سیاه می‌باشد و گره جدید N فرزند چپ والد P است و P فرزند چپ پدربزرگ(G)است. در این حالت رو ی پدر بزرگ(g) دوران به راست اجرا می‌گردد. درختی که نتیجه می‌شود دارای والد ی به نام P برای هردو گره G و N است .G، به عنوان ریشه، سیاه است و این تا آن زمان که فرزندش قرمز باشد پابرجاست. با تغییر رینگ P و G درخت نهایی حاصل می‌گردد که همهٔ ویژگی‌های فوق از جمله تعداد مساوی گره سیاه در هر مسیر (به این شکل که تمامی مسیرهایی که از این سه گره عبور می‌کند که قبلاً از G عبور می‌کرده و اکنون از P عبور می‌کند) پابرجاست.
به همین ترتیب اگر والد قرمز است ولی عمو سیاه می‌باشد و گره جدید N فرزند راست والد P است و P فرزند راست پدربزرگ(G)است. در این حالت رو ی پدر بزرگ(g) دوران به چپ اجرا می‌گردد.
void insert_case5(BinaryNode *n)
{
        BinaryNode *g = grandparent(n);

        n->parent->color = BLACK;
        g->color = RED;
        if ((n == n->parent->left) && (n->parent == g->left)) {
                rotate_right(g);
        } else {
                /*یعنی :
                 * (n == n->parent->right) && (n->parent == g->right).
                 */
                rotate_left(g);
        }
}
| ن ب وساختمان داده‌ها | ن ب وساختمان داده‌ها |
| --- | --- |
انتزاعی:  آرایه انجمنی  پشته  صف دوطرفه  صف اولویت دوطرفه  لیست  مجموعه (نوع داده انتزاعی) مجزا 
آرایه‌ها:  آرایه بیتی  آرایه پویا  جدول درهم‌سازی  درخت آرایه درهم  بافر چرخشی  ماتریس خلوت 
پیوندی:  فهرست انجمنی  فهرست پرشی  فهرست پیوندی دوطرفه  واپیچیده  XOR 
درخت:  درخت جستجوی دودویی (AVL •  قرمز-سیاه •  اسپلی)  بی  بی‌پلاس  هیپ (دی هیپ •  فیبوناتچی •  دوجمله‌ای)  فنویک  ترای 
گراف:  جهت‌دار  جهت‌دار بدون‌دور  ابرگراف 
درخت قرمز-سیاه مثال فوق، مانند یک درخت بی است.
Diagram of case 3
Diagram of case 4
Diagram of case 5