advertise laitec sharif univercity
دانلود مجموعه 70 پروژه مفید و کاربردی سی شارپ #C

دانلود مجموعه 70 پروژه مفید و کاربردی سی شارپ #C

12000 تومان
دانلود برنامه آزمون تستی در مالتی مدیا بیلدر MMb

دانلود برنامه آزمون تستی در مالتی مدیا بیلدر MMb

5000 تومان
دانلود پروژه پایانی طراحی وب سایت مخابرات با Asp.net

دانلود پروژه پایانی طراحی وب سایت مخابرات با Asp.net

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

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

5000 تومان
دانلود پروژه مدیریت کتابخانه با سی شارپ و SQL سرور

دانلود پروژه مدیریت کتابخانه با سی شارپ و SQL سرور

5000 تومان

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

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

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