Računalništvo 1

Ne, tudi v drugem izrazu so lahko oklepaji.

Če je znak, ki ga pregledujemo oklepaj in je naslednji znak prav tako oklepaj, v tabelo s predznaki dodamo zadnji element tabele (to v primeru, da je pred prvim oklepajem - ali pa +).

Naloga predpostavlja, da se vsaka črka pojavi samo enkrat. Ja morali bi pregledovati število pojavitev vsake črke tako z znakom plus, kot minus – to seveda le za tisti izraz, ki ga nato zapišemo v obliki slovarja (npr. za izraz = '-b+b' bi potem slovar izgledal takole slovar = {'b' : {'+': 1, '-': 1}}).

V oklepaju smo, če dolžina tabele ni enaka 0. Če je pred ugnezdenim oklepajem predznak, ga vstavimo v tabelo. Če pa je pred njem oklepaj pa v tabelo ponovno vstavimo zadnji element tabele.

Zaradi preverjanja enakosti izrazov saj je lahko vrstni red črk v izrazih različen, kar ne bi bilo ugodno za primerjanje dveh skladov med seboj.

To sem že odgovorila pri prejšnjem vprašanju.

V najslabšem primeru je O(n), ko imamo izrojeno drevo. V najboljšem primeru pa O(1) takrat, ko gledamo koren drevesa, ki pa nima desnega poddrevesa ali pa je njegovo desno poddrevo samo njegov desni sin. Prav tako, če iščemo naslednika levega sina korena, ki nima desnega poddrevesa.

Časovna zahtevnost uravnoteženega dvojiškega iskalnega drevesa je O(logn) saj v vsakem koraku izgubimo polovico možnosti.

Sam način iskanja je enak, samo da pri enemu rekurzivno kličemo poddrevesa, ko iščemo iskano vozlišče. Prav tako je prostorska zahtevnost večja zaradi rekurzivnih klicov.

Iskali smo naslednika glede na vmesni pregled. Torej ko algoritem najde iskani element, moramo mi vrniti isti element, kot bi bil naslednji na vrsti glede na vmesni pregled.

Narediti bi morali nov algoritem, ki bi pa bil dokaj podoben našemu. Če pogledamo iterativno verzijo, bi iskanje elementa potekalo enako kot pri nasledniku, edina razlika bi bila, da si kot možnega prednika označimo tisti koren, ki je manjši od iskanega elementa. Potem pa ko bi našli iskan element bi najprej preverili, če ima naše vozlišče levo poddrevo. Če ga ima bi vrnili največji element v levem poddrevesu, torej premikali bi se desno po poddrevesu dokler bi se lahko in tako dobili prednika. Če pa nima levega poddrevesa, bi pa vrnili zadnji element, ki smo si ga shranili kot prednika. Če pa nima ne enega ne drugega pa vemo, da naš element nima prednika.

Bolj zahtevna bi rekel, da je rekurzivna, saj si je težje shranjevati možne naslednike.

Rekurzivni algoritem ima večjo prostorsko zahtevnost, saj daje rekurzivne klice v sklade. Časovno zahtevnost pa imata enako.

Problem predvideva, da če števila ni v drevesu, vrnemo kot naslednika naslednje večje število od iskanega.

Algoritem vrne naslednika glede na vmesni pregled.