Kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti samarqand filiali

int avl_insert(struct avl_tree * tree, int item) 
{ 
 
struct avl_node ** v, *w, *x, *y, *z; 

---

143 
 
/* agar daraxtda hali tugunlar bo’lmasa */ 
 
v = &tree->root; 
 
x = z = tree->root; 
 
if(x == NULL) 
 
{ 
 
 
tree->root = new_node(tree,item); 
 
 
return tree->root != NULL; 
 
} 
 
/*1-holat */ 
/* keyin qo’yiladigan element uchun mumkin bo’lgan 
o’rinni qidirish */ 
 
for(;;) 
 
{ 
 
 
int dir; 
 
 
/*  agar  bunday  element  daraxtda  bo’lsa, 
funktsiya ishini tugutishi mumkin */ 
 
 
if(item == z->data) return 2; 
 
 
dir = (item > z->data) ; 
 
 
y = z->link[dir]; 
 
 
if(y == NULL) 
 
 
{ 
 
 
 
y 
= 
z->link[dir] 
= 
new_node(tree,item); 
 
 
 
if(y == NULL) return 0; 
 
 
 
break; 
 
 
} 
 
 
if(y->bal != 0) 
 
 
{ 

---

144 
 
 
 
 
v = &z->link[dir]; 
 
 
 
x = y; 
 
 
} 
 
 
z = y; 
 
} 
 
/* 2-holat */ 
/* 
qo’yish 
uchun 
talab 
qilingan 
tugunning 
muvozanatlash koeffitsientini hisoblash */ 
 
w = z = x->link[item > x->data]; 
 
while(z != y) 
 
 
if(item < z->data) 
 
 
{ 
 
 
 
z->bal = -1; 
 
 
 
z = z->link[0]; 
 
 
} 
 
 
else 
 
 
{ 
 
 
 
z->bal  = 
+1; 
 
 
 
z = z->link[1]; 
 
 
} 
 
/* 3-holat*/ 
/*  chap  qismdaraxtga  yangi  tugun  qo’yishda 
muvozanatlash */ 
 
if(item < x->data) 
 
{ 
 
 
if (x->bal != -1) 
 
 
 
x->bal --; 

---

145 
 
 
 
else if(w->bal == -1) 
 
 
{ 
 
 
 
*v=w; 
 
 
 
x->link[0] = w->link[1]; 
 
 
 
w->link[1] = x; 
 
 
 
x->bal = w->bal = 0; 
 
 
} 
 
 
else 
 
 
{ 
 
 
 
*v = z = w->link[1]; 
 
 
 
w->link[1] = z->link[0]; 
 
 
 
z->link[0] = w; 
 
 
 
x->link[0] = z->link[1]; 
 
 
 
z->link[1] = x; 
 
 
 
if(z->bal == -1) 
 
 
 
{ 
 
 
 
 
x->bal = 1; 
 
 
 
 
w->bal = 0; 
 
 
 
} 
 
 
 
 
 
 
else if(z->bal == 0) 
 
 
 
 
x->bal = w->bal = 0; 
 
 
 
else 
 
 
 
{ 
 
 
 
 
x->bal = 0; 
 
 
 
 
w->bal = -1; 
 
 
 
} 
 
 
 
z->bal=0; 
 
 
} 
 
} 

---

146 
 
/* 4-holat*/ 
/*  o’ng  qismdaraxtga  yangi  tugun  qo’yishda 
muvozanatlash */ 
 
else  
 
{ 
 
 
if( x->bal != +1) 
 
 
 
x->bal++; 
 
 
else if(w->bal == +1) 
 
 
{ 
 
 
 
*v = w; 
 
 
 
x->link[1] = w->link[0]; 
 
 
 
w->link[0] = x; 
 
 
 
x->bal = w->bal = 0;  
 
 
} 
 
 
else 
 
 
{ 
 
 
 
*v = z = w->link[0]; 
 
 
 
w->link[0] = z->link[1]; 
 
 
 
z->link[1] = w; 
 
 
 
x->link[1] = z->link[0]; 
 
 
 
z->link[0] = x; 
 
 
 
if(z->bal == +1) 
 
 
 
{ 
 
 
 
 
x->bal = -1; 
 
 
 
 
w->bal = 0; 
 
 
 
} 
 
 
 
else if(z->bal == 0) 
 
 
 
 
x->bal = w->bal = 0; 
 
 
 
else 

---

147 
 
 
 
 
{ 
 
 
 
 
x->bal = 0; 
 
 
 
 
w->bal = 1; 
 
 
 
} 
 
 
 
z->bal = 0; 
 
 
} 
 
} 
 
return 1; 
} 
avl_insert funktsiyasi juda katta hajmga ega, uni o’rganish uchun batafsil 
ko’rib  chiqish  kerak  bo’ladi.  6-listingdagi  1-holatda  AVL-daraxtga  tugun 
qo’shish  o’rnini  qidirish  berilgan.  Ushbu  holatda  vaqtinchalik  z  o’zgaruvchisi 
joriy tugunni qarab chiqish uchun qo’llanilgan. Agar qo’shiladigan tugun qiymati 
z tugun qiymatiga teng bo’lsa, u holda funktsiya o’z ishini yakunlaydi, ya’ni binar 
daraxtda bir xil qiymatli tugun bo’lishi mumkin emas.  
Keyin  y  o’zgaruvchisiga  zarur  qismdaraxtning  keyingi  tuguniga 
ko’rsatkich  yozilgan (agar qo’shiladigan tugun  qiymati  joriy  tugun  qiymatidan 
kichik bo’lsa chap qismdaraxt tuguniga, katta bo’lsa, o’ng qismdaraxt tuguniga 
ko’rsatkich).  Agar  y  NULL  ga  teng  bo’lsa,  u  holda  joriy  tugunda  kerakli 
qismdaraxtlar  mavjud  bo’lmaydi,  va  aynan  shu  yerdan  yangi  tugunni  qo’shish 
kerak  bo’ladi.  Yangi  tugunni  qo’shish  uchun  new_node  funktsiyasidan 
foydalanmiz. 
Listing 7. AVL-daraxtga yangi tugun qo’shish funktsiyasi 
struct avl_node * new_node(struct avl_tree * tree, 
int item) 
{ 
 
struct avl_node * node = malloc(sizeof * node); 
 
node->data = item; 
 
node->link[0] = node->link[1] = NULL; 

---

148 
 
 
node->bal = 0 ; 
 
tree->count ++ ; 
 
return node; 
}; 
1-holatdagi  x  va  v  o’zgaruvchilari  oxirgi  o’tilgan  tugunni  nol  bo’lmagan 
muvozanatlash  koeffitsienti  uchun  qo’llaniladi.  Xuddi  shunday  muvozanatlash 
koeffitsienti 0 ga teng bo’lsa, yangi tugunni qo’yishda u +1 yoki -1 ga o’zgaradi, 
bu  holda  muvozanatlash  talab  etilmaydi.  Agar  ushbu  koeffitsient  boshida  0  ga 
teng  bo’lmasa,  yangi  tugun  qo’shishdan  keyin  daraxtni  muvozanatlash  talab 
etiladi.  
Yangi  tugunni  qo’shishda  y  undan  yuqorida  turgan  tugun  uchun 
koefitsientni o’zgartirsa, u holda x va y tugunlari orasida joylashgan tugun uchun 
koefitsientni yangilash talab etiladi. Bu harakat 7-listingdagi 2-holatda bajariladi.  
6-listingdagi  3  –holatda  y  tugun  x  tugunning  chap  qismdaraxtida 
joylashgan  holatiga  mos  keladi.  Bunday  holda  x  muvozanatlash  koeffitsienti 
boshida -1 ga teng bo’ladi, yangi tugun qo’shilgandan keyin esa -2 ga teng bo’lib 
qoladi,  shuning  uchun  ham  muvozanatlashni  bajarish  talab  etiladi.  3-rasmda 
muvozanatlashning ikkita varianti keltirilgan.  

---

149 
 
 
3-rasm. Daraxtni muvozanatlashga misolar 
3-rasmning  yuqori  qismida  w  va  x  tugunlarni  o’ng  aylanish  bajariladi, 
shuning uchun ham w tuguni x tuguni o’rniga joylashadi. x tugun esa, w tuguni 
uchun  o’ng  o’g’il  tugun  bo’ladi,  natijada  daraxt  balandligi  tugun  qo’shishdan 
oldingi balandlikka teng bo’ladi. 3-rasmning pastki qismida ikki marta aylanish 
bajariladi –  birinchi  w  va  y  tugunlarning chap  aylanishi,  keyin  y  va  x  tugunlar 
uchun o’ng aylanish bajariladi.  
Listingdagi  4-holatda  y  tugunning  x  tugunning  o’ng  qismdaraxtida 
joylashgan bo’lsa, muvozanatlash holati bajariladi.  
 
8.4. AVL-daraxtdan tugunni o’chirish 
AVL-daraxtdan tugunni o’chirish oddiy binar daraxtdan tugun o’chirishga 
nisbatan ancha murakkab hisoblanadi va u quyidagi bosqichlardan iborat: 

---

150 
 
-  o’chirish  talab  qilinadigan  tugunni  qidirish;  keyingi  muvozanatlash 
amalni bajarish uchun qidirish jarayonida o’tilgan tugunlar eslab qolish; 
- topilgan tugunni o’chirish va o’tilgan tugunlar ro’yxatini yangilash; 
- muvozanatlashni bajarish va muvozanatlash koeffitsientini hisoblash. 
Listing 8. AVL-daraxtdan tugunni o’chirish funktsiyasi 
int avl_delete(struct avl_tree * tree, int item) 
{ 
 
struct avl_node * ap[32]; 
 
int ad[32]; 
 
int k = 1; 
 
struct avl_node ** y, * z; 
 
ad[0] = 0 ; 
 
ap[0] = (struct avl_node * ) &tree->root; 
 
z = tree->root; 
/* o’chirish uchun tanlangan tugunni qidirish */ 
 
for(;;) 
 
{ 
 
 
int dir; 
 
 
if(z == NULL) 
 
 
 
return 0 ; 
 
 
if (item == z->data) 
 
 
 
break; 
 
 
dir = item > z->data; 
 
 
ap[k] = z; 
 
 
ad[k++] = dir; 
 
 
z = z->link[dir]; 
 
} 
/* daraxtni tugunni o’chirish */ 
 
tree->count-- ; 

---

151 
 
 
y = &ap[k - 1]->link[ad[k-1]]; 
 
if(z->link[1] == NULL) 
 
 
*y = z->link[0]; 
 
else 
 
{  
 
 
struct avl_node *x = z->link[1]; 
 
 
if (x->link[0] == NULL) 
 
 
{ 
 
 
 
x->link[0] = z->link[0]; 
 
 
 
*y = x; 
 
 
 
x->bal = z->bal; 
 
 
 
ad[k] = 1; 
 
 
 
ap[k++] = x; 
 
 
} 
 
 
else 
 
 
{ 
 
 
 
struct avl_node *w = x->link[0]; 
 
 
 
int j = k++; 
 
 
 
ad[k] = 0 ; 
 
 
 
ap[k++] = x; 
 
 
 
while (w->link[0] != NULL) 
 
 
 
{ 
 
 
 
 
x = w; 
 
 
 
 
w = x->link[0]; 
 
 
 
 
ad[k] = 0 ; 
 
 
 
 
ap[k++] = x; 
 
 
 
} 
 
 
 
ad[j] = 1; 
 
 
 
ap[j] = w; 

---

152 
 
 
 
 
w->link[0] = z->link[0]; 
 
 
 
x->link[0] = w->link[1]; 
 
 
 
w->link[1] = z->link[1]; 
 
 
 
w->bal = z->bal; 
 
 
 
*y = w; 
 
 
} 
 
} 
 
free(z); 
/* olingan daraxtni muvozanatlash */ 
 
while(--k) 
 
{ 
 
 
struct avl_node *w, *x; 
 
 
w = ap[k];   
 
 
if (ad[k] == 0 ) 
 
 
{ 
 
 
 
if (w->bal == -1) 
 
 
 
{ 
 
 
 
 
w->bal = 0; 
 
 
 
 
continue; 
 
 
 
} 
 
 
 
else if (w->bal == 0 ) 
 
 
 
{ 
 
 
 
 
w->bal = 1; 
 
 
 
 
break; 
 
 
 
} 
 
 
 
x = w->link[1]; 
 
 
 
if (x->bal > -1) 
 
 
 
{ 
 
 
 
 
w->link[1]= x->link[0]; 

---

153 
 
 
 
 
 
x->link[0] = w; 
 
 
 
 
ap[k-1]->link[ad[k-1]] = x; 
 
 
 
 
if (x->bal == 0 ) 
 
 
 
 
{ 
 
 
 
 
 
x->bal = -1; 
 
 
 
 
 
break; 
 
 
 
 
} 
 
 
 
 
else 
 
 
 
 
 
w->bal = x->bal = 0 ; 
 
 
 
} 
 
 
 
else 
 
 
 
{ 
 
 
 
 
z = x->link[0]; 
 
 
 
 
x->link[0] = z->link[1]; 
 
 
 
 
z->link[1] = x; 
 
 
 
 
w->link[1] = z->link[0]; 
 
 
 
 
z->link[0] = w; 
 
 
 
 
if (z->bal == 1) 
 
 
 
 
{ 
 
 
 
 
 
w->bal = -1; 
 
 
 
 
 
x->bal = 0; 
 
 
 
 
} 
 
 
 
 
else if (z->bal == 0 ) 
 
 
 
 
 
w->bal = x->bal = 0; 
 
 
 
 
else 
 
 
 
 
{ 
 
 
 
 
 
w->bal = 0; 
 
 
 
 
 
x->bal = 1; 
 
 
 
 
} 

---

154 
 
 
 
 
 
z->bal = 0; 
 
 
 
 
ap[k-1]->link[ad[k-1]] = z; 
 
 
 
} 
 
 
} 
 
 
else 
 
 
{ 
 
 
 
if (w->bal == 1) 
 
 
 
{ 
 
 
 
 
w->bal = 0 ; 
 
 
 
 
continue; 
 
 
 
} 
 
 
 
else if (w->bal ==0) 
 
 
 
{ 
 
 
 
 
w->bal = -1; 
 
 
 
 
break; 
 
 
 
} 
 
 
 
x = w->link[0]; 
 
 
 
if (x->bal < 1) 
 
 
 
{ 
 
 
 
 
w->link[0] = x->link[1]; 
 
 
 
 
x->link[1] = w; 
 
 
 
 
ap[k-1]->link[ad[k-1]] = x; 
 
 
 
 
if (x->bal == 0 ) 
 
 
 
 
{ 
 
 
 
 
 
x->bal = 1; 
 
 
 
 
 
break; 
 
 
 
 
} 
 
 
 
 
else 
 
 
 
 
 
w->bal = x->bal = 0; 

---

155 
 
 
 
 
} 
 
 
 
else if (x->bal == 1) 
 
 
 
{ 
 
 
 
 
z = x->link[1]; 
 
 
 
 
x->link[1] = z->link[0]; 
 
 
 
 
z->link[0] = x; 
 
 
 
 
w->link[0] = z->link[1]; 
 
 
 
 
z->link[1] = w; 
 
 
 
 
if (z->bal == -1) 
 
 
 
 
{ 
 
 
 
 
 
w->bal = 1; 
 
 
 
 
 
x->bal = 0; 
 
 
 
 
} 
 
 
 
 
else if (z->bal == 0 ) 
 
 
 
 
 
w->bal = x->bal = 0 ; 
 
 
 
 
else 
 
 
 
 
{ 
 
 
 
 
 
w->bal = 0 ; 
 
 
 
 
 
x->bal = -1; 
 
 
 
 
} 
 
 
 
 
z->bal = 0; 
 
 
 
 
ap[k-1]->link[ad[k-1]] = z; 
 
 
 
} 
 
 
} 
 
} 
 
return 1; 
}
 

---

156 
 
Bu  funktsiyaning  boshida o’chirilishi kerak bo’lgan  tugun qidiriladi.  Har 
bir o’tilgan z tugun item ning butun qiymati bilan taqqoslanadi. O’tilgan tugunlar 
ap massivga joylatiriladi, harakat yo’nalishi esa ad massivda saqlanadi.  
Shundan keyin daraxtdan tugunni o’chirish bajariladi, buning uchun oddiy 
binar  daraxtdan  tugunni  o’chirishning  3  ta  variantidan  biri  qo’llaniladi.  Lekin, 
AVL-daraxt  uchun  qo’shimcha  ravishda  o’chirilgan  tugundan  oldin  (yuqori)da 
joylashgan  tugunlar  ro’yxatini  saqlab  borish  kerak.  O’chirishdan  keyin 
muvozanatlash  amal  bajariladi,  bu  xuddi  yangi  tugun  qo’shishdan  keyin 
bajarilganga  o’xshash,  faqat  bunda  o’ng  va  chap  qismdaraxtlar  bo’yicha  emas, 
balki o’chirilgan tugundan yuqorida joylashgan tugunlar bo’yicha muvozanatlash 
amal bajariladi. 
  
Xulosa 
AVL-daraxtning  qidirishdagi  afzalliklariga  qaramasdan,  tugun  qo’shish 
yoki  o’chirish  amallarini  bajargandan  keyin  uni  muvozanatlash  masalasi  juda 
murakkab  hisoblanadi.  Muvozanatlash  algoritmi  asosiy  muammolardan  biri 
hisoblanadi,  chunki  bu  algoritmni  noto’g’ri  qo’llash  natijasida  ishlab  chiqilgan 
dastur  unumdorligi  pasayib  ketishi  mumkin.  Ushbu  mavzuda  AVL-daraxtlar 
ustida bajariladigan amallar: hosil qilish, tugunni qo’shish, o’chirish algoritmlari 
C  tilidagi varianti  berildi.  Foydalanuvchi  ushbu  algoritmlarning  Python  tilidagi 
variantini mustaqil o’rganib olishi mumkin.  
Listing 8. AVL-daraxtning unumdorligini testlash 
int main() 
{ 
   struct avl_tree * my_tree = tree_create(); 
   int res = 0; 
   int i = 0 ; 
   int rnd = 0; 
   int count = 10000000; 

---

157 
 
   time_t start,time2; 
   volatile long unsigned t; 
   start = time(NULL); 
   srand (time (NULL)); 
   for( i = 0; i < count; i++)  
   { 
     rnd = (rand() % count); 
     res = avl_insert(my_tree, rnd); 
     if(my_tree->count==5000000) break; 
   } 
  time2 = time(NULL); 
  printf("\n  sarflangan  vaqt  %f  sekund.\n", 
difftime(time2, start)); 
  printf("\n  balandlik=%d  tugunlari  soni  =%d\n", 
height(my_tree->root),my_tree->count); 
  return 0 ; 
 } 
 
 
 
 
 
 
 
 
 
 
 
 

---

158 
 
Adabiyotlar ro’yxati 
1. 
Яковлев  C. 
Работа со структурами данных в языках Си и Python. 
/Интернет 
ресурс: 
https://www.ibm.com/developerworks/ru/library/l-
data_structures_01/index.html 
2.  Robergé,  Jim.  A  laboratory  course  in  C++  data  structures  /  James 
Robergé, Stefan Brandle, David Whittington. p. 431. 2003. ISBN 0-7637-1976-
5. 
3. Weiss, Mark Allen. Data structures and algorithm analysis in C++ / Mark 
Allen Weiss, Florida International University. — Fourth edition. p.654. ISBN-13: 
978-0-13-284737-7. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

---

159 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

---

160