Binar terekler menen islew

ÓZBEKSTAN RESPUBLIKASÍ SANLI TEXNOLOGIYALAR MINISTRLIGI MUHAMMED AL-XOREZMIY ATINDAǴÍ TASHKENT INFORMACIYALÍQ TEXNOLOGIYALARÍ UNIVERSITETI NÓKIS FILIALÍ TELEKOMMUNIKACIYA TEXNOLOGIYALARI HÁM KÁSIPLIK TÁLIM FAKULTETI « Informaciyalıq qáwipsizlik» baǵdarı 2-kurs 305-22 topar studentı Shapiev Timurdıń « Maǵlıwmatlar strukturası hám algoritmleri » páninen jazılǵan ÓZ BETINSHE JUMÍSÍ

Tema:Binar terekler menen islew
Tayarlaǵan ______________ Shapiev T.
Qabıllaǵan _______________ Sársenbaeva H.
Nókis-2023

Reje:

1. 
   Terek, binar terek;
   
2. 
   Binar terek beriliwi hám oǵan mısal.
   

Uzeller (elementler) hám olardıń munasábetlerinen ibarat elementler kompleksiniń ierarxik strukturasına terek si’yaqli’ maǵlıwmatlar strukturası dep ataladı.

Terek - bul sonday sızıqsız baylanısqan maǵlıwmatlar strukturası boli’p, ol tómendegi belgileri menen xarakterlenedi:
- terekte sonday bir element bar, oǵan basqa elementlerden múrajat joq. Bul element terek túbiri dep ataladı ;
- terekte qálegen element shekli sandaǵı kórsetkishler járdeminde basqa
túyinlerge múrajat etiwi múmkin;
- terektiń hár bir elementi tek ǵana ózinden aldınǵı kelgen bir element penen
baylanısqan.
Binar terek – bul hár bir túyin maksimum 2 bala(child) elementine iye bolǵan terek berilgenler strukturasına aytamız. Bul degeni binary terektegi hár bir túyin bir yaki eki yaki ulıwma dawamshıǵa iye bolǵan túyinge aytamız. Binar terektegi hár bir túyin terektegi maǵlıwmatlar hám áwladlarǵa baǵdarlar (ssilkalar) dan dúzilgen. Jaǵdaylarına qarap balaların shep yaki oń balası dep aytamız. Binar terekte túyinler strukturası tómendegishe: Reference to the Left Child, Data, Reference to right Child. Terektiń diametri dep eki túyin arasındaǵı maksimal uzınlıqtaǵı jolǵa aytıladı. 1)Binar terek hár bir túyini shep hám oń terekke iye bolǵan túbirge iye terek bolıp tabıladı. Binar terektiń ushları terekti kórip shıǵıwdı túrli jollarına sáykes keletuǵın úsh tártibi bar bolıp: 1. Pre-order: Daslep túbir, keyin shep bólim terek, keyin oń bólim terek. 2. In-order: Daslep shep bólim terek, keyin túbir, keyin oń bólim terek. 3. Post-order: Daslep shep bólim terek, keyin oń bólim terek, keyin túbir. 2)Binar indekslengen terek yamasa Fenwick teregi massivtiń dinamikalıq variantı bolıp tabıladı. Ol massivte eki O(logn) waqıtlı ámeller qabıl etedi: aralıq sorawlardı esaplaw hám bahalardı jańalaw.Binar terektiń abzallıǵı sonda ol bizge nátiyjeli túrde massiv bahaların ózgertiw imkaniyatın beredi. 3)Segment tree eki ámel qabıl etetuǵın maǵlıwmatlar strukturası bolıp tabıladı: aralıq sorawdı ámelge asırıw hám massiv ma`nisin update qılıw. Segment terekler jıyındı sorawı, minimum soraw, maksimum soraw hám sol sıyaqlı basqa sorawlardı qabıl etedi jáne bulardıń barlıǵında O(logn) waqıtlı eki ámelden paydalanadı. Segment terek tómendegi úshlari massiv elementleri bolǵan hám qalǵan elementleri aralıq sorawların ámelge asırıwǵa kerek bolatuǵın bahalardan ibarat terek. Binar terekte túyinler strukturası tómendegishe:
Reference to the Left Child
Data
Reference to right Child
Terek n túyin hám n-1 qabırǵadan ibarat bolǵan baylanısqan graf bolıp tabıladı. Terektegi qálegen qabırǵanı alıp taslaw onı eki bólekke ajratadı, qálegen qabırǵani qosıw bolsa onı siklga aylandıradı. Sonıń menen birge hár qanday eki túyin ushın birden-bir jol bar.
Mısal ushın tómendegi terek 8 túyin hám 7 qabırǵadan ibarat

Terektiń japıraqları (LeafNode) dárejesi 1 bolǵan (bir qońsılasqa iye) túyinler bolıp tabıladı. Mısal ushın joqarıdaǵı terektiń japıraqları 3, 5, 7 hám 8 bolıp tabıladı.
Túbirge iye terekte (ParentNode), túyinlerden biri terektiń túbiri boladı hám qalǵan túyinler sol túbirge baylanisıp payda boladı. Mısal ushın, tómendegi terekte birinshi túyin túbir túyin esaplanadı.
Túbirge iye terekte, túyinniń balaları(ChildNode) onıń tómendegi qońsılasları bolıp tabıladı hám túyinniń ákesi onıń joqarıdaǵı qońsılası bolıp tabıladı. Ákesi joq túbir túyinnen tısqarı hár bir túyinniń birden-bir ákesi bar. Mısal ushın, joqarıdaǵı terekte 2-túyinniń balaları 5 hám 6 -túyin, ákesi bolsa 1-túyin.
Túbirge iye terektiń strukturası rekursiyalıq: terektiń hár bir túyini túyinniń ózi jáne onıń barlıq balaların saqlaytuǵın bólekterektiń túbiri boladı.
Mısal ushın, joqarıdaǵı terekte, 2-túyindi bólekteregi 2-5-6-8 túyinlerden ibarat. 29. Siziqli zilew algoritmi izbe-iz izlew alforitimi depte aytıladi hám bunda massivlerde berilgen elementti izlew judá ápiwayi usil bolip esaplanadi.
Bul algoritm elementti izlewde massivtegi há’r bir element penen izlenip atirǵan element tabilmaǵansha birme-bir salistiriw arqali isleydi.
Bunday algoritm kóbinese tártiplenbegen massivlerde qollaniladi. Máselen, A[ ] massivi tómendegi koriniste berilgen bolsin:
int A[ ] = { 10, 8, 2, 7, 3, 4, 9, 1, 6, 5};
Bul massivten 7 mánisin zilewdi qarastirayiq. Berilgen manis massivte bar, hám oniń massivtegi jaylasqan indeksi 3 ti qaytaradi.
Tómende bul algoritmniń psevdo kodi keltirilgen:
LINEAR_SEARCH(A, N, QIYMAT)
Adim 1: j = -1 //-1 mánisi element bar ekenligin bildiredi
Adim 2: i = 0 //1- elementten baslap izlew
Adim 3: Adim - 4 -ti while IAdim 4: Eger A[I] = QIYMAT //elementti salistiriw
j = i //indeksti eslep qaliw
break;
Qadem 6 ǵa ótiw
I = I + 1 // keyingi elementke ótiw
Adim 5: Eger j = -1 // di tekseriw
Baspaģa Shiģariw " Berilgen manis massivte joq. "
Adim 6: SHIǴIW
Binar izlew algoritmi
Massivtegi qandayda bir elementti izlewdi eń ápiwayı usılı for ciklında massivti barlıq elementlerin kórip shıǵıw bolıp tabıladı.
Mısal ushın tómendegi kod massivten x elementti izleydi:
Bul kodtıń time limiti O(n), sebebi izlenip atırǵan element aqırǵı kelgen jaǵdayda barlıq elementlerdi kórip shıǵıw kerek. Eger massiv elementleri qálegen tártipte bolsada, sol usıldı qollaw kerek boladı, sebebi massivtiń qay jerinen x elementti izlewimiz haqqında bizde maǵlıwmat bolmaydı.
Biraq massiv tártiplengen bolsa jaǵday basqasha boladı. Bul jaǵdayda izlewdi tezirek ámelge asırsa boladı, sebebi elementler tártibi izlewge baǵdar berip turadı. Tómendegi binar izlew tártiplengen massivte elementi O (log n) waqıtta izleydi
Binar izlewdi ámelge asırıwdı ádetdegi usılı sózlikten sóz qıdırıwǵa uqsaydı. Ol jaǵdayda mudamı kirgiziwdi ekige bóletuǵın adımlar atqarıladı.
Hár bir adımda aktiv bólektiń orayındaǵı element kóriledi. Eger ortadaǵı element izlenip atırǵan element bolsa, izlew toqtatıladı. Keri jaǵdayda, izlew rekursiv túrde oraydaǵı elementke qaray massivtiń oń yamasa shep yarımına kóshedi. Joqarıdaǵı pikir tómende ámelge asırılǵan:
Bul kodta aktiv bólim (a..b) basqasha etip aytqanda 0…n-1. Algoritm hár adımda kirgiziwdi ekige bóledı, sol sebepli asimptotika O(log n).
2-usıl
Binary search ti ámelge asırıwdıń basqa usılı massivtiń elementlerin qayta-qayta tákirarlap shıǵıwdıń nátiyjeli usılına tiykarlanǵan. Ideya sekiriwlerdi ámelge asırıw hám nıshan elementine jaqınlasǵanda tezlikti tómenletiw bolıp tabıladı.
Izlew shep tárepten ońǵa massiv arqalı ámelge asırıladı hám baslanǵısh sekiriwdiń uzınlıǵın 1/2 ge teń. Hár bir adımda sekiriw uzınlıǵı yarımǵa azayıp baradı: birinshini 1/4. Keyingini 1/8, n/16 t.b. hám aqır-aqıbetde uzınlıq 1 ge teń bolaman degenge shekem. Sekiriwlerden keyin yamasa nıshan elementi tabıladı yamasa biz bilgenimizdey ol massivte payda bolmaydı. Tómendegi kod joqarıdaǵı ideyanı ámelge asıradı.
Izlew dawamında, ózgeriwshi b ámeldegi sekiriw uzınlıǵın óz ishine aladı. Bul programmanıń time limiti O(logn). “While loop” dagi kod hár bir sekiriw uzınlıǵı ushın eń kóbi menen eki ret ámelge asırıladı.
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. 
   Akbaraliev B.B., Yusupova Z.Dj. “Ma'lumotlar tuzilmasi va algoritmlar” fanidan laboratoriya ishlarini bajarish bo'yicha uslubiy ko'rsatma. Toshkent, 2013.
   
3. 
   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.