Ахборот тизимлари ва технологиялари Кириш

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

Келтирилган алгоритм рўйхат учун ҳам массив учун хам ўринли. Бироқ бу алгоритм массив учун тавсия қилинмайди, сабаби элементларни ўринлаштиришга кўрсаткичларни ўринлаштиришдан кўра анча кўп вақт талаб қилади.
Транспозиция усули
Ушбу усулда топилган элемент рўхатда битта олдинги элемент билан ўрин алмаштирилади. Агарда мазкур элементга кўп мурожаат қилинса, биттадан олдинга сурилиб бориб натижада рўйхат бошида бўлади.



Чизма. Қўшни элементларни ўрнини алмаштириш

р – ишчи кўрсаткич

q – ёрдамчи кўрсаткич, р дан битта қадам орқада бўлади
s - ёрдамчи кўрсаткич, q дан иккита қадам орқада бўлади
Ушбу усул нафақат рўйхатда, балки массивда хам қулай (сабаби фақатгина иккита ёнма-ён турган элемент ўрин алмаштирилади).

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

Агар ажратиб олинган элементлар қандайдир ўзгармас тўпламни ташкил қилишса, келгуси қидирувлар самаралироқ бўлиши учун уларни бинар дарахт кўринишида ифодалаш мақсадга мувофиқ бўлиши мумкин.
Қуйида келтирилган дарахтларда бинар қидирувни кўриб чиқайлик ( а)ва б) чизма). Иккала дарахт хам учтадан элементга эга - к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
Бирор бир берилган калитлар ва эхтимолликлар тўпламида кутилаётган таққослашлар сонини минималлаштирувчи бинар қидирув дарахти мукаммал дейилади. Гарчи дарахт яратиш алгоритми анча сермашаққат иш бўлсада, бироқ у яратган дарахтда қидувни амалга ошириш анча самарали бўлади. Афсуски, кўпинча, қидирув аргументи эхтимоллиги олдиндан аниқ бўлмайди.