Ma'lumotlar tuzilmalarini doimiyga o'tkazish usullari

Загружено в:

12.08.2023

Скачано:

0

Размер:

1451.818359375 KB

Скачать

1

Mundarija
I Kirish ………… … …… …… …………………… …...…... ………… ……… .2
II Asosiy qism …………………………………..…… …………………… ..3
2.1 Ma'lumotlar tuzilmalarini doimiyga o'tkazish usullari … ………….… ..3
2.2 Doimiy to'plam … ……………………………………………………... .8
23 Doimiy navbat ……………………………………… ……………… … 13
2. 4 Doimiy pastki ………………………………………………………... .24
2.5 Doimiy ustuvor navbat ……………………………………………….. .29
III Xulosa ………………………………………………… ……………… … 38
IV Foydalanigan adabiyotlar …………………………… ……………... 39

2

Kirish
Doimiy ma'lumotlar strukturasi - har qanday o'zgartirishl ar kiritilganda
o'zining avvalgi holatini va ushbu holatlarga kirish huquqini saqlab qolgan
ma'lumotlar tuzilmasi. To'liq doimiy ma'lumotlar tuzilmalarida siz nafaqat oxirgi,
balki ma'lumotlar tuzilmalarining istalgan versiyasini o'zgartirishingiz mumkin,
shuningdek, istalgan versiyaga so'rovlar qilishingiz mumkin.
Birlashtirilgan ma'lumotlar tuzilmalari ikkita ma'lumotlar tuzilmasini bittaga
(birlashtirilishi mumkin bo'lgan qidiruv daraxtlari) birlashtirishga imkon beradi.
Funktsional ma'lumotlar tuzilmala ri ta'rifi bo'yicha to'liq barqarordir, chunki
ular halokatli topshiriqlarga ruxsat bermaydi, ya'ni. har qanday o'zgaruvchiga faqat
bir marta qiymat berilishi mumkin va uni o'zgartirib bo'lmaydi. Agar ma'lumotlar
strukturasi funksional bo'lsa, u holda u qo 'shiladi, agar u qo'shilgan bo'lsa, u butunlay
doimiy, agar u to'liq doimiy bo'lsa, u ham qisman doimiydir. Shu bilan birga,
funktsional emas, balki birlashuvchi ma'lumotlar tuzilmalari mavjud.

3

2.1 Ma'lumotlar tuzilmalarini doimiyga o'tkazish usullar i
Ha r qanday tuzilmani barqaror qilishning bir necha yo'li mavjud:
 to'liq zaxira nusxasi (ingl. full copy ) har qanday o'zgartirish
operatsiyasi uchun ma'lumotlar strukturasi to'liq nusxalanganda, natijada yangi
nusxa o'zgartiriladi,
 yuqoriga yo'l (ingliz. Pat h copying ),
 fat node usuli .
Qisman qat'iyat bilan boshlaylik. Aniqlik uchun ma'lumotlar tuzilmalarining
turli versiyalarini raqamlaymiz. Ma'lumotlar strukturasidagi o'zgarishlar tarixi
chiziqli bo'lib, istalgan vaqtda ma'lumotlar strukturasining istalgan versiyasiga
murojaat qilishingiz mumkin, lekin faqat oxirgi versiyasini o'zgartirish mumkin (u
rasmda ko'k rang bilan ta'kidlangan) (1 -rasm) .

1-rasm
Keling, ma'lumotlar strukturasi nima ekanligini aniqlaylik. Bizning
tushunchamizda ma'lumotlar strukturas i ba'zi ma'lumotlar saqlanadigan va bu
tugunlar havolalar bilan bog'langan tugunlar to'plami deb ataladi. Ma'lumotlar
strukturasiga misol daraxtdir . Keling, yo'lni nusxalash orqali daraxtni qanday qilib
barqaror qilishni ko'rib c hiqaylik.
Yo'ldan nusxa ko'chirish usuli
Bir bor bo'lsin muvozanatli qidiruv daraxt . Undagi barcha operatsiyalar uchun
baja riladi O ( h ), qayerda h - daraxtning balandligi va daraxtning
balandligi O ( logn ), qayerda n -uchlari soni. Aytaylik, bu muvozanatli daraxtda
qandaydir yangilanishni amalga oshirish kerak, masalan, boshqa element qo'shing,
lekin ayni paytda eski darax tni yo'qotmaslik kerak. Yangi bola qo'shmoqchi bo'lgan

4

tugunni oling. Yangi tugunni qo'shish o'rniga, biz ushbu tugunni nusxalaymiz,
nusxaga yangi bola qo'shamiz, shuningdek, barcha ko'rsatkichlar bilan birga birinchi
ko'chirilgan tugunga erishish mumkin b o'lgan ildizgacha bo'lgan barcha tugunlarni
nusxalaymiz. Biz o'zgartirilgan tugunga etib bo'lmaydigan barcha burchaklarga
tegmaymiz. Yangi tugunlar soni har doim logarifm tartibida bo'ladi. Natijada, biz
daraxtning ikkala versiyasiga kirish imkoniyatiga eg amiz (2 -rasm) .

2-rasm
Biz muvozanatli qidiruv daraxtini ko'rib chiqayotganimiz sababli,
muvozanatlash paytida cho'qqini yuqoriga ko'taramiz, siz aylanishlarda ishtirok
etuvchi barcha cho'qqilarning nusxalarini yaratishingiz kerak, ular uchun bolalarga
hav olalar o'zgartirildi. Bundaylar har doim uchtadan ko'p emas, shuning uchun
asimptotiklar O ( log n ) azob chekmaydi. Balanslash tugagach, yo'l bo'ylab
cho'qqilarning nusxalarini yaratib, ildizga ko'tarilish kerak.
Bu o'zgartirganda, qo'shish operatsiyasi j uda qimmatga tushadi, chunki
element boshqa barcha elementlardan kirish mumkin bo'lgan navbatning dumiga

5

qo'shiladi. Agar ma'lumotlar tuzilmasi ota -onaga havolalar mavjud bo'lsa, ushbu
usuldan foydalanish foydali emas.

Segmentlar daraxtini amalga oshirish
Segment daraxtiga asoslanib, siz to'liq doimiy ma'lumotlar strukturasini
yaratishingiz mumkin.
Segmentlarning doimiy daraxtini amalga oshirish uchun daraxtning tuzilishini
biroz o'zgartirish qulay. Buning uchun biz aniq mayoqlar foydalanish va bolalar
uch un. Bundan tashqari, biz versiya segmentlari daraxtining ildiziga
ishora qiladigan massiv yaratamiz
Elementlardan doimiy segmentlar daraxtini yaratish uchun daraxtning so'nggi
versiyasiga element qo'shish operatsiyasini qo'llash kerak . Daraxtning -th
vers iyasiga yangi element qo'shish uchun siz uning to'liq ikkilik ekanligini
tekshirishingiz kerak. Ha bo'lsa, unda yangi ildiz yarating, chap o'g'il qiling... Aks
holda, biz asl nusxaning ildiz nusxasini yaratamiz. Keling, ildizlar qatorining oxiriga
ildiz qo 'shamiz. Bundan tashqari, ildizdan birinchi bo'sh barggacha tushib, biz
mavjud bo'lmagan tugunlarni yaratamiz va mavjudlarini klonlaymiz. Shundan so'ng,
yangi filialda siz funktsiyaning qiymatini va bola elementlarining ba'zi
ko'rsatkichlarini yangilashing iz kerak. Shuning uchun, rekursiyadan qaytib, biz bitta
ko'rsatgichni yangi yaratilgan yoki ko'chirilgan cho'qqiga o'zgartiramiz, shuningdek,
daraxt qurilgan funktsiyaning qiymatini yangilaymiz. Ushbu operatsiyadan so'ng,
kiritilgan elementni o'z ichiga ol gan daraxtda yangi versiya paydo bo'ladi.
Segmentlarning doimiy daraxtidagi elementni o'zgartirish uchun siz
quyidagilarni qilishingiz kerak: daraxt bo'ylab kerakli versiyaning ildizidan kerakli
elementga o'ting, uni nusxalang, qiymatni o'zgartiring va dar axt bo'ylab yuqoriga
chiqing. , biz tugunlarni klonlaymiz. Bunday holda, oldingi klonlash paytida
yaratilgan tugunga ko'rsatgichni bolalardan biriga o'zgartirish kerak. Ildizdan nusxa
olgandan so'ng, ildiz qatorining oxiriga yangi ildiz qo'shing (3 -rasm) .

6

3-rasm
Bu erda dastlab 3 ta uchi bo'lgan minimal operatsiyaga ega doimiy segment
daraxti ko'rsatilgan. Avval unga qiymati 2 bo'lgan cho'qqi qo'shilgan, keyin esa 7
qiymatli cho'qqi o'zgartirilgan.Qirra va cho'qqilarning rangi ularning paydo bo'lish
vaqtig a mos keladi. Elementlarning ko'k rangi ularning aslini, yashil - qo'shgandan
keyin paydo bo'lganligini va to'q sariq rang - element o'zgartirilgandan keyin paydo
bo'lganligini anglatadi.
Qalin tugun usuli
Aytaylik, ma'lumotlar tuzilmasida siz o'zgartirish kiritishingiz kerak bo'lgan
tugun mavjud (masalan, quyidagi rasmda, ma'lumotlar strukturasining birinchi
versiyasida tugunda maydon mavjud, ikkinchi versiyada esa bu maydon). teng
bo'lishi kerak ), lekin ayni paytda siz tugunning eski versiyasiga kirishni saqlab
qolishingiz kerak va vaqtni tejashga hojat yo'q. Bunday holda, siz tugunning ikkala
versiyasini katta kombinatsiyalangan tugunda saqlashingiz mumkin (4 -rasm) .

7

4-rasm
Yuqoridagi misolda, bu "yog'li" tugun birinchi versiyani saqlaydi , ikkinchi
ver siyaga ega bo'lgan . Agar keyingi o'zgarishlar bo'lsa
(masalan, tugun maydoni teng bo'ladi ), qalin tugunga boshqa versiyani
qo'shing – (5 -rasm) .

5-rasm
Aytaylik, siz ma'lumotlar strukturasining ikkinchi versiyasiga so'rov
yuborishingiz kerak (yuqorida gi rasmda bu so'rov . Ushbu so'rovni amalga oshirish
uchun siz tugunga borishingiz va versiyalar ro'yxatidan kamroq bo'lgan maksimal
versiyani topishingiz kerak. so'rov versiyasiga teng yoki unga teng (rasmdagi
misolda bu versiya ) va tugunning ushbu versi yasida maydon qiymatini
toping (misolda ). Kerakli versiyani tezda topish uchun "qalin" tugunda
saqlanadigan versiyalar ro'yxati, siz ularni daraxt shaklida saqlashingiz kerak. Keyin
logarifm uchun kerakli versiyani topib, unga murojaat qilishimiz mumkin. Ushbu
ma'lumotlar strukturasida bajariladigan operatsiyalar ko'paytiriladi. versiyalar
sonining logarifmi bo'yicha.
Qalin tugunning tuzilishi har xil bo'lishi mumkin: har bir tepada siz uning
o'zgarishlar jurnalini saqlashingiz mumkin, bu o'zgarish sodir b o'lgan versiyani,
shuningdek o'zgarishning o'zini qayd qiladi. Qalin tugunning bunday tuzilishi
quyida qisman va to'liq doimiy ma'lumotlar tuzilmalarini olishning umumiy usullari
bo'limlarida ko'rib chiqiladi. Jurnal turli yo'llar bilan tashkil etilishi mu mkin. Odatda
har bir tepalik maydoni uchun alohida jurnal tuziladi. Cho'qqida biror narsa
o'zgarganda, bu o'zgarish va bu o'zgarish sodir bo'lgan versiya raqami tegishli
maydonning jurnalida qayd etiladi. Qachonki eski versiyaga murojaat qilishingiz
kerak bo'lsa, keyin ikkilik qidiruvdan foydalanib, ular ushbu versiyaga oxirgi

8

o'zgartirish kiritish uchun jurnalga qarashadi va kerakli qiymatni
topadilar. Yog'tugunining usuli sekinlashuvni beradi , bu erda ma'lumotlar
tuzilishidagi o'zgarishlar soni; xotira t alab qilinadi , bu yerda ma'lumotlar
strukturasidagi uchlari soni.

9

2.2 Doimiy to'plam
Massivni amalga oshirish
Keling, stekni o'zgartiruvchi so'rovlar qatorini yarataylik.
struct Query :
T value
uint prev
Massivning har bir elementida maydonlar b o'ladi: stekning yuqori qismidagi
qiymat va ste kning oldingi versiyasi indeksi
Keyin surish va pop operatsiyalari quyidagicha ko'rinadi:
 Push( i, x ) - bir elementni qo'shimchalar bir qator suyakka uchun ,
natijada to'p bir raqami bo'ladi ,
 function push(i : uint , x : T):
 s.top = s.top + 1
 s[s.top].value = x
 s[s.top].prev = i
 pop (i)- raqamlangan elementda saqlangan qiymatni qaytaradi va
oldingi elementni uning uchun nusxalaydi, natijada stek raqamlanadi .
 T pop(i : uint ):
 Query k = s[i]
 k = s [k.prev]
 push(k.prev, k.value)
 return s[i].value
Ro'yxatda amalga oshirish

10

Biz qiymat va stekning oldingi versiyasiga havolaga ega bo'lgan tugundan
foydalanamiz. Bunday holda, tugunning o'zi stekning versiyasidir.
struct Node :
T value
Node pr ev
Biz holatlarni tugunlarda saqlaymiz. Joriy cho'qqi haqidagi ma'lumotni
foydalanuvchiga qaytaramiz.
Har bir tugunda maydonlar bo'ladi: stekning yuqori qismidagi qiymat va stekning
oldingi versiyasiga havola.
Doimiy to'plamning o'zi belgilanadi .
 push (i,x)- tugun stekiga element qo'shadi ,
Stack push(i : Node , x : T):
k.value = x
k.prev = i
s.top = k
return s
 push (i)- tugunda saqlangan qiymatni qaytaradi va unga oldingi
elementni ko'chiradi.
pair<T, Stack> pop(i : Node ):
T val = i.value
i = i.prev
return pair(val, s)

11

K eling, dastlab bitta bo'sh stekga ega bo'lamiz. Keling, uni massivga yozamiz
(6-rasm ).
6-ras m

1- ga tegishli qiymat bilan yangi cho'qqi yaratiladi , uni mas sivning 2 -
yacheykasiga qo'ying (7-rasm ):
in deks Bitta 2
qiymat 3
oldingi Bitta
7-rasm
Keling, shunga o'xshash tarzda bajaramiz (8-rasm ):
Indeks bitta 2 3
Q iymat 3 5
O ldingi Bitta 2
Keling, qilaylik . U 2-cho'qqini qaytaradi va nusxalaydi (9-rasm ).
Indeks Bitta
Q iymat
O ldingi

12

indeks Bitta 2 3 4
qiyma t 3 5 3
oldingi Bitta 2 bitta
9-rasm
Amallar ketma -ketligidan keyin massiv shunday ko'rinishga ega bo'ladi (10-rasm )

indeks bitta 2 3 4 5 6 7 Sakkiz 9
qiymat 3 5 3 6 bitta 5 9
oldingi Bitta 2 Bitta 3 5 2 7
10-rasm

13

2.3 Doimiy navba t
Doimiy buri lish (Ing. Persistent queue )– bularning barchasi
qat'iylikni amalga oshiradi , ya'ni uning barcha oldingi versiyalariga kirish imkonini
beradi. Quyida ko'rsatilgandek, funktsional qat'iylikni amalga oshirish mumkin,
ya'ni bunday strukturadagi ha r bir xotira katakchasi bir marta ishga tushiriladi va
kelajakda o'zgarmaydi.
Doimiy navbatni yaratish uchun uni steklarda amalga oshirishdan foydalanish
juda qul ay , chunki steklarni doimiy qilish oson va bu holda biz funktsional
qat' iylikka erishamiz. Buning uchun ikkita stekda amalga oshirish mos emas, chunki
eng yomon holatda bu vaqt talab etadi va shuning uchun qat'iylik holatida
operatsiya uchun xotira. Keling, birinchi navbatda vaqti -vaqti bilan real vaqt
rejimida navbat yaratish va keyin uni doimiy navbatga aylantirishni ko'rsatamiz.
6-stekli navbatni amalga oshirish
Ikkita stekda amalga oshirishning kamchiliklaridan biri shundaki, eng yomon
holatda biz operatsiyaga vaqt sarflaymiz . Agar biz elementlarni bir stekdan
ikkinchisiga o'tkazish uchun ketadigan vaqtni operatsiyalar bo'yicha taqsimlasak,
biz har bir operatsiya uchun haqiqiy vaqtdan eng yomon holatlarsiz navbatga ega
bo'lamiz .
Birinchidan, biz ikkita stack bilan bir xil tarzda davom etamiz. Aytaylik,
bizda operatsiyalar uchun steсk bor . Stack bo'shatilguncha, biz stekning joriy
elementlarini o'z ichiga olgan stekni to'g'ri tartibda olib tashlash uchun vaqtimiz
bo'lishi kerak . Perekopirovanie ( qayta nusxalash rejimi ) biz yangi suyakka
suyakka perekopirovat suyakka qolgan op eratsiyalari uchun mumkin emas, deb bir
xavf bor bo'lsa boshlanadi . Shubhasiz, bu holat L.size> R.size, bunday holat
mantiqiy turdagi recopyning maxsus o'zgaruvchisi bilan aks ettirilsin.
Nusxa ko'chirish operatsiyalari kelishi mumkinligi aniq p u s h va
to'plam L bu vaqtda u o'z tuzilishini yo'qotadi, biz u erga elementlarni qo'sha
olmaymiz, ya'ni biz boshqa stek yarati shimiz kerak L' , unga biz yangi elementlar

14

qo'shamiz. Nusxa ko'chirish tugagandan so 'ng, biz rollarni o'zgartiramiz
L ,L' va R,R' birinch i qarashda hamma narsa yaxshi bo'ladi.
Ammo, agar biz ushbu algoritmni amalga oshirsak, biz yoqimsiz narsani
olamiz: eski stek R bu vaqt ichida bo'shab qolmasligi mumkin, ya'ni biz chiqish
ma'lumotlari bo'lgan ikkita stek oldik, ya'ni ish mumkin (masalan, agar barcha
kiruvchi operatsiyalar - push ), keyingi nusxalashda bizda elementlarni nusxalash
uchun bo'sh stek bo'lmaydi . Ushbu muammoni hal qilish uchun biz barcha
elementlarni stekdan olib tashlashga majbur qilamiz R yordamchi stakka S keyin
stekdan elem entlarni nusxalash L va R keyin elementlarni stekdan nusxa
ko'chiring S va R. Yuqoridagi algoritm shunchaki yakunlanishini ko'rsatish oson
R barcha stek elementlari L,R to'g'ri tartibda.
Lekin bu hali ham yetarli emas. Agar biz elementlarni stekdan majbura n
chiqarsak R, quyidagi muammolar paydo bo'ladi:
1. Operatsiya paytida nimani qaytarish kerak pop ? Buni amalga oshirish
uchun keling, o'zimizga stek olamiz Rc - stek nusxasi R, undan biz kerakli
elementlarni ajratib olamiz.
2. Bunday nusxaning to'g'riligini qan day saqlash kerak? Ushbu stek faqat
nusxa ko'chirish uchun kerak bo'lganligi sababli va u band bo'lganligi sababli,
zaxira nusxasi kerak Rc' biz nusxa ko'chiradigan barcha elementlarni
nusxalash uchun R , va nusxa ko'chirish oxirida biz stek larning rollarin i
o'zgartiramiz Rc,Rc' biz steklar bilan qilganimizdek L ,L'.
3. Nusxa ko'chirish paytida ba'zi elementlardan olinganligini qanday
hisobga olish kerak Rc ? Buning uchun biz maxsus o'zgaruvchini yaratamiz
toCopy Bu stekda qancha to'g'ri elementlar mavjudligini ko'rsatadi S, va har
bir ekstraktsiya bilan kamayadi S yoki operatsiyalar p o p. Yaxshiyamki,
barcha noto'g'ri elementlar stekning pastki qismidan o'sadi, shuning uchun biz
hech qachon noto'g'ri elementni ochmaymiz toCopy>0 . Agar operatsiya
paytida pop biz da bor toCopy=0 , bu hozir stekda ekanligini anglatadi

15

R navbatning butun o'ng tomoni joyl ashgan, shuning uchun biz undan
elementni chiqarib olishimiz kerak.
Endi bo'sh bo'lmagan muammo bo'lishi mumkin Rc nusxalash tugallangandan
keyin. Keling, odatdagi r ejimda har bir operatsiya uchun undan qo'shimcha
ekstraktsiyadan foydalansak, uni bo'shatish uchun doimo vaqtimiz borligini
ko'rsatamiz, buning uchun biz algoritmni to'liq tahlil qilamiz.
Stackda nusxa ko'chirish boshida bo'lsin R o'z ichiga oladi n elemen tlar, keyin
stekda L joylashgan n+ 1 elementlar. Biz istalgan miqdordagi operatsiyalarni to'g'ri
bajarishimiz mumkin push , shuningdek n operatsiyalar pop . E'tibor bering,
operatsiya empty nusxalash paytida har doim qaytib keladi false chunki biz stekdan
na rsalarni chiqara olmaymiz L bu bo'sh emas. Shunday qilib, nusxa ko'chirishni
faollashtiradigan operatsiya bilan birgalikda biz to'g'ri ishlov berishimiz
kafolatlanadi n + 1 bitta operatsiya.
Keling, oldinda bo'ladigan qo'shimcha harakatlarni ko'rib chiqayl ik:
1. Kontentni ko'chirish R va S, n harakat.
2. Kontentni ko'chirish L steklarda R, Rc' , n + 1 bitta harakat.
3. Avval harakatlaning toCopy dan buyumlar S va R , Rc ' qolganlarini
tashlang, n harakat.
4. Staklarni almashtirish Rc,Rc' , L, L' , 2 harakatlar.
Shund ay qilib, biz oldik 3⋅n + 3 uchun qo'shimcha harakatlar n + 1
bitta operatsiyalar, yoki 3 = O ( 1 ) kerak bo'lganda nusxa ko'chirish rejimida
ishlash uchun qo'shimcha harakatlar.
Keling, nusxa ko'chirishning butun davri davomida bizning steklarimiz qanda y
o'zgarganini ko'rib chiqaylik. Operatsiyaga rozi bo'lamiz empty navbatni
o'zgartirmaydi, ya'ni qo'shimcha harakatlar bajarilmaydi. ruxsat bering
n o'zgaruvchan operatsiyalar faollashtirilgandan so'ng ( push, pop ) qabul
qildi x operatsiyalar pop , n-x oper atsiyalar push . Shubhasiz, nusxa
ko'chirilgandan so'ng, yangi to'plamlar quyidagilarni o'z ichiga oladi: n-x ichidagi
elementlar L, 2 ⋅ n + 1 - x = ( n - x ) + ( n + 1 ) ichidagi elementlar R, ya'ni keyingi

16

nusxalashdan oldin, hali n + 2 opera tsiyalar. Boshqa tomondan, stack
Rc hammasini o'z ichiga olgan n elementlar, shuning uchun biz oddiy usulda bir
vaqtning o'zida bitta elementni o'c hirish orqali uni tozalashimiz mumkin.
Shunday qilib, navbat Q oltita to'plamga ega bo'ladi L ,L', R , R c , Rc ', S
shuningdek, ikkita ichki o'zgaruvchi recopy, toCopy , to'g'ri nusxalash uchun zarur
bo'lgan + qo'shimcha o'zgaruvchi c o p i e d elementlarn i stekdan ko'chirganimizni
ko'rsatadi L stek ustida R bu narsalarni stekga surishni boshlamaslik uchun S.
Navbat o'zgarmas (normal rejim):
1. Stak L navbatning chap yarmini o'z ichiga oladi, olishda tartib
teskari bo'ladi.
2. Stak R navbatning o'ng yarmini, to'g 'ri chiziqni olish tartibini o'z
ichiga oladi.
3. L . s i ze ⩽ R . s i ze
4. R . s i ze = 0 ≡ Q . s i ze = 0
5. R c – nusxa R
6. Rc '. s i ze < R . s i ze - L . s i ze
7. L'.s i ze = 0 , S. s i ze = 0
Keyin keyingi nusxalash uchun (L . s i ze = R . s i ze + 1) bizda bo's h steklarga
ega bo'lish kafolatlangan L', S, Rc ' bizga kerak bo'lgan.
Navbat o'zgarmas (nusxa olish rejimi):
1. R c . s i ze = t o C o p y
2. Agar L . s i ze = 0, keyin:
1. Da t o C o p y >0 birinchi toCopy elementlar S - to'g'ri,
ya'ni ular aslida navbatda joylas hgan.
2. Da t o C o p y ⩽ 0 stack R navbatning butun o'ng qismini
to'g'ri tartibda o'z ichiga oladi.
Navbat ikki rejimda ishlaydi:

17

1. Oddiy rejim, kiriting L, dan ko'chirma R va R c , Rc ' tartibni,
operatsiyani saqlash e m p t y= ( R . S i ze = 0 ).
2. Nusxa ko'chirish rejimi, kiriting L', dan ko'chirma R c balki
dan R , empt y = f a l s e, biz qo'shimcha harakatlar qilamiz.
Bundan tashqari, odatdagidek operatsiyadan so'ng, nusxa ko'chirishning
faollashtirilganligini tekshiring ( r e c o p y =( L.size > R . s i ze )), Agar shunday
bo'lsa, toC op y =R .size , recop y= true , copie d= fal s , qo'shimcha harakatlarning
birinchi to'plami amalga oshiriladi.
Nusxa ko'chirish rejimida ishlagandan so'ng, nusxa ko'chirishning
tugallanganligi tekshiriladi ( r e c o p y =( S.s i ze = = 0 )) va tugallangandan so'ng ,
steklar teskari bo'ladi R c , Rc ', L, L' .
Quyidagi psevdokod kerakli operatsiyalarni bajaradi:
empty
boolean empty():
return !recopy and R.size == 0
push
function push(x : T):
if !recopy
L.push(x)
if Rc'.size > 0
Rc'.pop()
checkRecopy()
else
L'.push(x)
checkNormal()
pop

18

T pop():
if !recopy
T tmp = R.pop()
Rc.pop()
if Rc'.size > 0
Rc'.pop()
checkRecopy()
return tmp
else
T tmp = Rc.pop()
if toCopy > 0
toCopy = toCopy - 1
else
R.pop()
Rc'.pop()
checkNormal()
return tmp
Misol
Aytaylik, biz doimiy navbat yaratdik. Biz uni doimiy stek versiyalarining
beshta daraxti, to'ldirilgan uchlari - navbatning joriy holatiga mos keladigan
steklarning joriy versiyalari shaklida taqdim etamiz; stack strelkasi R' stekning o'sha
versiyasiga ishora qiladi R hozir u erda saqlanadi. Ushbu uchlarga mos keladigan
qiymatlar cho'qqilarning o'zida yoziladi (14 -rasm ).
14 -rasm
Operatsiyani qilaylik p u s h ( 1 ), dastlab rejim normal, shuning uchun
element stekga o'tadi L. Ushbu operatsiya nusxa ko'chirish rejimini faollashtiradi,

19

buning natijasida tarkib L stekga ko'chiriladi R , shundan so'ng nusxa ko'chirish
tugallanadi, steklar L ,L' joylarni almashtir ish (15 -rasm ).
15 -rasm
Operatsiyani qilaylik push(2) , bizda oddiy rejim bor, shuning uchun element
stekga o'tadi L, nusxa ko'chirish faollashtirilmagan (16 -rasm ).
16 -rasm
Operatsiyani qilaylik push(3) , bizda oddiy rejim bor, shuning uchun element
stekga o'tadi L, nusxa ko'chirish faoll ashtirilgan, R '= R , uchta operatsiyada stek
elementini nusxalash uchun vaqtimiz bor R stek ustida Sva ikkita stek elementini
qaytadan nusxalash L stek ustida R (17 -rasm ).
17 -rasm
O peratsiyani qilaylik push(4) , biz nusxa ko'chirish rejimidamiz, shuning
uchun element stekg a o'tadi L', keyin elementni stekdan nusxalash uchun vaqtimiz
bor S stek ustida R , nusxa ko'chirish uchlari, steklar L ,L' joylarni almashtirish (18-
rasm ).

20

18-rasm
Operatsiyani qilaylik push(5) , bizda oddiy rejim bor, shuning uchun element
stekga o'tadi L, nusxa ko'chiris h faollashtirilmagan (19 -rasm ).
19 -rasm
Operatsiyani qilaylik push(6) , bizda oddiy rejim bor, shuning uchun element
stekga o'tadi L, nusxa ko'chirish faollashtirilmagan (20 -rasm ).
20 -rasm
Operatsiyani qilaylik push(7) , bizda oddiy rejim bor, shun ing uchun element
stekga o'tadi L,nusxa ko'chirish faollashtirilgan, R '= R , toC opy=3, uchta

21

operatsiyada biz stek tarkibini nusxalash uchun vaqtimiz bor R stek ustida S (21 -
rasm ).
21 -rasm
Operatsiyani qilaylik pop , biz nusxa ko'chirish rejimidamiz, shuning uchun
element olinmoqda R ', t o C o p y =2. Uch ta operatsiyada biz stekning uchta
elementi ni nusxalash uchun vaqtimiz bor L stek ustida R(22 -rasm ).
22 -rasm

Operatsiyani qilaylik pop , biz nusxa ko'chirish rejimidamiz, shuning uchun
element olinmoqda R ',toCop y=1 . Uchta amalda stekning bitta elementi ni nusxalash
uchun vaqtimiz bor L stek ustida R va shuningdek, stekning ikkita elementini
oching S, hisobga olgan holda toCopy faqat bitta element stekga
tushadi R , toCopy=0 (23 -rasm ).

22

23 -rasm
O peratsiyani qilaylik p o ppop , biz nusxa ko'chirish rejimidamiz, shuning
uchun element olin moqda R' , lekin toCopy=0 , shuning uchun biz stekdan yana
bitta elementni chiqarishimiz kerak R . Biz to'plamdan bitta elementni chiqaramiz S,
uchlarini qayta nusxalash, steklar L ,L' joylarni almashtirish (24 -rasm ).
24 -rasm

23

2.4 Doimiy pastki
Dek (inglizcha deque - double ended queue - ikki uchli navbat) - elementlarga
ikki tomonlama kirish imkoniyatiga ega bo'lgan ma'lumotlar strukturasi, ya'ni. ular
olib tashlanishi va kemaning boshiga ham, oxiriga ham qo'shilishi mumkin.
Pastki qismga qo'shimcha ravishda , stek va navba tning birlashmasi
bo'lgan steque deb nomlangan ma'lumotlar tuzilmasi ham mavjud - elementlar faqat
bitta uchiga qo'shilishi va i kkalasidan ham ol inishi mumkin (25 -rasm ).
Strukturani saqlash usuli
25 -rasm
Doimiy pastki qismni yakka bog'langan ro'yxat sifatida ko'rish mumkin , bu erda
har bir tugun juftlikni - chap va o'ng elementni, shuningdek, bolani - keyingi
tugunga havolani saqlaydi . Har bir tugunning faqat chap va o'ng elementlari
oldingisiga qaraganda ikki baravar ko'p ob'ektlarni saqlaydi. Buni bug ' turi
yordamida qilish qulay .
A turi elementlar bir necha saqlaydi va turlari .
class Pair<T>:
T first
T last

24

Deckning o'zi to'g'ridan -to'g'ri konstruktorni chaqirish orqali ishga tushirilishi
mumkin . Shablon orqali strukturaning tavsifi quyidagicha:
class
Deque <T>:
T chap
T o'ng
Deque <Pair <T>> bola
Bizning ma'lumotlar tuzilmamiz barqaror, shuning uchun
operatsiya boshida element qo'shilgan yangi qavatni qaytaradi .
push
Bo'sh pastki belgi bilan belgilanadi ∅, va bo'sh juftlik - ∅Biz kemaga murojaat
qilganim izda va elementga murojaat qilganimizda, buni aniqroq qilish uchun. Biz
pastki qismning boshiga element qo'shish yoki uni boshidan olib tashlashni
xohlasak, biz birinchi nav batda maydonga murojaat qilamiz left . Agar biz oxiri bilan
ishlasak, unda biz birin chi navbatda maydonga murojaat qilamiz r right .
Deque<T> pushFront(x: T, D: Deque<T> ):
if D == ∅
// agar pastki bo'sh bo'lsa, yangi pastki
return Deque(x, ∅ )
else if D.left == ∅
// agar chap bola mavjud bo'lmasa, u holda qiling xxchap bola
return Deque(x, D.child, D.right)
else
// aks holda, chap bolani yangi element bilan bi rlashtiring va keyingi
bosqichda
return Deque( ∅, pushFront(Pair(x, D.left), D.child), D.right)
pop

25

Usul popFront(D) juftlikni qaytaradi ⟨e, D' ⟩ birinchi elementdan va bu
elementni olib tashlash orqali eskisidan olingan yangi pastki.
Pair<T, Deque<T>> popFront(D: Deque<T> ):
if D == ∅
// bo'sh pastki qaytib, bir juft "nol element - bo'sh pastki" bir narsani olib
tashlash
return h∅, ∅i
else if D.left ≠ ∅
// agar chap bola bo'sh bo'lmasa, biz undan bir juft va chap bolasiz yangi
pastki qism ini qaytaramiz,
// faqat chap bola qolgan bo'lsa, bas, uni va bo'sh pastki qaytib
if D.child == ∅ and D.right == ∅
return hD.left, ∅i
return hD.left, Deque( ∅, D.child, D.right) ii
else if D.child == ∅
// agar chap bola bo'sh b o'lsa va keyingi qavatga havola bo'lmasa,
// keyin o'ng bola va butunlay bo'sh pastki
return hD.right, ∅i
else
/ *
* agar oldingi ikkita shart bajarilmagan bo'lsa, biz usulni rekursiv
chaqiramiz p o p F r o n tpopFront
* va qaytar ilgan "element - yangi pastki" juftligi o'zgaruvchilarga saqlanadi
t e m ptemp va n e w D e qu enewDeque ...
* Rekursiv qo'ng'iroqlar chap bola bo'sh qolmasligi bilanoq to'xtaydi
* yoki kemaning keyingi dekabrga havolasi bo'lmaydi.
* /
(temp , newDeque) = popFront(D.child) / *

26

* Bu yerga t e m ptemp har doim bo'sh emas; vaqtinchalik juftlikning
birinchi elementi qaytarilishi kerak
* (ushbu blokda harorat har doim shunday bo'ladi P a i rPair );
* yangi qavatning chap to moniga qo'yishingiz kerak
t e m p . l a s ttemp...last (quyida t e m ptemp saqlanadi
* ikki barobar ko'p elementlar, shuning uchun joriy darajada
t e m p . l a s ttemp...last mos keladi
* elementlarning kerakli soni); n e w D e qu enewDeque qi l
c h i l dchild ohm
* yangi paluba va r i gh tright joriy r i gh tright ohm yangi
* /
return ⟨⟨temp.first, Deque(temp.last, newDeque, D.right) ⟩
O'ng uchiga qo'shish va undan ajratib olish operatsiyalari simmetrik tarzda
amalga oshiriladi.
Ish vaqti asimptotikasi
Shunday qilib, agar biz elementlarni faqat bir uchiga qo'shsak, u holda i- chi
darajal i paluba endi yo'q 2i-elementlar. Joriy kemaning chuqurligiga ruxsat bering
d. Keyin dan ortiq bo'lishi mumkin emas n = 1 + 2 + 4 + … +2d ob'ektlar, biz
qaerdan olamiz d= b?????????????????? ?????????????????? .
Elementni olish uchun siz daraxtning chuqurligidan ko'proq past ga tushishingiz
kerak. Qo'shish uchun ham xuddi shunday. Shuning uchun ikkala operatsiya ham
ichida amalga oshiriladi O (logn )
Misol
Keling, operatsiyani batafsil ko'rib chiqaylik. Eng yomon holatda, narsalar
faqat bir uchiga qo'shiladi va ikkinchisidan olinadi.
pushFront
Bizda dastlab bo'sh paluba bor. Elementlar kemaning chap uchiga qo'shiladi va
ular qo'shilish tartibiga ko'ra raqamlanadi. Avval birinchi elementni qo'shamiz. U

27

pastki qavatning birinchi darajasidagi chap bolaning o'rnini egallaydi. Endi ikkinchi
elementni qo'shishga harakat qilaylik. Chap bolaning pozitsiyasi egallangan, ya'ni
biz yangi elementni eskisi bilan birlashtiramiz va hosil bo'lgan juftlikni ikkinchi
qavatning chap bolasi o'rniga qo'yamiz. Qo'shish jarayonini qo'shish deb hisobl ash
mumkin 1ta ikkilik ko'rinishdagi sonning raqamiga: raqamda bo'lsa 1, keyin undan
keyingi ketma -ket birliklar nolga teng bo'ladi - elementlar juftlarga birlashtiriladi,
aks holda ular bu zaryadsizlanish o'rnini egallaydi (26 -rasm ).

27 -rasm

28

2.5 Doimiy ustuvor navbat
D oimiy ustuvorlik navbati (Ing. Persistent priority queue ) - ustuvor
navbat , qat'iylikni amalga oshiradi , ya'ni uning barcha oldingi versiy alariga kirish
imkonini beradi.
Segment daraxti bilan amalga oshirish
Fikr
Ma'lumki, segment daraxti asosida to'liq doimiy ma'lumotlar strukturasi
qurilishi mumkin . Shuning uchun biz navbat elementlarini kiritish va o'chirishda
o'zgartirish operatsiyasini o'zgartirib, undan foydalanamiz.
Amalga oshirish
Biz aniq ko'rsatgichlarni bolalar elementlariga saqlaymiz. Keyin daraxt
tugunining tuzilishi quyidagi shaklni oladi:
struct Node:
Node left
Node right
T key
Node(val : T) // varaqlar uchun konstruktor
Node(leftChild : Node , rightChild : Node )
/* tugunlar uchun konstruktor (kalit maydoniga leftChild va rightChild orasida
minimal miqdorni tayinlaydi) */
Keling, quyidagi funktsiyalarni bajaraylik:
 build - daraxt qurish,
 insert - yangi navbat elementini kiritish,
 extractMin - navbatning minimal elementini olib tashlash,
 merge - birlashish.

29

Har bir funktsiya yangi daraxtning ildizini qaytaradi, keyin uni yana o'zgar tirish
mumkin. Amalga oshirishda siz daraxt ildizlarining alohida qatorini saqlashingiz
mumkin va har bir versiyaga har bir yangi o'zgartirish kiritilganda, o'zgartirilganini
massiv oxiriga qo'shishingiz mumkin.
Build -qurmoq
Daraxt belgilangan hajmda quril adi. Shuni ta'kidlash kerakki, bir nechta
daraxtlarni yaratishda siz bitta maksimal o'lchamga rioya qilishingiz
kerak. Segmentlar daraxtini qurishning asimptotik harakati bo'ladi O ( n )O(n) ...
Node build(left : uint , right : uint ):
if left == right
return Node( ∞∞)
uint mid = (left + right) / 2
return Node(build(left, mid), build(mid + 1, right))
insert -kiritmoq
Har qanday bo'sh varaqqa yangi qiymat kiritamiz. Agar uning qiymati bo'lsa,
varaq bo'sh hisoblanadi ∞. Shu bilan birga, navbatning oldin gi holatini saqlab qolish
uchun o'zgartirilishi mumkin bo'lgan tugunlarni birinchi navbatda nusxalash
kerakligini va keyin nusxa ko'chirilganiga asoslanib yangisini kiritish kerakligini
unutmang. Yangi kalit kiritish so'rovi hosil bo'ladi O ( logn ) yangi cho'qqilar va
uning ish vaqti O ( n ).
Node insert(currentNode : Node , newVal : T):
if currentNode.left == null and currentNode.right == null and currentNode.val !=
∞ // varaq band bo'lsa
return null
if currentNode.left == null and currentNode.right == null and currentNode.val
== ∞ // varaq bepul bo'lsa
return Node(newVal)

30

Node temp = insert(currentNode.left, newVal)
if temp == null
temp = insert(cur rentNode.right, newVal)
if temp == null
return null
else
return Node(currentNode.left, temp)
else
return Node(temp, currentNode.right)
extractMin - ekstraktiMin
Daraxtning ildizida minimal elementning kaliti mavjudligini hisobga olsak, siz
ushbu elementni o'z ichiga olgan varaqning yo'lini topishingiz va uni o'chirishingiz
mumkin. Qo'shishga o'xshab, navbatning oldingi holatini saqlab qolishni
unutmang. Funktsiya chaqiruvi daraxtning ildizini va daraxt ildizidagi qiymatni
argument sifatida ko'rsatish orqali amalga oshirilishi kerak. Minimal kalitni o'chirish
so'rovi hosil bo'ladi O ( logn ) yangi cho'qqilar.
Node extractMin(currentNode : Node , delVal : T):
if currentNode.left == null and currentNode.right == null and currentNode. val
== delVal
return Node( ∞)
if currentNode.left.val == delVal:
return Node(extractMin(currentNode.left, delVal), currentNode.right)
else
return Node(currentNode.left, extractMin(currentNode.right, delVal))
birlashtirish
Ikki daraxtni birlashtirish struktura konstrukto ri yordamida amalga
oshiriladi. Shuning uchun u uchun amalga oshiriladi O ( 1 ).

31

Node merge(leftTree : Node , rightTree : Node )
return Node(leftTree, rightTree)
Amalga oshirishdagi kamchiliklar
Ushbu amaliyot bir qator muhim kamchiliklarga ega:
1. Amalga os hirish navbatning cheklangan hajmini nazarda tutadi, bu esa uni
keng ma'lumotlar diapazonida ishlatishni juda qiyinlashtiradi.
2. Kiritish amalga oshiriladi O(n) , bu esa ushbu dasturni katta hajmdagi
ma'lumotlarda foydasiz qiladi. Har safar ustuvorlik
navbati o'zgartirilganda ustuvor navbatni nusxalash va o'zgartirish orqali bir
xil ish vaqtini olish mumkin edi .
Yana samarali amalga oshirish ikkilik qi diruv daraxti ustida qurilgan doimiy
ustuvor navbatdir . Birlashtirishdan tashqari barcha operatsiyalar ichida
bajariladi O ( logn ). Bundan tashqari, ikkilik qidiruv daraxti dinamik tuzilma bo'lib,
uni amalga oshirish tufayli ma'l umotlarni cheklash haq ida o'ylamaslikka imkon
beradi.
Chap qirrali to'p bilan amalga oshirish
Keling, chap tomondagi uyada ustuvor navbatni
amalga oshiramiz . Chunki hech halokatli topshiriqlar joyda amalga
oshiriladi yilda chap tomonlama yoshroq , keyin siz bir doimiy ustuvor navbatda uni
o'zgartirishingiz mumkin.
Biz strukturani saqlaymiz:
struct LeftistHeap:
LeftistHeap left
LeftistHeap right
T key
int dist

32

LeftistHeap(leftChild : LeftistH eap , rightChild : LeftistHeap , val : T)
Bu yerda konstruktorning amalga oshirilishi:
LeftistHeap(leftChild : LeftistHeap , rightChild : LeftistHeap , val : T):
key = val
if leftChild.dist > rightChild.dist
left = leftChild
right = rightChild
else
left = rightChild
right = leftChild
dist = min(left.dist, right.dist) + 1
Qo'llab -quvvatlanadigan operatsiyalar
Deyarli barcha operatsiyalar ( bundan mustasno merge ) chap tomondagi
yig'ish operatsiyalariga o'xshaydi, faqat har biri o'zgartirilgan uyaning ildizini
qaytaradi. Ayniqsa extractMin ajratilgan cho' qqidan va o'zgartirilgan to'pdan
juftlikni qaytaradi.
merge quyidagi shaklni oladi:
LeftistHeap merge(x : LeftistHeap , y : LeftistHeap ):
if x == ∅:
return y
if y == ∅:
return x
if y.key >= x.key:
z = LeftistHeap(x.left, merge(x.right, y), x.key)
else
z = LeftistHeap(y.left, merge(y.right, x), y.key)

33

return z;
Binomli to'pni amalga oshirish
Keling, binomial to'plamni olaylik va uni bir -biriga bog'langan ro'yxatlarda
amalga oshiramiz .
Buning uchu n biz ildizlar ro'yxatini darajaning o'sish tartibida, bolalarni esa
darajaning kamayish tartibida saqlaymiz. Har bir ota -ona bolalar ro'yxatining boshi
bo'lgan yuqori martabali bolani biladi, lekin bola ota -onasini tanimaydi. Chunki bola
o'z ota -onasidan bexabar bo'lsa, unda bu tuzilmaning mustahkamligini saqlab,
daraxtlarni birlashtirish mumkin.
Uyum tuzilishi
Doimiy binomial to'pdagi har bir tugun maydonlar to'plami bilan ifodalanadi:
 key - elementning kaliti (og'irligi),
 next - keyingi elementga ko'rsat gich,
 child - yuqori martabali bolaga ko'rsatgich,
 degree - tugun darajasi (berilgan tugunning bola tugunlari soni).
Uyumga ildizlar ro'yxatidagi birinchi ildizga havola orqali kirish mumkin.
Operatsiyalar
getMinimum
Minimal elementni topish uchun siz dara xt ildizlari ro'yxatidan o'tishingiz
kerak. Buning uchun qilishingiz mumkin O ( log n ) beri ildizlar ro'yxati ko'pi bilan
o'z ichiga oladi log n elementlar. Rasmda bu uyumdagi ikkinchi daraxtning
ildizi (28 -rasm ).

34

28 -rasm
Merge - birlashtirish
Biz ildiz ro'yxatlarini ko'ri b chiqamiz va bir xil darajadagi daraxtlarni
birlashtirib, yangisini yaratamiz.
Yordamchi funksiya mergeTree bir xil darajadagi daraxtlarni
birlashtiradi. Buning uchun biz ikkita yangi tugun yaratamiz, ulardan biri yangi
ildiz, ikkinchisi daraxtlardan biri ning o'zgartirilgan ildizidir.
PersistentBinomialHeap mergeTree(t1 : PersistentBinomialHeap , t2 :
PersistentBinomialHeap ):
newRoot = PersistentBinomialHeap()
tmp = PersistentBinomialHeap()
newRoot.child = tmp
newRoot.degree = t1.degree + t2.degree
if (t1.key < t2.key)
tmp = PersistentBinomialHeap(t2) ) // konstruktor yordamida eskisini nusxalash
orqali yangi tugun yarating
tmp.next = t1.child
newRoot.key = t1.key
else
tmp = PersistentBinomialHeap(t1)
tmp.next = t2.child
newRoot.key = t2.key
return newRoot

35

Ikki daraxtni birlashtirish jarayoni rasmda ko'rsatilgan. Dastlab ikkita daraxt
bor edi t1 va t2 (rasmda qora rang bilan ta'kidlangan). Keyin ular birlashtirildi, ikkita
yangi tugun paydo bo'ldi, ular hali ham eski p astki daraxtlarga tegishli (qizil rang
bilan ta'kidlangan , 29 -rasm ).

29 -rasm
Ildiz ro'yxatlar bo'ylab o'tish ichida amalga oshiriladi O ( logn ), daraxtlarning
birlashuvi amalga oshiriladi O (1). Keyin merge uchun ishlaydi O ( logn ).
Insert -kiritmoq
Yangi elementni kir itishning umumiy printsipi oddiy binomial uyumga kiritish
tamoyiliga o'xshayd i . Darajali daraxt bilan to'p yarating 0, unda bitta element
bo'ladi - biz kirit ishimiz kerak bo'lgan element va keyin biz ikkita to'pni bittasiga
birlashtiramiz.
Birlashtirishning ikkita holati mavjud:
1. Uyumdagi daraxtning minimal darajasi nolga teng. Key in ikkita
to'plamni birlashtiramiz merge . Ish vaqti O ( logn ).

36

2. Uyumdagi daraxtning minimal darajasi nolga teng emas. Keyin
biz yaratilgan uyumga element qo'shmoqchi bo'lgan narsani biriktiramiz. Ish
vaqti O (1).
Keyin bitta operatsiyaning amortizatsiya qili ngan
qiymati insert hisoblanadi O ( 1 ).
PersistentBinomialHeap insert(heap : PersistentBinomialHeap , newVal : T):
newRoot = PersistentBinomialHeap(newVal)
if heap.degree == newRoot.degree:
return merge(newRoot, heap)
else
newRoot.next = hea p
return newRoot
Ishga misol.
Tavsif Rasm
Asl to'plam.

37

Uyumga element kiritamiz, kaliti
teng 3. Bunday holda, band ostidagi
shart 2.

Endi bir xil to'plamga kaliti teng
bo'lgan elementni kiritamiz 4. Ushbu
holat paragrafga mos keladi 1.

extra ctMinimum - Minimal ekstrakt
Oddiy binomial to'pdagi kabi ishlaydi . Biz ildi zlar ro'yxatini ko'rib chiqamiz
va minimal kalit bilan tepani topamiz. Keyin biz minimal kalitga ega bo'lgan
daraxtni olamiz. Daraxtdagi bolalarni minimal kalit bilan darajaning o'sishi bo'yicha
saralaymiz. Ikki to'plamni birlashtirish. Funktsiya minimal k alitni va minimalni
olgandan so'ng yangi to'pni qaytaradi. Operatsion vaqti O ( logn ).

38

Xulosa
Bu kurs ishimizda biz asosan segment daraxt va shu bilan
birgalikda saralash haqida va birgalikda push, pop operatorlari haqida
qisqacha ma’lumotlar berib o’ti lgan. Shu bilan birgalikda dasturlashni
baholashga doir ma’ lu mot lar ham, ya’ni chiziqli, logarifmli kvadratli va
boshqalari haqida qizqacha yoritib o’tilgan.

39

Foydalanilgan adabiyolar :
1. M.O‘. ASHUROV, SH.A.SATTAROVA, SH.U.USMONQULOV,
“ALGORITMLAR” , «Fan va texnologiya» nashriyoti, 2018.
2. Richard Bellman . Sayohatchi sotuvchi muammosini dinamik dasturlash
bilan davolash // ACM jurnali . - 1962 . -- T. 9 . - S. 61 –63.
3. Kazuo Ivama, Takuya Nakashima. TSP kub grafigi uchun
takomillashtirilgan aniq algoritm // Proc. Hisoblash va kombinatorika
bo‘yicha 13 -yillik xalqaro konferensiya (COCOON 2007). - 2007. - T. 4598.
- S. 108 -117. - (Informatika fanidan ma'ruza matnlari).
4. Maykl Gari, Devid S. Jonson , Larri Stokmeyer. Ba'zi soddalashtirilgan NP -
to'liq muammolar // Proc. Hisoblash nazariyasi bo'yicha 6 -ACM simpoziumi
(STOC '74). - 1974. - S. 47 –63.
5. Maykl Gari, Devid S. Jonson , Larri Stokmeyer. Ba'zi soddalashtirilgan NP -
to'liq muammolar // Proc. Hisoblash nazariyasi bo'yicha 6 -ACM simpoziumi
(STOC '74). - 1974. - S. 47 –63.

Foydalanilgan internet saytlar:
1. https://neerc.ifmo.ru/wiki/index.php
2. http://ziyonet.uz/
3. https://fayllar.org/fan -algoritmlar -va -malumotlar -strukturasi.html
4. https://fayllar.org/c -boyicha -qollanma -c.html?page=2

1 Mundarija I Kirish ………… … …… …… …………………… …...…... ………… ……… .2 II Asosiy qism …………………………………..…… …………………… ..3 2.1 Ma'lumotlar tuzilmalarini doimiyga o'tkazish usullari … ………….… ..3 2.2 Doimiy to'plam … ……………………………………………………... .8 23 Doimiy navbat ……………………………………… ……………… … 13 2. 4 Doimiy pastki ………………………………………………………... .24 2.5 Doimiy ustuvor navbat ……………………………………………….. .29 III Xulosa ………………………………………………… ……………… … 38 IV Foydalanigan adabiyotlar …………………………… ……………... 39

2 Kirish Doimiy ma'lumotlar strukturasi - har qanday o'zgartirishl ar kiritilganda o'zining avvalgi holatini va ushbu holatlarga kirish huquqini saqlab qolgan ma'lumotlar tuzilmasi. To'liq doimiy ma'lumotlar tuzilmalarida siz nafaqat oxirgi, balki ma'lumotlar tuzilmalarining istalgan versiyasini o'zgartirishingiz mumkin, shuningdek, istalgan versiyaga so'rovlar qilishingiz mumkin. Birlashtirilgan ma'lumotlar tuzilmalari ikkita ma'lumotlar tuzilmasini bittaga (birlashtirilishi mumkin bo'lgan qidiruv daraxtlari) birlashtirishga imkon beradi. Funktsional ma'lumotlar tuzilmala ri ta'rifi bo'yicha to'liq barqarordir, chunki ular halokatli topshiriqlarga ruxsat bermaydi, ya'ni. har qanday o'zgaruvchiga faqat bir marta qiymat berilishi mumkin va uni o'zgartirib bo'lmaydi. Agar ma'lumotlar strukturasi funksional bo'lsa, u holda u qo 'shiladi, agar u qo'shilgan bo'lsa, u butunlay doimiy, agar u to'liq doimiy bo'lsa, u ham qisman doimiydir. Shu bilan birga, funktsional emas, balki birlashuvchi ma'lumotlar tuzilmalari mavjud.

3 2.1 Ma'lumotlar tuzilmalarini doimiyga o'tkazish usullar i Ha r qanday tuzilmani barqaror qilishning bir necha yo'li mavjud:  to'liq zaxira nusxasi (ingl. full copy ) har qanday o'zgartirish operatsiyasi uchun ma'lumotlar strukturasi to'liq nusxalanganda, natijada yangi nusxa o'zgartiriladi,  yuqoriga yo'l (ingliz. Pat h copying ),  fat node usuli . Qisman qat'iyat bilan boshlaylik. Aniqlik uchun ma'lumotlar tuzilmalarining turli versiyalarini raqamlaymiz. Ma'lumotlar strukturasidagi o'zgarishlar tarixi chiziqli bo'lib, istalgan vaqtda ma'lumotlar strukturasining istalgan versiyasiga murojaat qilishingiz mumkin, lekin faqat oxirgi versiyasini o'zgartirish mumkin (u rasmda ko'k rang bilan ta'kidlangan) (1 -rasm) . 1-rasm Keling, ma'lumotlar strukturasi nima ekanligini aniqlaylik. Bizning tushunchamizda ma'lumotlar strukturas i ba'zi ma'lumotlar saqlanadigan va bu tugunlar havolalar bilan bog'langan tugunlar to'plami deb ataladi. Ma'lumotlar strukturasiga misol daraxtdir . Keling, yo'lni nusxalash orqali daraxtni qanday qilib barqaror qilishni ko'rib c hiqaylik. Yo'ldan nusxa ko'chirish usuli Bir bor bo'lsin muvozanatli qidiruv daraxt . Undagi barcha operatsiyalar uchun baja riladi O ( h ), qayerda h - daraxtning balandligi va daraxtning balandligi O ( logn ), qayerda n -uchlari soni. Aytaylik, bu muvozanatli daraxtda qandaydir yangilanishni amalga oshirish kerak, masalan, boshqa element qo'shing, lekin ayni paytda eski darax tni yo'qotmaslik kerak. Yangi bola qo'shmoqchi bo'lgan

4 tugunni oling. Yangi tugunni qo'shish o'rniga, biz ushbu tugunni nusxalaymiz, nusxaga yangi bola qo'shamiz, shuningdek, barcha ko'rsatkichlar bilan birga birinchi ko'chirilgan tugunga erishish mumkin b o'lgan ildizgacha bo'lgan barcha tugunlarni nusxalaymiz. Biz o'zgartirilgan tugunga etib bo'lmaydigan barcha burchaklarga tegmaymiz. Yangi tugunlar soni har doim logarifm tartibida bo'ladi. Natijada, biz daraxtning ikkala versiyasiga kirish imkoniyatiga eg amiz (2 -rasm) . 2-rasm Biz muvozanatli qidiruv daraxtini ko'rib chiqayotganimiz sababli, muvozanatlash paytida cho'qqini yuqoriga ko'taramiz, siz aylanishlarda ishtirok etuvchi barcha cho'qqilarning nusxalarini yaratishingiz kerak, ular uchun bolalarga hav olalar o'zgartirildi. Bundaylar har doim uchtadan ko'p emas, shuning uchun asimptotiklar O ( log n ) azob chekmaydi. Balanslash tugagach, yo'l bo'ylab cho'qqilarning nusxalarini yaratib, ildizga ko'tarilish kerak. Bu o'zgartirganda, qo'shish operatsiyasi j uda qimmatga tushadi, chunki element boshqa barcha elementlardan kirish mumkin bo'lgan navbatning dumiga

5 qo'shiladi. Agar ma'lumotlar tuzilmasi ota -onaga havolalar mavjud bo'lsa, ushbu usuldan foydalanish foydali emas. Segmentlar daraxtini amalga oshirish Segment daraxtiga asoslanib, siz to'liq doimiy ma'lumotlar strukturasini yaratishingiz mumkin. Segmentlarning doimiy daraxtini amalga oshirish uchun daraxtning tuzilishini biroz o'zgartirish qulay. Buning uchun biz aniq mayoqlar foydalanish va bolalar uch un. Bundan tashqari, biz versiya segmentlari daraxtining ildiziga ishora qiladigan massiv yaratamiz Elementlardan doimiy segmentlar daraxtini yaratish uchun daraxtning so'nggi versiyasiga element qo'shish operatsiyasini qo'llash kerak . Daraxtning -th vers iyasiga yangi element qo'shish uchun siz uning to'liq ikkilik ekanligini tekshirishingiz kerak. Ha bo'lsa, unda yangi ildiz yarating, chap o'g'il qiling... Aks holda, biz asl nusxaning ildiz nusxasini yaratamiz. Keling, ildizlar qatorining oxiriga ildiz qo 'shamiz. Bundan tashqari, ildizdan birinchi bo'sh barggacha tushib, biz mavjud bo'lmagan tugunlarni yaratamiz va mavjudlarini klonlaymiz. Shundan so'ng, yangi filialda siz funktsiyaning qiymatini va bola elementlarining ba'zi ko'rsatkichlarini yangilashing iz kerak. Shuning uchun, rekursiyadan qaytib, biz bitta ko'rsatgichni yangi yaratilgan yoki ko'chirilgan cho'qqiga o'zgartiramiz, shuningdek, daraxt qurilgan funktsiyaning qiymatini yangilaymiz. Ushbu operatsiyadan so'ng, kiritilgan elementni o'z ichiga ol gan daraxtda yangi versiya paydo bo'ladi. Segmentlarning doimiy daraxtidagi elementni o'zgartirish uchun siz quyidagilarni qilishingiz kerak: daraxt bo'ylab kerakli versiyaning ildizidan kerakli elementga o'ting, uni nusxalang, qiymatni o'zgartiring va dar axt bo'ylab yuqoriga chiqing. , biz tugunlarni klonlaymiz. Bunday holda, oldingi klonlash paytida yaratilgan tugunga ko'rsatgichni bolalardan biriga o'zgartirish kerak. Ildizdan nusxa olgandan so'ng, ildiz qatorining oxiriga yangi ildiz qo'shing (3 -rasm) .

Ma'lumotlar tuzilmalarini doimiyga o'tkazish usullari

12.08.2023

0

1451.818359375 KB

Похожие