ساختمان داده درختهای قرمز - سیاه red-black tree
ساختمان داده درختهای قرمز - سیاه red -black
یکی از درختهای متوازن، که زمان جست وجو در آن مناسب میباشد، درخت قرمز – سیاه (RBT) است که راه حلی برای مسئله اداره کردن درختهای جست وجویی نامتوازن هستند.
درخت قرمز – سیاه علاوه بر تمام خواص درخت جست وجوی دودویی، خواص ویژه ای نیز دارد. همانطور که از نام این درخت پیداست، هر یک از گره های درخت قرمز – سیاه میتواند قرمز یا سیاه باشد. اگر رنگ آمیزی گره ها بطور مناسب انجام گیرد، درخت کاملا متوازنی ایجاد خواهد شد.
قوانین (خواص) درخت قرمز – سیاه
درخت قرمز – سیاه علاوه بر تمام خواص درخت جست وجوی دودویی قوانینی دارد که به شرح زیر میباشند:
1- هر گره در درخت قرمز – سیاه به رنگ قرمز یا سیاه است.
2- در هر مسیری از یک گره به برگ باید تعداد گره های سیاه یکسانی داشته باشد.
3- اگر گره ای قرمز باشد، هر دو فرزند آن گره سیاه هستند.
4- گره ریشه به رنگ سیاه است.
اعمال این قوانین در درخت قرمز – سیاه موجب میشود که این درخت کاملا متوازن باقی بماند، در نتیجه جست وجو در آن دارای کارایی بالایی خواهد بود. اما اعمال قوانین موجب میشود اعمال درج و حذف در درخت قرمز – سیاه بسیار دشوار باشد.
درج گره در درخت قرمز – سیاه
درج گره در درخت قرمز – سیاه پیچیده است، زیرا ممکن است با درج گره جدید در درخت، یکی از قوانین مربوط به درخت نقض شود. وقتی گره ی جدیدی در درخت قرار می گیرد ، به رنگ قرمز در می آید. این عمل، تعداد گره های سیاه موجود در هر مسیر به برگ را تغییر نمیدهد، اما ممکن است موجب شود که دو گره قرمز متوالی در درخت به وجود آید، یعنی والد و فرزند هر دو قرمز باشند.
اگر گره جدید بعنوان فرزند گره سیاه درآید، مشکلی وجود ندارد. اما ممکن است فرزند یک گره قرمز محسوب شود. این وضعیت را نقض دو قرمزی (یا نقض قرمز - قرمز) میگویند و در برگ به وجود می آید. باید قواعدی موجود باشند که موجب شود نقض دو قرمزی به سمت ریشه برود ولی هیچ تاثیری در تعداد گره های سیاه هر مسیر نداشته باشد، تا اینکه با انتقال یک گره سیاه به پایین، این مشکل برطرف شود، یا اینکه به ریشه برسد، که در آنجا میتواند به رنگ سیاه درآید.
با توجه به توضیحاتی که گفته شد، برای درج گره ای در درخت قرمز – سیاه، سه مرحله زیر را دنبال کنید:
1- گره را همانند درخت جست وجوی دودویی در درخت درج کنید. رنگ گره را قرمز نمایید. قوانین 1 و 2 مربوط به درخت قرمز – سیاه نقض نمیشوند ولی ممکن است قوانین 3 و 4 نقض گردند.
2- نقض قرمز – قرمز را با استفاده از قواعد چرخش برطرف کنید. ممکن است لازم باشداین قواعد را چندین بار انجام دهید.
3- اگر مراحل 1 و 2 موجب شوند که ریشه قرمز شود، براساس قانون شماره 4 درخت قرمز – سیاه آن را سیاه کنید.
اکنون الگوریتمی برای درج گره ای در درخت قرمز – سیاه ارائه میدهیم:
ورودی : ریشه درخت قرمز – سیاه (root) و گره جدید (item)
خروجی : درخت قرمز – سیاه با درج گره جدید
1- اگر root تهی است
2- گره newNode را با داده ی item بعنوان ریشه درخت اضافه کنید و رنگ آن را سیاه تعیین نمایید
3- true را برگردان
4- وگر نه اگر (else if) مقدار item برابر با root.data است.
5- item در درخت وجود دارد، false را برگردان
6- وگرنه اگر item کوچکتر از root.data
7- اگر زیردرخت چپ null است
8- گره جدید را در زیردرخت چپ درج کرده آن را قرمز کنید.
9- true را برگردان
10- وگرنه (else)
11- اگر هر دو فرزند چپ و راست قرمز باشند
12- رنگ فرزندان را به سیاه و ریشه آنها (ریشه محلی) را قرمز کنید.
13- item را بطور بازگشتی در زیردرخت چپ درج کنید
14- اگر اکنون فرزند چپ قرمز است
15- اگر grandchild چپ قرمز است
16- رنگ فرزند چپ را به سیاه تغییر دهید و ریشه آنها را قرمز کنید
17- درخت را حول ریشه آنها چرخش دهید
18- وگرنه اگر grandchild راست قرمز است
19- فرزند چپ را به چپ چرخش دهید
20- رنگ فرزند قرمز را به سیاه و رنگ ریشه آنها را به قرمز تغییر دهید
21- ریشه آنها را به راست دوران دهید
22- وگرنه
23- item بزرگتر از root.data است.
24- اگر ریشه محلی ریشه درخت است
25- رنگ آن را سیاه تعیین کنید.
حذف گره ای از درخت قرمز – سیاه
حذف گره از درخت قرمز – سیاه مثل حذف گره از درخت جست وجوی دودویی است:
► اگر گره ای که باید حذف شود، برگ است، آن را حذف کنید.
► اگر گره ای که باید حذف شود، تنها دارای یک فرزند است، فرزند آن را به جای آن قرار دهید.
► اگر گره ای که باید حذف شود، دو فرزند دارد آن را با گره بعدی اش در پیمایش inorder جایگزین کنید و سپس این گره بعدی در پیمایش inorder را حذف نمایید.
برای حذف گره در درخت قرمز – سیاه همین قوانین را رعایت کنید. سرانجام یکی از دو حالت اول را خواهید داشت، (گره برگ است و یا گره حداقل یک فرزند دارد) فرض کنید، U گره ای باشد که باید حذف گردد، موارد زیر را انجام دهید:
► اگر U برگ است، آن را حذف میکنیم.
► اگر U تنها یک گره بنام V دارد، V را به جای U قرار میدهیم.
اگرU قرمز باشد، حذف آن هیچ کدام از قوانین درخت قرمز – سیاه را نقض نمیکند و کار به اتمام میرسد. اما اگر U سیاه باشد (و ریشه نباشد) حذف آن موجب نقض قانون شماره 2 مربوط به درخت قرمز – سیاه میشود، یعنی موجب میشود که تعداد گره های سیاه در تمام مسیرها یکسان نباشند. فرض میکنیم سیاهیی که U از دست میدهد به V داده شد و V دارای سیاهی مضاعف گردد. باید درخت را تنظیم کنیم تا این سیاهی اضافه به سمت بالای درخت هدایت شود و در جایی جذب گردد.
.gif)
