advertise laitec sharif univercity
پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

148000 تومان
پروژه پایانی PHP وب سایت فروشگاه کامپیوتری

پروژه پایانی PHP وب سایت فروشگاه کامپیوتری

68000 تومان
دانلود سورس پروژه فروشگاه کیف با asp.net و sql express

دانلود سورس پروژه فروشگاه کیف با asp.net و sql express

10000 تومان
دانلود مقاله ای در مورد الگوریتم  کرم شب تاب FireFly در هوش مصنوعی

دانلود مقاله ای در مورد الگوریتم کرم شب تاب FireFly در هوش مصنوعی

10000 تومان
سیستم اتوماسیون دهیاری ، پروژه مهندسی نرم افزار

سیستم اتوماسیون دهیاری ، پروژه مهندسی نرم افزار

10000 تومان

ساختمان داده درختهای قرمز - سیاه red-black tree

ساختمان داده درختهای قرمز - سیاه RBT یکی از درختهای متوازن، که زمان جست وجو در آن مناسب میباشد است که راه حلی برای مسئله اداره کردن درختهای جست وجویی نامتوازن هستند.
ساختمان داده درختهای قرمز - سیاه 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 دارای سیاهی مضاعف گردد. باید درخت را تنظیم کنیم تا این سیاهی اضافه به سمت بالای درخت هدایت شود و در جایی جذب گردد.

 

 



0
نظرات

نظر خود را ارسال کنید



نام:
ایمیل:
دیدگاه:
captcha
کد امنیتی :


advertise
قوانین درخت قرمز سیاهآشنایی با درختهای قرمز و سیاهدرخت متوازن قرمز و سیاهخواص ساختمان داده درخت قرمز، سیاهحذف گره ای از درخت قرمز سیاهساختمان داده RBTدرج گره در درخت قرمز سیاهچگونه به درخت قرمز و سیاه گره جدید اضافه میشود؟الگوریتم درج در درخت قرمز سیاهred-black tree in data structureدرخت قرمز و سیاه چیست؟آموزش data structure درخت قرمز و سیاهچگونگی درج گره در ساختمان داده RBTساختمان داده red black tree لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

پیشنهادات ویژه سورس کد

پکیج ویژه پروژه پایانی رشته کامپیوتر دانلود مجموعه 70 پروژه کاربردی سی شارپ وب سایت فروشگاه با php