E-mail : [email protected] TALLINN 2000 ÜLESANDE TINGIMUSED 1. paigutada lauses olevad snad paisktabelisse (maht T=31 sõna); 1. aadressi leidmisel kasutada järgmist kodeerimist: 2. arvestatakse kahte esimest sümbolit, 3. sümbolid kodeeritakse järgnevalt: a 1, b 2, ..., z 26, tühik 0; suur- ja väiketähed on ekvivalentsed 4. paiskfunktsioon arvutatakse järgmiselt: h = 1.täht * 27 + 2.täht 5. primaaraadress arvutatakse järgmiselt: f = h mod T, kus T- tabeli maht; 2. kollisioonid lahendatakse järgmiselt: 1. sammuga 1, 2. sammuga s (algandmetest), 3. samm arvutatakse s= ( h mod (T-2) ) + 1, 4. kasutatakse 3-elemendilisi pakette (tabeli maht T=33 sõna). ALGANDMED Samm s = 21 12) the 26) much
vasakuks lapseks 3. pööre paremale - tipu Y vasak laps saab uueks (alam)puu juureks ning Y ise satub tema paremaks lapseks 13.7.3 Milleks kasutatakse Praktikas üks enam kasutatavatest isebalanseeruvatest otsimispuudest. Konteinerites “set” ja “map”. C++: STL library, Javas: klass “TreeMap” ja muudes realisatsioonides, kus on vaja kasutada assotsatiivset massiivi. 14. Paisksalvestusmeetod. Paisktabel. Paiskfunktsioon (jäägi meetod ja korrutamise meetod). Kollisisoonide lahendamine (ahelad väljaspool tabelit, avatud paisksalvestus ja erinevad sondeerimismeetodid). Andmete lisamine, otsimine ja kustutamine. 14.1 Paisksalvestusmeetod Def – algoritm, mis paneb suvalise pikkusega andmehulga vastavusse fikseeritud pikkusega andmehulgaga. • Mõistlik kasutada siis, kui struktuur, millega tegeldakse ei pea võimaldama muud kui lisamist,
Iga puu tipp on värvitud punaseks või mustaks. Jälgides tippude lisamisel ja kustutamisel teatud värvide skeemi saab säilitada puu mõistliku seisu. Reeglid – iga sõlm kas punane või must; tühjad alampuud on mustad; igal punasel sõlmel must vanem & mustad lapsed; iga tee, mis läheb puu juurest mõnda lehte, sisaldab sama arv musti sõlmi. Otsimise aeg 2*log(n+1). Puu must kõrgus – mustade tippude arv puu juurest leheni. 13. Paisksalvestusmeetod. Paisktabel. Paiskfunktsioon (jäägi meetod ja korrutamise meetod). Kollisioonide lahendamine (ahelad väljaspool tabelit, avatud paisksalvestus). Andmete lisamine, otsimine ja kustutamine. Paisksalvestusmeetod – igas kirjes eraldatakse üks väli, mis on võtmeks. Sellele võtmele rakendatakse paiskfn-i, mis vastavalt võtme väärtusele arvutab indeksi ehk tabeli lahtri aadressi. Paiskfn tuleb valida nii, et arvutuse tulemus mahuks tabeli indeksite vahemikku
annaabi.ee 
