پاورپوینت ساختمان داده ها و الگوريتم ها
نوع فایل:
پاورپوینت
قابل
ویرایش 44 اسلاید
درختهاي
قرمز و سياه (Red/Black
Trees) نوعي درخت جستجوي دودويي (Binary Search Tree)
است که هر گره آن علاوه بر فيلدهاي ديگر، يک بيت
رنگ نيز دارد
بيت رنگ
دوحالته (قرمز يا سياه) است
هدف از
اين بيت، تضمين توازن نسبي درخت است
در درخت
جستجوي دودويي، عمليات جستجو ، افزودن و حذف گره
هزينه اي متناسب با عمق درخت دارند.
عمق درخت
متوازن با N
گره از مرتبه O(log
N) است.
عمق درخت
نامتوازن با N
گره از مرتبه O(N) است.
RBT
= BST + 1 color bit
بقيه
مشخصات همانند BST است
ارث بري Inheritance
key, left, right, p.
هر گره
درخت دقيقا دو فرزند دارد
به جاي
فرزند نداشته، null استفاده مي کنيم
تمام
برگهاي تهي ( فرزنداني که وجود ندارند،) به رنگ سياه هستند
براي
مشخص نمودن برگهاي تهي ، يک گره کمکي nil مي سازيم و از آن به جاي تمام فرزندان تهي درخت استفاده مي
کنيم.
مشابه
گره first در ليستهاي پيوندي
برچسب ها:
پاورپوینت ساختمان داده ها و الگوريتم ها ساختمان داده ها و الگوريتم ها الگوريتم ها پاورپوینت ساختمان داده ها پاورپوینت الگوريتم ها