دانلود پاورپوینت درخت قرمز وسیاه در ساختمان داده

آرشیو کالا و خدمات

کتاب

پرفروش ترین ها

پر فروش ترین های فورکیا

پر بازدید ترین های فورکیا

پیوند ها

آمار بازدید

بازدید امروز : 599
بازدید دیروز : 898
بازدید کل : 3113732

دانلود پاورپوینت درخت قرمز وسیاه در ساختمان داده

دانلود پاورپوینت درخت قرمز وسیاه در ساختمان داده با فرمت ppt و در44 صفحه قابل ویرایش

قسمتی از متن پاورپوینت درخت قرمز وسیاه در ساختمان داده

Red-Black Trees (RBT)

درختهاي قرمز و سياه (Red/Black Trees) نوعي درخت جستجوي دودويي (Binary Search Tree) است که هر گره آن علاوه بر فيلدهاي ديگر، يک بيت رنگ نيز دارد lبيت رنگ دوحالته (قرمز يا سياه) است lهدف از اين بيت، تضمين توازن نسبي درخت است –در درخت جستجوي دودويي، عمليات جستجو ، افزودن و حذف گره هزينه اي متناسب با عمق درخت دارند. –عمق درخت متوازن با N گره از مرتبه O(log N) است. عمق درخت نامتوازن با N ‌ گره از مرتبه O(N) ‌است

lRBT = BST + 1 color bit

lبقيه مشخصات همانند BST است

–ارث بري Inheritance

–key, left, right, p.

هر گره درخت دقيقا دو فرزند دارد

– به جاي فرزند نداشته، null استفاده مي کنيم

lتمام برگهاي تهي ( فرزنداني که وجود ندارند،) به رنگ سياه هستند

–براي مشخص نمودن برگهاي تهي ، يک گره کمکي nil مي سازيم و از آن به جاي تمام فرزندان تهي درخت استفاده مي کنيم.

مشابه گره first ‌ در ليستهاي پيوندي

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

مثال RBT

توجه: هر گره درخت دقيقا دو فرزند دارد؛ به جاي فرزند نداشته، null استفاده مي کنيم

ارتفاع گره h(x) : ارتفاع يک گره برابر با طول بزرگترين مسير گره به برگهاي درخت است.

ارتفاع سياه گره x bh(x) : تعداد گرههاي سياه در هر يک از مسيرهايي است که از اين گره شروع مي شوند و به برگ null(T) ختم مي شوند

–برگ null(T) جزء مسير محسوب مي شود

–خود گره x جزء مسير محسوب نمي شود

ارتفاع سياه يک درخت RBT برابر با ارتفاع سياه ريشه آن است

لم1 : ارتفاع درخت RBT

لم1: طول بزرگترين مسير از يک گره به برگ حداکثر دو برابر طول کوتاهترين مسير است:

اثبات:

تعداد گرههاي‌ سياه روي مسيرهاي که از گره x‌شروع شده و به برگي مي رسند برابر bh(x) است ( خاصيت 5)

اگر طول کوتاهترين مسير را با s(x)‌نشان دهيم، bh(x) <= s(x)

بنابر خاصيت چهارم، روي مسيرهاي مذکور گرههاي قرمز متوالي وجود ندارند و همه مسيرها هم به گره سياه تمام مي شوند. بنابراين روي بلندترين مسير، ترتيب گرههاي قرمز و سياه حداکثر يک در ميان و به تعداد مساوي است: h(x) <= 2bh(x)

درنهايت h(x) <= 2s(x)

مبلغ واقعی ~~25,000 تومان~~ 40% تخفیف مبلغ قابل پرداخت 15,000 تومان

انتشار : ۲۰ مهر ۱۴۰۱ تعداد بازدید : 363

سایت http://30book.4kia.ir سایت دانلود کتاب ,دانلود مقاله,دانلود تحقیق ,دانلود گزارش کاراموزی ,دانلود طرح توجیهی ,دانلود پروژه ,دانلود پاورپوینت ,دانلود جزوه وغیره

پیوند ها

آمار بازدید

دانلود پاورپوینت درخت قرمز وسیاه در ساختمان داده

تمام حقوق مادی و معنوی این وب سایت متعلق به "" می باشد