الگوریتم جستجوی دودویی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
بدون خلاصۀ ویرایش |
|||
خط ۹:
فرض کنید داده ساختاری شامل مجموعه‌ای از اطلاعات نام٫ آدرس و شماره تلفن و غیره‌است و [[آرایه]] ای که نام‌ها را در بر دارد از ۱ تا N شماره گذاری شده‌است، یک در خواست می‌تواند این باشد: شماره فردی به نام X چند است. برای پاسخ دادن به این سوال [[آرایه]] مورد نظر باید جستجو شده و اندیس مربوط به نام داده شده در صورت وجود برگردانده شود، در این حالت شماره تلفن ذخیره شده در آرایه تلفن‌ها در این اندیس، همان شماره فرد X است و به همین ترتیب برای آدرس و غیره نیز می‌توان عمل کرد.
==خواص درخت دودویی==
n تعداد گره ها در یک درخت دودویی کامل است که با استفاده از این فرمول می توان یافت ''<math>n = 2^{h+1}-1</math>'' که در آن h عمق درخت است
N تعداد گره ها در یک درخت دودویی کامل است حداقل ''<math>n = 2^{h}</math>'' و حداکثر''<math>n = 2^{h+1}-1</math>'' که در آن h عمق درخت است
L تعدادی از گره های برگ در درخت دودویی کامل است که با استفاده از این فرمول می توان یافت ''<math>L = 2^h</math>'' که در آن L، تعدادی از گره های برگ در درخت است.
N تعداد گره ها در یک درخت دودویی کامل نیز می تواند یافت شود با استفاده از این فرمول ''<math>n = 2L-1</math>'' که در آن L، تعدادی از گره های برگ در درخت است.
تعدادی از لینک های تهی (فرزندان غایب از گره ها) در یک درخت دودویی کامل از n گره<math>(n+1)</math>
تعداد ''<math>n-L</math>'' از گره های داخلی در یک درخت دودویی کامل از n گره (گره های غیر برگ) <math>\lfloor n/2 \rfloor</math>.
برای هر درخت غیر تهی با گره های برگ <math>n_0</math> و <math>n_2</math> گره ها از درجه 2 <math>n_0 = n_2 + 1</math>.
اثبات:
N = تعداد کل گره
B = تعداد شاخه ها
:::''n''<sub>0</sub>, ''n''<sub>1</sub>, ''n''<sub>2</sub> برای نشان دادن تعداد گره بدون فرزند، تنها یک فرزند و دو فرزند بود
:::''B'' = ''n'' - 1 (از آنجا که تمام گره ها به جز گره ریشه از شاخه واحد)
:::''B'' = ''n''<sub>1</sub> + 2*''n''<sub>2</sub>
:::''n'' = ''n''<sub>1</sub>+ 2*''n''<sub>2</sub> + 1
:::''n'' = ''n''<sub>0</sub> + ''n''<sub>1</sub> + ''n''<sub>2</sub>
:::''n''<sub>1</sub>+ 2*''n''<sub>2</sub> + 1 = ''n''<sub>0</sub> + ''n''<sub>1</sub> + ''n''<sub>2</sub> ==> ''n''<sub>0</sub> = ''n''<sub>2</sub> + 1
== مثال ==
| |||