) Binar indekslengen terek yaki fenevick algoritmi

Download 124.9 Kb.
bet	3/3
Sana	05.11.2023
Hajmi	124.9 Kb.
	#94476

Bog'liq
Saliev mag.str word
Faza va nol farqi, zazemleniya, anatatsiya, Yo\'l-yo\'l, Usnatdinov Islam Magliwmatlar strukturasi oz betinshe, Usnatdinov Islam Magliwmatlar strukturasi oz betinshe, Reja Mehnat unumdorligi va uning ahamiyati, essay, Qiziqarli fizika. PhysicsUzb , Atom yadro fizikasidan laboratoriya ishlari qo\'lanmasi, Nazirov Jamshid, 11-mavzu, Xf6v40aysSs CaTyRQfdkRubDxQNpheG (1), 26003769, 2-mavzu Sahna.

31) Binar indekslengen terek yaki fenevick algoritmi Ekilik indeksli terek yamasa Fenwick teregi Ekilik indeksli terekti túsiniw ushın tómendegi máseleni kórip shıǵayıq. Bizde arr[0 dızbeki bar... n-1]. Biz qáleymiz 1 Birinshi i elementlerdiń jıyındısın esaplań. 2 Dızbektiń belgilengen elementiniń ma`nisin ózgertiriń arr[i] = x bul erda 0 <= i <= n-1. Ápiwayı sheshim - 0 den i-1 ge shekem bolǵan cikldı jumısqa túsiriw hám elementlerdiń jıyındısın esaplaw. Bahanı jańalaw ushın arr[i] = x ni atqarıń. Birinshi operatsiya O (n) waqtın aladı, ekinshi operatsiya bolsa O (1) waqtın aladı. Taǵı bir ápiwayı sheshim qosımsha dızbek jaratıw jáne bul jańa dızbekte i-indeks degi birinshi i -ne elementlerdiń jıyındısın saqlaw bolıp tabıladı. Berilgen diapazondıń jıyındısı endi O (1) waqıt ishinde esaplanıwı múmkin, biraq jańalaw procesi O (n) waqtın aladı. Eger soraw operatsiyaları kóp bolsa, lekin jańalaw operatsiyaları júdá az bolsa, bul jaqsı isleydi. O (log n) waqtında soraw hám jańalaw ámellerin atqara alamızba? Nátiyjeli sheshimlerden biri O (Logn) waqtında eki operatsiyanı atqaratuǵın Segment Tree-den paydalanıw bolıp tabıladı. Alternativ sheshim ekilik indeksli terek bolıp, ol eki operatsiya ushın da O (Logn) waqıt quramalılıǵına erisedi. Segment tereki menen salıstırǵanda, Ekilik indeksli terek kemrek jay talap etedi hám ámelge asırıw ańsatlaw. wákillik Ekilik indeksli terek dızbek retinde usınıs etiledi. Dızbek BITree[] bolsın. Ekilik indeksli terektiń hár bir túyininde kirisiw dızbekiniń birpara elementleri jıyındısı saqlanadı. Ekilik indeksli terektiń ólshemi kirisiw dızbekiniń ólshemine teń bolıp, n menen belgilenedi. Tómendegi kodta biz ámelge asırıw qolaylıǵı ushın n+1 ólsheminen paydalanamız. Qurılıs Biz BITree[] dagi barlıq bahalardı 0 retinde jumısqa túsiremiz. Keyin barlıq indeksler ushın update () ni shaqıramız, update () operatsiyası tómende talqılaw etiledi. Operatsiyalar GetSum (x): arr[0, …, x] kishi dızbektiń jıyındısın qaytaradı // arr[0..n-1] den dúzilgen BITree[0..n] járdeminde arr[0, …, x] kishi dızbekleri jıyındısın qaytaradı. 1) Shıǵıw summasın 0, ámeldegi indeksti x+1 retinde baslań. 2) Ámeldegi indeks 0 den úlken bolǵanda tómendegi ámellerdi atqarıń. …a) Jıyındı BITree[indeks] …b) BITree[indeks] ata-anasına ótiń. Ata-ananı alıp taslaw arqalı alıw múmkin ámeldegi indeksten aqırǵı ornatılǵan bıyt, yaǵnıy indeks = indeks - (indeks & (-index)) 3) Qaytıw summası. Jańalaw funktsiyası arr[i] ni óz ishine alǵan barlıq BITree túyinleri jańalanıwına isenim payda etiwi kerek. Biz BITree-dagi bunday túyinlerdi ámeldegi indekstiń aqırǵı ornaılǵan bitiga sáykes keletuǵın onlıq sannı qayta -qayta qosıw arqalı aylantıramız. Ekilik indeksli terek qanday isleydi? Bul ideya barlıq oń sanlardı 2 dıń dárejeleri jıyındısı retinde ańlatıw múmkinligine tiykarlanadı. Mısalı, 19 ni 16 + 2 + 1 retinde kórsetiw múmkin. BITree dıń hár bir túyininde n ta element jıyındısı saqlanadı, bul erda n - a 2 dıń kúshi. Mısalı, joqarıdaǵı birinshi diagrammada (getSum () diagramması ) dáslepki 12 elementtiń jıyındısı aqırǵı 4 element (9 dan 12 ge shekem) hám 8 teńiń jıyındısı menen alınıwı múmkin. elementler (1 den 8 ge shekem). n sanınıń ekilik kórinisindegi ornatılǵan bıytlar sanı O (Logn) bolıp tabıladı. Sol sebepli biz getSum () hám update () operatsiyalarında eń kóp O (Logn) túyinlerin kesip ótemiz. Qurılıstıń waqıt quramalılıǵı O (nLogn) bolıp tabıladı, sebebi ol barlıq n element ushın update () ni shaqıradı. Terekke jańa element qosıw funksiyası Terekke qandayda bir bir elementti qosıwdan aldın terekte berilgen gilt boyınsha qıdırıwdı ámelge asırıw kerek boladı. Eger berilgen giltke teń gilt bar bolsa, ol halda programma óz jumısın juwmaqlaydı, keri jaǵdayda terekke element qosıw ámelge asıriladı. Terekke jańa jazıwdı kirgiziw ushın, áwele terektiń sonday túyinin tabıw kerek, nátiyjede usı túyinge jańa element qosıw múmkin bolsın. Kerekli túyindi qıdırıw algoritmı da tap berilgen gilt boyınsha túyindi tabıw algoritmı sıyaqlı boladı. Terekte qosılıp atırǵan element giltine teń giltli element joq bolǵan halda elementti strukturaǵa qosıw funksiyasın keltirip ótemiz. Node *q=NULL; Node *p=tree; while(p!=NULL){ q=p; if(key==p->key){ search=p; return 0; } If(key key) p=p->left; else p=p->right; } Berilgen giltke teń túyin tabilǵan zatdı, element qosıw talap etiledi. Áke bolıwı múmkin túyinge q kórsetkish beriledi, elementtiń ózi bolsa jańa atlı kórsetkishi menen beriledi. node *q=new node; Qoyılıp atırǵan jańa element shep yamasa oń ul bolıwın anıqlaw kerek. If(keykey) q->left=jana; else q->right=jana; search=jana; return 0; Ekilik terekten element óshiriw funksiyası Túyindi óshirip taslaw nátiyjesinde terektiń tártiplengenligi buzılmawı kerek. Túyin terekte óshirilip atırǵanda 3 qıylı variant bolıwı múmkin: 1) Tabılǵan túyin terminal (japıraq). Bul jaǵdayda túyin atasınıń qaysı tárepinde turǵan bolsa, atasınıń sol tárepindegi shaxası óshiriledi hám túyinniń yadta jaylasqan tarawı tazalanadı. 2) Tabılǵan túyin tek ǵana bir ulǵa iye. Ol halda ul áke ornına jaylastırıladı. 3) Óshirilip atırǵan túyin eki ulǵa iye. Bunday jaǵdayda sonday bólim terekler zvenosın tabıw kerek, onı óshirilip atırǵan túyin ornına qoyıw múmkin bolsın. Bunday zveno mudamı bar boladı : - bul yamasa shep bólim terektiń eń oń tárepdegi elementi (bul zvenoga erisiw ushın keyingi ushına shep shaxa arqalı ótip, náwbettegi úshlarine bolsa, shaqırıq NULL bolmaǵansha, tek ǵana oń shaxaları arqalı ótiw zárúr ); - yamasa oń bólim terektiń eń shep elementi (bul zvenoga erisiw ushın keyingi ushına oń shaq arqalı ótip, náwbettegi úshlarina bolsa, shaqırıq NULL bolmaǵansha, tek ǵana shep shaxaları arqalı ótiw zárúr ). Paydalanılǵan ádebiyatlar: 1. Akbaraliev B.B. 5521900 “Informatika va axborot texnologiyalari” ta'lim yo'nalishi talabalari uchun “Ma'lumotlar tuzilmasi va algoritmlar” fanidan ma'ruzalar matni, Toshkent, 2008. 2. Xudoyberdiev M.X., Akbaraliev B.B., Yusupova Z.Dj. “Ma'lumotlar tuzilmasi va algoritmlar” fanidan amaliy mashg'ulotlar uchun topshiriqlar(uslubiy ko'rsatmalari bilan). Toshkent, 2013. 3. Akbaraliev B.B., Yusupova Z.Dj. “Ma'lumotlar tuzilmasi va algoritmlar” fanidan laboratoriya ishlarini bajarish bo'yicha uslubiy ko'rsatma. Toshkent, 2013. Download 124.9 Kb.

Download 124.9 Kb.