(۲۱ شهریور ۱۳۹۲ ۰۷:۰۳ ب.ظ)azk84 نوشته شده توسط:  

(21 شهریور ۱۳۹۲ ۰۶:۰۶ ب.ظ)tabassomesayna نوشته شده توسط:  سلام دوستان
در مورد سوال زیر :

غیر از روش حل از طریق مثال در کتاب آقای مقسمی , اثبات دقیقش اومده که من متوجهش نمیشم
کسی روش اثباتش رو بلده ؟

سلام.

اگه دقت کنیم می‌بینیم که نمیشه از درخت فقط یک گره حذف بشه، چون حتماً یک گره تک‌فرزندی خواهد شد. به عبارت دیگه همیشه درختی با شرط داده شده تعداد عناصرش باید فرد باشه. بنابراین میریم سراغ این که ببینیم رابطه‌ی (T(n برای درختی با دو گره‌ی کم‌تر به چه شکلی در میاد:

وقتی دو برگ از درخت T حذف بشه، یک گره‌ی غیر برگ تبدیل به برگ میشه (با توجه به شرط گفته شده برای درخت، هر دو برگ باید از یک گره حذف بشن و نه از گره‌های متفاوت). اگه این برگ‌ها توی عمق d باشند، (E(T-2 و (I(T-2 به این شکل در خواهند اومد:

[tex]E(T-2)=E(T)-(2\times d) (d-1)[/tex]
[tex]I(T-2)=I(T)-(d-1)[/tex]

دلیل این تغییرات اینه که دو برگ از عمق d کم میشن و یک برگ در عمق d-1 اضافه میشه (که قبلاً پدر اون دو برگ بوده).

بنابراین با این تغییرات مقدار (T(n-2 برابر میشه با:
[tex]T(n)=E(T)-I(T)\Rightarrow T(n-2)=E(T-2)-I(T-2)=E(T)-(2\times d) (d-1)-I(T) (d-1)=T(n)-2\Rightarrow T(n)=T(n-2) 2[/tex]

که میشه گزینه‌ی ۱ :-)

(۲۲ شهریور ۱۳۹۲ ۱۲:۱۳ ق.ظ)tabassomesayna نوشته شده توسط:  

(21 شهریور ۱۳۹۲ ۰۷:۰۳ ب.ظ)azk84 نوشته شده توسط:  

(21 شهریور ۱۳۹۲ ۰۶:۰۶ ب.ظ)tabassomesayna نوشته شده توسط:  سلام دوستان
در مورد سوال زیر :

غیر از روش حل از طریق مثال در کتاب آقای مقسمی , اثبات دقیقش اومده که من متوجهش نمیشم
کسی روش اثباتش رو بلده ؟

سلام.

اگه دقت کنیم می‌بینیم که نمیشه از درخت فقط یک گره حذف بشه، چون حتماً یک گره تک‌فرزندی خواهد شد. به عبارت دیگه همیشه درختی با شرط داده شده تعداد عناصرش باید فرد باشه. بنابراین میریم سراغ این که ببینیم رابطه‌ی (T(n برای درختی با دو گره‌ی کم‌تر به چه شکلی در میاد:

وقتی دو برگ از درخت T حذف بشه، یک گره‌ی غیر برگ تبدیل به برگ میشه (با توجه به شرط گفته شده برای درخت، هر دو برگ باید از یک گره حذف بشن و نه از گره‌های متفاوت). اگه این برگ‌ها توی عمق d باشند، (E(T-2 و (I(T-2 به این شکل در خواهند اومد:

[tex]E(T-2)=E(T)-(2\times d) (d-1)[/tex]
[tex]I(T-2)=I(T)-(d-1)[/tex]

دلیل این تغییرات اینه که دو برگ از عمق d کم میشن و یک برگ در عمق d-1 اضافه میشه (که قبلاً پدر اون دو برگ بوده).

بنابراین با این تغییرات مقدار (T(n-2 برابر میشه با:
[tex]T(n)=E(T)-I(T)\Rightarrow T(n-2)=E(T-2)-I(T-2)=E(T)-(2\times d) (d-1)-I(T) (d-1)=T(n)-2\Rightarrow T(n)=T(n-2) 2[/tex]

که میشه گزینه‌ی ۱ :-)

خیلی ممنون بابت توضیح کاملتون