Адабиётлар

 
Мукаммал қидирув дарахти 
Агар ажратиб олинган элементлар қандайдир ўзгармас тўпламни 
ташкил қилишса, келгуси қидирувлар самаралироқ бўлиши учун уларни 
бинар дарахт кўринишида ифодалаш мақсадга мувофиқ бўлиши мумкин. 
Қуйида келтирилган дарахтларда бинар қидирувни кўриб чиқайлик ( 
а)ва б) чизма). Иккала дарахт хам учтадан элементга эга - к1, к2, к3 бўлиб бу 
ерда к1<к2<к3. к3 элементни қидириш a) чизмада иккита таққослашни талаб 
қилса, б) чизмада эса битта. 
Бирор бир ѐзувни ажратиб олиш учун зарур бўлган калитларни 
таққослашлар сони бинар қидирув дарахтидаги ушбу ѐзув босқичига бирни 
қўшганига тенг.
Фараз қилайлик: 
қидирув аргументи key = к1 бўлиши эхтимоллиги - p1, 
қидирув аргументи key = к2 бўлиши эхтимоллиги – p3, 
қидирув аргументи key = к3 бўлиши эхтимоллиги – p3, 
key < к1 бўлиши эхтимоллиги – q0, 
к2 > key > к1 бўлиши эхтимоллиги – q1, 
к3 > key > к2 бўлиши эхтимоллиги – q2, 

---

―Маълумотлар тузилмаси ва алгоритмлар‖ фанидан маърузалар матни.
муаллиф: Б.Б.Акбаралиев 
key > к3 бўлиши эхтимоллиги – q3, 
C1 - a) чизмадаги таққослашлар сони, 
C2 - б) чизмадаги таққослашлар сони. 
Чизма а)
Чизма б) 
У ҳолда р1+ р2+ р3+ q0+ q1+ q2+ q3 = 1 
Бирор бир қидирувда кутилаѐтган таққослашлар сони қуйидагича бўлади: 
 
C1 = 2 р1+1 р2+2 р3+2 q0+2 q1+2 q2+2 q3 
C2 = 2 р1+3 р2+1 р3+2 q0+3 q1+3 q2+1 q3 
Бирор бир берилган калитлар ва эхтимолликлар тўпламида кутилаѐтган 
таққослашлар сонини минималлаштирувчи бинар қидирув дарахти мукаммал 
дейилади. Гарчи дарахт яратиш алгоритми анча сермашаққат иш бўлсада, 
бироқ у яратган дарахтда қидувни амалга ошириш анча самарали бўлади. 
Афсуски, кўпинча, қидирув аргументи эхтимоллиги олдиндан аниқ 
бўлмайди.