درخت قرمز-سیاه

از ویکی‌پدیا، دانشنامهٔ آزاد.

این مقاله نیازمند ویکی‌سازی است. لطفاً با توجه به راهنمای ویرایش و شیوه‌نامه آن را تغییر دهید. در پایان، پس از ویکی‌سازی این الگوی پیامی را بردارید.

در علم رایانه، ساختمان داده درخت‌ قرمز-سیاه، یک نوع درخت جستجوی دودویی خود متوازن کننده است. این ساختمان داده را ابتدا رودولف بایر در سال ۱۹۷۲ با نام «درخت دودویی B متقارن» ابداع کرد ولی نام جدید آن از پایان نامهٔ لیو.جی.گیباس و رابرت سجویک گرفته شده‌است. این ساختمان داده پیچیده‌ است با این حال اعمال مربوط به آن حتی دربدترین حالت نیز زمان اجرای خوبی دارند، در واقع زمان جستجو، حذف، و درج برای این درخت مانند درخت AVL لگاریتمی است ( ((O(log(n که n تعداد گره‌های موجود در درخت است). مزیت عمده این ساختمان داده نسبت به درخت AVL این است که اعمال درج و حذف با تنها یک بار پیمایش درخت از بالا به پایین و تغییر رنگ گره‌ها انجام می‌شوند و در نتیجه پیاده سازی این درخت از درخت AVL ساده‌تر است .

[ویرایش] ویژگی ها

نمونهٔ یک درخت قرمز-سیاه

درخت قرمز-سیاه یک درخت جستجوی دودویی است که ویژگی‌های زیر را دارد:

1. هرگره با یکی از دو رنگ سیاه یا قرمز رنگ آمیزی می‌شود .
2. ریشه همیشه به رنگ سیاه است .
3. اگر گره‌ای قرمز باشد فرزندان آن باید سیاه باشند.
4. تمامی مسیرها از یک گره به برگ‌ها (گره‌های null) باید دارای تعداد مساوی گره سیاه باشند.
5. تمامی برگها سیاه هستند.(برگ گره‌ای است که فرزندی نداشته باشد- همان گره‌های null)

ویژگی‌های بالا موجب این خصوصیت مهم درخت‌های قرمز-سیاه می‌شوند:

• اگر یک درخت قرمز سیاه n گره غیر null داشته باشد ارتفاع درخت حداکثر 2log(n + 1) خواهد بود.

ویژگی فوق باعث می‌شود تا درخت‌های قرمز-سیاه کارایی مناسبی در اعمال جستجو، درج، و حذف داشته باشند.
همچنین به خاطر این که در تمام مسیرهای از ریشه به برگ، تعداد گره‌های سیاه برابر است (ویژگی ۴) و ممکن نیست دو گره قرمز پشت سر هم قراربگیرند(ویژگی ۳)، در این نوع درخت‌ها طول بلندترین مسیر از ریشه تا برگ هیچ وقت بزرگتر از دو برابر طول کوتاه‌ترین مسیر ریشه تا برگ نمی‌شود.
با توجه به ویژگی‌های بالا درخت‌های قرمز-سیاه (بر خلاف درخت‌های جستجوی دودویی معمولی) هیچ وقت دچار عدم توازن شدید نمی‌شوند و زمان اجرای لگاریتمی اعمال در این درخت‌ها تضمین شده است.

[ویرایش] عملگرها

عملگرهای فقط خواندنی نسبت به درخت‌های دودویی ساده نیاز به تغییر دارند چراکه یک حالت خاص از آنها می‌باشند و حذف و اضافهٔ معمولی می‌تواند تاثیراتی از قبیل خارج شدن از شروط اولیهٔ درخت‌های قرمز- سیاه داشته باشد که برای بازگردانی آن ویژگی‌ها نیاز به تغییر رنگ و چرخش درخت دارد .اگرچه این نوع حذف واضافه پیچیدگی بسیاری دارد ولی بازهم نرخ جسجتجوی آن همچنان (O(logn می‌باشد .

[ویرایش] اضافه کردن

اضافه کردن به وسیلهٔ پیاده سازی انجام شده در درختهای دودویی و رنگ آمیزی آنها با رنگ قرمز انجام میشود . اتفاقی که بعدا می‌افتد بستگی به شیوهٔ رنگ آمیزی گره‌های مجاور بستگی دارد عبارت گره عمو به برادر گره والد اشاره دارد ، همانند آن چه که در روابط خانوادگی مطرح است . توجه به موارد زیر لازم است :

1. . ویژگی ۵ (همهٔ برگ‌ها سیاه هستند( گره‌های nullهم سیاه محسوب می‌شوند) ) همیشه باید حفظ شود .
2. .ویژگی ۳ (فرندان گره قرمز سیاه هستند) با اضافه کردن گره قرمز و تغییر رنگ گره به سیاه یا چرخش تهدید می‌گردد .
3. .ویژگی ۴ (همهٔ مسیر‌ها باید دارای تعداد مساوی گره سیاه باشند ) با اضافه کردن یک گره سیاه تغییر رنگ فرمز به سیاه و یا چرخش تهدید می‌شود

توجه کنید : برچسب‌های 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 تغییر می دهد ، قابلیت اجرا پیدا می کند که در آن والد قبلی با فرزندش جابجا می شود سپس والد قبلی که اکنون دوباره برچسب گذاری شده با ویژگی همه مسیر ها دارای تعدا مساوی گره سیاه هستند ؛سر و کار دارد . چون بر طبق ویژگی 4 (هر دو فرزند گره قرمز سیاه هستند) همچنان مورد تهدید بی اعتبارشدن درخت همراه است . دوران باعث می گردد تا در بعضی از مسیرها (از جمله مسیری که از زیر درخت برچسب گذاری شده ی 1)عبور می نماید از گره جدیدی که قبلا مطرح نبوده است ، عبور می کند ولی چون این گره مانند گره قبلی قرمز است ، ویژگی 4 با دوران اعتبار درخت را از بین نمی برد .

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)است . در این حالت رو ی Pدوران به راست اجرا می گردد .درختی که نتیجه می شود دارای والد ی به نام P برای هردو گره G و N است .G ، به عن.ان ریشه، سیاه است و این تا آن زمان که فرزندش قرمز باشد پابرجاست .با تغییر رینگ P و G درخت نهایی حاصل می گردد که همهی ویژگی های فوق از جمله تعداد مساوی گره سیاه در هر مسیر ( به این شکل که تمامی مسیر هایی که از این سه گره عبور می کند که قبلا از G عبور میکرده و اکنون از P عبور میکند ) پابرجاست .

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

[ویرایش] منابع

• دنیای ریاضی :درخت قرمز-سیاه
• دانشگاه ایالتی سن دیگو کلاس 660 :نکته هایی درباره ی درخت های قرمز-سیاه , by Roger Whitney
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. معرفی الگوریتم ها, چاپ دوم. انتشارات ام.ای.تی و مک گروهیل, 2001. شابک 0-262-03293-7 . فصل 13: درخت های قرمز-سیاه, صفحه های :273–301.

[ویرایش] پیوند به بیرون

[ویرایش] پیش نمایش

• Red Black Tree Applet, یک پیش نمایش از درخت قرمز -سیاه و سایر جستجو‌ها
• Red Black Tree Applet, یک پیش نمایش از درخت قرمز- سیاه و avl و چرخش .
• Red/Black Tree Demonstration, یک نمایش از خذف واضافه به همراه کد جاوا.
• Red-Black Tree Animation, یک نمایش از بدترین حالت ورود
• aiSee: Visualization of a Sorting Algorithm, یک فایل گیف که نشان دهندهٔ اضافه‌است (۲۰۰KB)
• Red-Black Tree Demonstration, یک نمایش از اضافه شدن با کد جاوا by David M. Howard