سلام

در جستجوی دودویی اگر کلید مورد نظر که داریم تو درخت دنبالش میکردیم پیدا بشه جستجو موفق هست و اگر پیدا نشه، ناموفق.

میشه این جستجوی دودویی رو با درخت دودویی نشون داد.
این درختی که میکشیم درخت تصمیم بهش میگن.
داخل هر نود مقدار mid نوشته میشه.
وقتی که به برگ ها برسیم یعنی جستجو ناموفق بوده (گره های مستطیلی)
و اگر در گره های داخلی کار تموم بشه یعنی جستجو موفق بود.

فرمولهایی که کاربردی هستن:

$E=I 2n$

$s(n)=\frac{I n}{n}$

$u(n)=\frac{E}{n 1}$

$s(n)=(1 \frac{1}{n})u(n)-1$

میانگین تعداد مقایسه در جستجوی موفق رو با $s(n)$ و میانگین تعداد مقایسه در جستجوی ناموفق رو با $u(n)$ نمایش میدن.
$I$ مجموع فاصله ی گره های داخلی از ریشه هست و $E$ مجموع طول مسیرهای خارجی.
$n$ تعداد گره های داخلی

یه عکس از کتاب پوران کشیدم پیوست کردم، که بهتر متوجه بشید.