Reja: Algoritm tushunchasi

Мукаммал қидирув дарахти

Агар ажратиб олинган элементлар қандайдир ўзгармас тўпламни ташкил қилишса, келгуси қидирувлар самаралироқ бўлиши учун уларни бинар дарахт кўринишида ифодалаш мақсадга мувофиқ бўлиши мумкин.

Қуйида келтирилган дарахтларда бинар қидирувни кўриб чиқайлик ( а)ва б) чизма). Иккала дарахт хам учтадан элементга эга - к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

Бирор бир берилган калитлар ва эхтимолликлар тўпламида кутилаётган таққослашлар сонини минималлаштирувчи бинар қидирув дарахти мукаммал дейилади. Гарчи дарахт яратиш алгоритми анча сермашаққат иш бўлсада, бироқ у яратган дарахтда қидувни амалга ошириш анча самарали бўлади. Афсуски, кўпинча, қидирув аргументи эхтимоллиги олдиндан аниқ бўлмайди.