پاورپوینت درخت قرمز و سیاه در ساختمان داده (pptx) 44 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 44 اسلاید
قسمتی از متن PowerPoint (.pptx) :
Red-Black Trees
ساختمان داده ها و الگوريتم ها
Red-Black Trees (RBT)
درختهاي قرمز و سياه (Red/Black Trees) نوعي درخت جستجوي دودويي (Binary Search Tree) است که هر گره آن علاوه بر فيلدهاي ديگر، يک بيت رنگ نيز دارد
بيت رنگ دوحالته (قرمز يا سياه) است
هدف از اين بيت، تضمين توازن نسبي درخت است
در درخت جستجوي دودويي، عمليات جستجو ، افزودن و حذف گره هزينه اي متناسب با عمق درخت دارند.
عمق درخت متوازن با N گره از مرتبه O(log N) است.
عمق درخت نامتوازن با N گره از مرتبه O(N) است.
Red-black Tree(RBT)
RBT = BST + 1 color bit
بقيه مشخصات همانند BST است
ارث بري Inheritance
key, left, right, p.
هر گره درخت دقيقا دو فرزند دارد
به جاي فرزند نداشته، null استفاده مي کنيم
تمام برگهاي تهي ( فرزنداني که وجود ندارند،) به رنگ سياه هستند
براي مشخص نمودن برگهاي تهي ، يک گره کمکي nil مي سازيم و از آن به جاي تمام فرزندان تهي درخت استفاده مي کنيم.
مشابه گره first در ليستهاي پيوندي
Red-black Properties
هر گره درخت يا سياه است يا قرمز
ريشه درخت سياه است
هر گره تهي(null) سياه است
اگر گرهي قرمز باشد، هر دو فرزند آن سياه هستند
همه مسيرهايي که از يک گره شروع شده و به برگ مي رسند، دقيقا داراي تعداد مساوي گره سياه هستند.
مثال RBT
26
17
30
47
38
50
41
توجه: هر گره درخت دقيقا دو فرزند دارد؛ به جاي فرزند نداشته، null استفاده مي کنيم
ارتفاع (عمق) درخت RBT
ارتفاع گره h(x) : ارتفاع يک گره برابر با طول بزرگترين مسير گره به برگهاي درخت است.
ارتفاع سياه گره x bh(x) : تعداد گرههاي سياه در هر يک از مسيرهايي است که از اين گره شروع مي شوند و به برگ null(T) ختم مي شوند
برگ null(T) جزء مسير محسوب مي شود
خود گره x جزء مسير محسوب نمي شود
ارتفاع سياه يک درخت RBT برابر با ارتفاع سياه ريشه آن است
Height of a RBT
26
17
30
47
38
50
41
null[T]
h=4
bh=2
h=3
bh=2
h=2
bh=1
h=2
bh=1
h=1
bh=1
h=1
bh=1
h=1
bh=1
h: ارتفاع
bh:ارتفاع سياه
bh(x) ≤ h(x) ≤ 2 bh(x)
طول بلندترين مسير از يک گره به برگي از درخت، حداکثر دو برابر طول کوتاهترين مسير از همان گره به برگهاي درخت است.
لم1 : ارتفاع درخت RBT
لم1: طول بزرگترين مسير از يک گره به برگ حداکثر دو برابر طول کوتاهترين مسير است:
اثبات:
تعداد گرههاي سياه روي مسيرهاي که از گره xشروع شده و به برگي مي رسند برابر bh(x) است ( خاصيت 5)
اگر طول کوتاهترين مسير را با s(x)نشان دهيم، bh(x) <= s(x)
بنابر خاصيت چهارم، روي مسيرهاي مذکور گرههاي قرمز متوالي وجود ندارند و همه مسيرها هم به گره سياه تمام مي شوند. بنابراين روي بلندترين مسير، ترتيب گرههاي قرمز و سياه حداکثر يک در ميان و به تعداد مساوي است: h(x) <= 2bh(x)
درنهايت h(x) <= 2s(x)
تعداد گرههاي RBT
لم 2: تعداد گرههاي داخلي درختچه واقع در گره x حداقل برابر است با:2bh(x)–1.
اثبات ( با استفاده از استقرا رياضي)
اگر h(x)=0 ، آنگاه xبرگ است. و ارتفاع سياه آن نيز صفر است. در نتيجه تعداد گرههاي درختچه برابر 20 -1 = 0 است
اگر h(x) =h>0 و فرض کنيم ارتفاع سياه گره xبرابر bh(x) = b باشد:
هر کدام از فرزندان x ارتفاعي برابر با h-1 خواهند داشت. اگر فرزند درخت قرمز باشد، ارتفاع سياه آن b و در غير اين صورت b-1 خواهد بود
بنابر فرض استقرا هر درختچه شروع شده از فرزند x حداقل-1 2bh(x) -1 گره خواهد داشد و درنتيجه، درختچه واقع در x حداقل 2(2bh(x)-1 -1 ) + 1گره خواهد داشت
2 (2bh(x) – 1 – 1)+1= 2bh(x) – 1 تعداد گرههاي درختچه واقع در x