ساختمان داده ها (درختان و درختان دودویی)

ساختمان داده ها (درختان و درختان دودویی)

اسلاید 1: ساختمان داده‌ها درختان و درختان دودویی

اسلاید 2: مرورمسأله: چگونه ساختارهای غیر خطی را نگهداری کنیم؟درخت دودویی:مثل لیست پیوندی است اما هر نود دو فرزند دارد. آهنگ رشد ارتفاع درخت دودویی لگاریتمی است. در هنگام جستجو و مرتب سازی خواص جالبی دارد. نودها همان اشیاء هستند.

اسلاید 3: ساختار درخت دودویی CEOVP of EngineeringVP of SalesHardwareVP of Marketing…Software…………………ریشهبرگها

اسلاید 4: درختشامل نودها ویالها است. از بالا به پایین رسم می شود.حلقه ندارد.برگهاریشه

اسلاید 5: واژگانوالد: A, B, D, Gفرزند: B, C, D, E, F, G, HSibling: {B, C, D}, {E, F}برگها: C, E, F, HABDFGHECسطح ۰سطح ۱سطح ۲سطح ۳

اسلاید 6: درخت جستجوی دودوییدرخت دودوییریشهزیردرخت سمت چپ زیردرخت سمت راستدر درخت دودویی ترتیب فرزندان مهم است. هر نود حداکثر دو فرزند دارد. عمق نود A برابر ۲ است.ارتفاع درخت برابر ۲است. DFBGECA

اسلاید 7: نمایش درختمثالی از درختABDFGHECAnullفرزند اولnext siblingBEnullHnullnullCnullDnullFnullnullGnull

اسلاید 8: درختان دودوییتعداد نودهای درخت دودویی به ارتفاع درخت و چگالی آن بستگی دارد. درخت خطی: هر نود فقط یک فرزند داشته باشد. درخت دودویی کامل: تمام برگها در دو سطح آخر درخت هستند. هر نود داخلی دقیقاً دو فرزند دارد. (به جز سمت چپ ترین نود سطح ما قبل آخر که می تواند یک فرزند داشته باشد. )

اسلاید 9: درخت دودویی کاملComplete Binary Tree (CBT)درخت دودوییتمام سطوح بجز سطح آخر پر هستند و دارای 2i نود هستند. تمام نودهای سطح آخر در سمت چپ ترین قسمت ممکن قرار دارند.

اسلاید 10: چند مثال از درخت دودویی که CBT نیستند.

اسلاید 11: رابطه ی بین CBT و آرایهاگر نودها را از بالا به پایین و از چپ به راست بشماریم یک آرایه خواهیم داشت.array: a b c d e f g h i jindex: 0 1 2 3 4 5 6 7 8 9bacihgdfej0123456789

اسلاید 12: تبدیلCBT به آرایهمی توانیم آرایه را به راحتی تبدیل به یک CBT کنیم. نودها را از بالا به پایین و از چپ به راست بخوانید. حال یک آرایه داریم. { 3, 10, 23, 42, 7, 21, 15, 19, 30}1032330191542217

اسلاید 13: تبدیل آرایه به CBTاگر یک آرایه داشته باشیم می توانیم یک CBT درست کنیم.آرایه: 3, 10, 23, 42, 7, 21, 15, 19, 30عناصر را از بالا به پایین و از چپ به راست بچینید.1032330191542217012345678

اسلاید 14: ایندکسهای آرایهArray: 3, 10, 23, 42, 7, 21, 15, 19, 30Index: 0 1 2 3 4 5 6 7 81032330191542217012345678indexleft child indexright child index012134256378………i??????Left child index = 2*i+1 ? Right child index = 2*i+2?

اسلاید 15: خواص CBTنودی که ایندکس آن برابر i است را در نظر بگیرید. پدر در محل (i-1)/2 دارد. فرزند سمت چپ در محل (2*i+1) قرار دارد. فرزند سمت راست در محل (2*i+2) قرار دارد. اگر تعداد نودها برابر n باشد:ارتفاع CBT برابر  log2(n + 1)  است. 1032330191542217012345678

اسلاید 16: مثالهای از درخت دودویی

اسلاید 17: درختان دودویی

اسلاید 18: خلاصهدرختان دودویی برای نمایش داده خیلی مفید هستند. ارتفاع CBT برابر O(log n) است که n تعداد نودها است. CBT ها را به راحتی می توان به آرایه تبدیل کرد. ما از درختان دودویی برای جستجو و مرتب سازی استفاده می کنیم.