Рекурсив маълумотлар тузилмаси

Элемент ўчириш

• if(p->right==NULL) v=p->left;
• if((p->left!=NULL)&&(p->right!=NULL)){t=p; v=p->right; s=v->left;}
• while(s!=NULL){
• t=v;
• v=s;
• s=v->left;
• }

Элемент ўчириш

• if((t!=NULL)&&(t!=p)){
• t->left=v->right;
• v->right=p->right;
• v->left=p->left;
• }
• if(t==p) v->left=p->left;
• if(q==NULL){
• cout<info<<" ildiz\n";

Элемент ўчириш

• tree=v;
• delete(p);
• return tree;
• }
• if(p==q->left)
• q->left=v;
• else q->right=v;
• delete(p); // o’chirilgan element joylashgan xotira yacheykasini tozalash
• return tree;
• }

Бинар дарахтдан тугунни ўчириш

Бинар дарахтда қидирув

Бинар дарахтда қидирув

Мазкур процедуранинг вазифаси шундан иборатки, у берилган калит бўйича дарахт тугуни қидирувини амалга оширади. Қидирув операциясининг давомийлиги дарахт тузилишига боғлиқ бўлади. Ҳақиқатдан, агар элементлар дарахтга калит қийматлари ўсиш (камайиш) тартибида келиб тушган бўлса, у ҳолда дарахт бир томонга йўналган рўйхат ҳосил қилади (чиқиш даражаси бир бўлади, яъни ягона шоҳга эга), масалан:

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

Кидирув

• int search(node *tree, int key){
• node *next; next=tree;
• while(next!=NULL)
• { if (next->info==key){cout<<"Binar daraxtda "<
• if (next->info>key) next=next->left;
• else next=next->right;}
• cout<<"tuzilmada izlangan element yo ’ q!!!"<

АВЛ-дарахти

АВЛ-дарахтининг номи унинг муаллифлари исмлари бош харфларидан олинган бўлиб, улар – совет математиклари Георгий Максимович Адельсон-Вельский ва Евгений Михайлович Ландис, 1962 йил ушбу мувозанатланган АВЛ дарахтни таклиф этишган.