15-maruza Chiziqsiz malumotlar tuzilmasi

 
 
C++ dasturlash tilida e’lon qilinishi: 
class Sublist{
//qismro’yhat elementlari toifasi 
int info; 
Sublist *next; 
} 
class Node{
//asosiy ro’yhat elementlari toifasi 
int info; 
Sublist *down; 
Node *next;
}
Chiziqsiz bog’langan tarmoqlanuvchi ro’yhat ustida asosiy amal bajarish 
algoritmlari: 
- asosiy ro’yhatga element kiritish; 
- elementga tegishli qismro’yhatga element kiritish; 
- asosiy ro’yhatdan element o’chirish; 
- qismro’yhatdan element o’chirish; 
- asosiy va qismro’yhatni bo’shlikka tekshirish; 
- element qidirish; 
Ro’yhatlarning kamchiligi bor: elementlarni qidirishda qat’iy ketma-ketlik 
mavjud. Qidirish davom ettiriladi toki element topilguncha yoki ro’yhat oxiriga 
yetguncha, agar element topilmasa. Shu masalani hal qilish uchun yuqorida 
aytilgan skip listlardan foydalaniladi. Bunda elementni qidirishda yoki unga 
murojaat qilishda ungacha bo’lgan xar bir element ko’rib chiqilmaydi.
n ta elementdan iborat skip list berilgan bo’lsin. Unda xar bir 1 ≤ k ≤ 
⎣lg 
n
⎦ va 1 ≤ i ≤ ⎣n/2
k–1
⎦ – 1 shartni qanoatlantiruvchi k va i  uchun 2
k-1
*i o’rinda 
turgan tugun 2
k-1
*(i+1) o’rinda turgan tugunni ko’rsatadi. Bu degani, xar bir 2-
tugun 2 tugun keyin turgan elementga murojaat qiladi va xar bir 4-element 
o’zidan 4 ta keyin turgan elementga murojaat qiladi va x.k. ( 6.5-quyidagi rasm) 
ko’rsatkich
ko’rsatkich 

---

6.5-rasm. Skip list tuzilmasi. 
Ushbu rasmdagi kabi skip listdan elementni qidirish algoritmi quyidagicha: 
(bizga ma’lumki, skip list tartiblangan) qidiruv eng yuqori ko’rsatkich bilan 
boshlanadi 
- Agar oldinda el elementdan qiymat jixatidan kichik elementlar 
chiqsa, qidiruv davom ettiriladi, toki el dan katta element chiqqunga 
qadar.
- Agar oldinda el dan katta element chiqadigan bo’lsa, bitta oldingi 
elementga qaytiladi va qidiruv bitta past darajadagi ko’rsdatkich 
bilan davom ettiriladi.
- Qidiruv element topilguncha davom ettiriladi yoki eng pastki 
darajadagi ko’rsatkich bilan oraliqdagi elementlarning xammasi 
tekshirilib chiqqanda to’xtatiladi. 
el elementni qidirish psevdokodi quyidagicha: 
search(element el) 
p=the nonnull list on the highest level i; 
while el not found and i≥0 
if p->key>el
p=a sublist that begins in the predecessor of p on level --i; 
else if p->key< el
if p is the last node on level i 
p=a nonnull sublist that begins in p on the highest level < i; 
i=the number of the new level; 
else p = p->next;
Masalan, agar bu ro’yhatda (6.5b-rasm) 16 ni qidiradigan bo’lsak, 4-
darajadan qidirishni boshlaymiz. Uning 1-elementi 28 ga olib boradi va bu 

---

darajada element topilmaydi, shu sababli bitta past darajadagi ko’rsatkich 
bo’yicha qidiramiz. Unda 1-element 8, demak kyingi elementni tekshiramiz, 2-
element 17, o’tib ketildi. Biz qidirayotgan element shu ikki element orasida 
bo’lishi mumkinligi sababli yana bitta past darajadagi ko’rsatkich bilan davom 
etamiz va bunda n8 va 17 orasidagi elementlar tekshiriladi. Bunda navbatdagi 
element 10 chiqadi va undan keyin yana 17. Shu sababli eng quyi darajaga tushib 
10 va 17 orasi qidiriladi. Unda 10, 12, 17 sonlari kelib chiqadi. Boshqa quyi 
darajadagi ko’rsatkich yuq va element shu paytgacha topilmagani uchun 
tuzilmada bu element yuq deb aytiladi.
Skip listlarni amalga oshirish va ustida amal bajarish algoritmlari dasturi 
quyida keltiriladi:

---

---

---

 
Bu skip listda qidirish samarali bo’lsada, kiritish va o’chirish algoritmlari 
ancha samarasizdir. Yangi element kiritilgan joydan keying barcha elemntlar 
qayta yozilib chiqiladi. Kiritiladigan ko’rsatkichli maydonlar soni va ularning 
qiymatlari xam o’zgartirilishi kerak. Skip list afzalligini saqlash va bunday 
muammolarni bartaraf etish maqsadida turli darajada turgan elementlarning 
turgan o’rni emas, ularning qiymatlari olib qaraladi. Masalan. 6.5-rasmdagi a) 
skip listdan b) skip list keltirilgan. Har ikkala tuzilmada xam 6 ta bitta 
ko’satkichli maydonga ega bo’lgan element mavjud, 2 ta ko’rsatkichli 3 ta 
element, 3 ta ko’rsatkichli 2 ta element va 4 ta ko’rsatkichli 1 ta element mavjud. 
Xosil qilingan yangi ro’yhat (6.5b.-rasm) da xam qidirish bir xil, lekin bunda 
yangi elementni kiritish qayta tashkil etishga majbur qilmaydi. Bunda elementlar 
shunday xosil qilinadiki, turli darajadaga elementlarni joylashda adekvatlik 
saqlanadi.
Bu qanday amalga oshiriladi? 

---

maxLevel=4 deb olaylik. 15 ta element uchun bitta ko’rsatkichli 8 ta element, 2 
ta ko’rsatkichli 2 ta element, 3 ta ko’rsatkichli 2 ta element, 4ta ko’rsatkichli 1 ta 
element yaratilishi kerak. Yangi element kiritiladigan bo’lsa, 1 va 15 orasida 
tasodifiy r soni xosil qilinadi. Agar r<9 bo’lsa, element eng quyi darajaga (1-
daraja) joylashadi, agar r<13 bo’lsa, element 2-darajaga joylashadi, agar r<15 
bo’lsa, element 3 - darajaga joylashadi va agar r=15 bo’lsa, element 4-darajaga
joylashadi.
Skip listning samaradorligi qanday? 
Ideal holatda 6.5.a-rasmda qidiruv samaradorligi O(lg n). eng yomon holatda, 
barcha elementlar bir xil darajada bo’lsa, bu oddiy chiziqli bog’langan ro’yhat 
kabi bo’ladi va qidiruv samaradorligi O(n) ga teng.


Nazorat savollar. 
1. Chiziqsiz malumotlar tuzilmasining o’ziga xosligi nimalardan iborat? 
2. Chiziqsiz malumotlar tuzilmasining klassifikasiyasi?
3. Daraxt va graf - chiziqsiz malumotlar tuzilmasi nima?.
4. Chiziqsiz tarmoqlanuvchi ro’yhat nima? 
5. Skip list nima? 
6. Skip listlarni dasturda ifodalanishi qanday? 
7. Skip list samaradorligi qanaqa? 
Adabiyotlar. 
1. AdamDrozdek. Data structure and algorithms in C++. Fourth edition. 
2013.Chapter 3.4. 96-106 betlar.
2. V.D.Daleka, A.S.Derevyanko, O.G.Kraves, L.Ye.Timanovskaya. 
Modeli i 
ctrukturы dannыx. uchebnoye posobiye. 
Xarkov:XGPU, 2000. - 241s. http://khpi-
iip.mipk.kharkiv.edu/library/datastr/book/prt05.html#lb54 

---