تعاریف زیر را برای درخت دودویی در نظر بگیرید:

تعریف ۱: یک درخت دودویی متشکل از تعدادی نقاط داخلی وتعدادی نقاط خارجی موسوم به گره‌ها می‌باشد. از هر گره داخلی دو گروه منشعب می‌گردند (گره چپ و گره راست) که با لبه‌های چپ و راست به آن متصل می‌شوند. از گره‌های خارجی هیچ گره‌ای منشعب نمی‌گردد. بطور مثال درخت دودویی زیر را در نظر بگیرید:

گره‌های مربع شکل گره‌های خارجی و گره‌های دایره‌ شکل گره‌های داخلی می‌باشند. گره ۱ موسوم به ریشه درخت می‌باشد.

تعریف ۲: طول یک مسیر از ریشه درخت $B$ به $u$ یک گره (داخلی یا خارجی) در درخت مساوی تعداد گره‌ها در مسیر منهای یک است. طول مسیر را با $l(u)$ نشان می‌دهیم.

در مثال بالا داریم: $l(5)=3$، $l(7)=2$ و $l(1)=0$

الف) فرض کنید $B$ یک درخت دودویی با $m$ گره خارجی $u_1,…,u_m$‌ باشد.

ثابت کنید: $\sum_{j=1}^m 2^{-l(u_j)}=1$

برای قسمت «ب» قرار دهید:

جمع طول مسیرها از ریشه به همه گره‌های خارجی=$\sum_u l(u)$ = $E(B)$

جمع طول مسیرها از ریشه به همه گره‌های داخلی= $\sum_u l(u)$ = $I(B)$

ب) ثابت کنید: $E(B)=I(B)+2n$

• سوال قبل