advertise laitec sharif univercity استخراج بیت کوین با کامپیوتر استخراج بیت کوین با کامپیوتر
دانلود سورس هوش مصنوعی رنگ آمیزی گراف با ژنتیک در #C

دانلود سورس هوش مصنوعی رنگ آمیزی گراف با ژنتیک در #C

4800 تومان
دانلود پروژه وب سایت اشعار با ASP.NET و SQL

دانلود پروژه وب سایت اشعار با ASP.NET و SQL

3000 تومان
دانلود مجموعه 100 سورس ساده و ابتدایی با سی پلاس پلاس

دانلود مجموعه 100 سورس ساده و ابتدایی با سی پلاس پلاس

5000 تومان
دانلود PDF مجموعه 300 نکته جالب برنامه نویسی در سی شارپ #C

دانلود PDF مجموعه 300 نکته جالب برنامه نویسی در سی شارپ #C

3000 تومان
دانلود آپلود سنتر پیشرفته با PHP و Ajax

دانلود آپلود سنتر پیشرفته با PHP و Ajax

3000 تومان

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

تولید بیت کوین با کامپیوتر

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

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