Мундарижа Кириш

1.3.2. Бинар дарахт
Бинар дарахтлар ўзида шундай структурани намоён қиладики, унда ҳар бир тугун (ёки уч) иккитадан ортиқ бўлмаган ворис-тугун ва бир ота-она тугундан ташкил топган. Энг баланд тугун ота-онасиз бўлган ягона тугун ҳисобланади ва у илдиз тугун деб аталади. N тугундан иборат бинар дарахт (максимал тугунлар тахламида) дан кам бўлмаган даражага эга. Масалан, 15 тугундан иборат тўлиқ бинар дарахтда битта илдиз, иккинчи даражада иккита тугун, учинчи даражада тўртта тугун ва тўртинчи даражада саккизта тугун мавжуд. Бизнинг тенглигимиз ҳам даражани беради. Кўришимиз мумкин, дарахтга яна бир тугунни қўшиш янги даража ҳосил бўлишига олиб келади ва уларнинг сони га тенг. N тугундан иборат энг катта дарахтда N даража мавжуд: бу дарахтнинг ҳар қайси тугуни бир ворислик аниқлигида (ва дарахт оддий рўйхатни ўзида намоён қилади).
Агар дарахт даражаларини илдиз 1 даражада эканлигини ҳисобга олиб рақамласак, у ҳолда К рақамли даражада тугун ётади. Тўлиқ (1 дан j гача рақамланган) j даражали дарахтда барча барглар j - рақамли даражада ётади ва биринчидан то j-1гача даражадаги тугунларда иккитадан ворислар мавжуд. Тўлиқ j даражали дарахтда тугун мавжуд. Бу маълумотлар ва формулалар кейинчалик бизга анча ас қотади.
1.3.3. Эҳтимоллик
Биз алгоритмларни кирувчи маълумотларга боғлиқ равишда таҳлил қилмоқчимиз, бунинг учун у ёки бу кирувчи маълумотлар тўплами қанчалик тез учрашини баҳолашимиз керак. Айниқса, у ёки бу шартларни қондирадиган кирувчи маълумотлар эҳтимолликлари билан ишлашга тўғри келади. У ёки бу ҳодисанинг эҳтимоллиги ўзида нол ва бир орасидаги сонни билдиради, яъни 0 эҳтимоллик ҳодисанинг умуман рўй бермаслигини, 1 эҳтимоллик эса ҳодисани муқаррар рўй беришини билдиради. Агар бизга турли хил мумкин бўлган кирувчи қийматлар аниқлиги 10 га тенглиги маълум бўлса, у ҳолда биз тўлиқ ишонч билан айтишимиз мумкинки – ҳар бир бундай киришлар эҳтимоллиги 0 ва 1 орасида ва бу барча эҳтимолликлар йиғиндиси 1 га тенг ҳамда улардан бири албатта рўй бериши керак. Агар ҳар бир кириш рўй бериш имконияти бир хил бўлса , у ҳолда уларнинг ҳар қайсиси эҳтимоллиги 0.1 га (10 дан бири ёки 1/10) тенг.
Бизнинг таҳлилимиз кўпроқ барча имкониятларни ҳисобга олади ва уларнинг барчаси тенг эҳтимолли деб фараз қиламиз. Агар барча имкониятлар сони N га тенг бўлса, у ҳолда уларнинг ҳар қасиси эҳтимоллиги 1/ N га тенг.