سوال ۶
تعاریف زیر را برای درخت دودویی در نظر بگیرید:
تعریف ۱: یک درخت دودویی متشکل از تعدادی نقاط داخلی وتعدادی نقاط خارجی موسوم به گره‌ها می‌باشد. از هر گره داخلی دو گروه منشعب می‌گردند (گره چپ و گره راست) که با لبه‌های چپ و راست به آن متصل می‌شوند. از گره‌های خارجی هیچ گره‌ای منشعب نمی‌گردد. بطور مثال درخت دودویی زیر را در نظر بگیرید:
گره‌های مربع شکل گره‌های خارجی و گره‌های دایره شکل گره‌های داخلی می‌باشند. گره ۱ موسوم به ریشه درخت می‌باشد.
تعریف ۲: طول یک مسیر از ریشه درخت $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$