Мавзу – Кенглик, нарҳ, ички даража мезонлари. Икки-йўналтирилган излаш Режа

Иккиланган дарахт бўйича излаш

Ахборот излашнинг кўриб чиқилган энг тезкор усулларидан бири бинар излаш ҳисобланади. Лекин бу усул фақат баъзи бир чеклашлар билан қўлланилади: ундан фақат узунлиги қайдланган тартибга солинган ёзув массивларида маълумотлар кетма-кет тақдим этиладиган ҳолларда фойдаланиш мумкин, излаш жараёнида эса муайян ҳисоблашларни бажариш зарур. Шуни қайд этиб ўтиш керакки, кетма-кет тартибга солинган маълумотлар излаш учун қулай, юритиш учун ноқулай, чунки ёзувларни қўшиш ёки ўчиришда ҳар бир массивни қайта ёзиш талаб этилади.

Маълумотларнинг тузилиши иккиланган дарахт шаклида бўлгандагина маълумотларни боғланган тарзда тақдим этишдан фойдаланадиган массивларда тезкор излаш олиб бориш мумкин. Бундай массивларда тезкор излашдан ташқари ёзувларни киритиш ва ўчириш ҳам осон.
Иккиланган дарахт шаклидаги тузилмада излаш кўрсаткичлар кўрсатиб турадиган йўналишда олиб борилади. Бўғиннинг ўнг кўрсаткичи калити катта ёзувларга, чап кўрсаткич эса калити кичик ёзувларга олиб боради. Навбатдаги ёзув манзили ва номери бунда талаб этилмайди.
Биринчи мурожаат дарахт илдизига қаратилади. Бунда кейинги ҳар бир мурожаат қилишда излаш аргументи жорий бўғиннинг ёзуви калити билан солиштирилади ва кейинги мурожаат йўналиши аниқланади. Агар солиштириш натижасида излаш аргументи қиймати жорий бўғин ёзуви калитидан катта бўлса, кейинги мурожаат алоқанинг ўнг манзили бўйича қилинади, акс ҳолда, ўнг кичик дарахтдан чиққан бўғинга мурожаат қилинади.
Иккиланган мувозанатлаштирилган дарахт бўйича излашда солиштиришлар сони кам бўлади ва вақт ҳам кам талаб этилади. Мувозанатлаштирилган иккиланган дарахтда излашда солиштиришларнинг ўртача сони lоg2N га мутаносиб, бу ерда N – дарахт бўғинлари сони. Яхши мувозанатлашган дарахтда солиштиришларнинг энг катта сони дарахт даражалари сонига тенг бўлади.
Иккиланган дарахт бўйича излаш жараёнида янги элементни қўйиш мумкин бўлади. Дарахт тузилишига эга ёзувлар массивига калит 12 ли ёзувни қўйиш керак бўлсин. Излаш жараёнида тўртта солиштириш операциясидан кейин бундай калитли ёзув массивда мавжуд эмаслиги аниқланади. Агар ёзув жойлаштирилган хотира уясига калит 11 ли ўнг кўрсаткич ўрнатилса, бу ёзув тузилмага киритилган бўлади.
Дарахт бўйича излашда энг ёмон баҳолар олинади. Бу ҳолда солиштиришлар ўртача сони N/2, солиштиришларнинг энг юқори сони N га тенг бўлади, яъни бундай излаш тадрижий излашга ўхшаш бўлади.
Мувозанатлаштирилган иккиланган дарахт тузилмаси маълумотларнинг энг мослашувчан тузилмаси ҳисобланади. У массивни юритиш учун энг яхши имкониятларни (унинг чекланмаган ўсишини, ёзувларни тез қўйиш ва ўчириш), энг тез саралаш ва излашни таъминлаб беради.
struct node {
int data;
struct node* left;
struct node* right;
}
static int lookup(struct node* node, int tar-
get) {
if (node == NULL) {
return(false);
}
else {
// 2. see if found here
if (target == node->data) return(true);
else {
if (target < node->data) return(lookup(node-
>left,
target));
else return(lookup(node->right, target));
}
} }
Савол вa топшириқлар

1. Ахборот тизимларида ахборотларни излаш ишлари нимага асосан олиб борилади?

2. Интедллектуал тизимларга тушадиган сўров шакллантирилганда қандай аргументлар аниқланади?
3. Ахборот излашнинг қандай турлари мавжуд?
4. Излаш стратегияси тушунчасини таърифлаб беринг.
5. Кетма-кет излаш усулининг бошқа номини айтинг ва мазмунини тушунтириб беринг.
6. Икки йўналтирилган излаш маълумотларнинг қайси тузилишида қўлланилади?