АСП2/Проширена табела
Proširena tabela,[1] jedan od najbeskorisnijih izuma čovečanstva i jedan od čestih zadataka na kolokvijumima iz Algoritama i struktura podataka 2, prvi put je formalno definisana na strani 218 knjige "Algoritmi i strukture podataka" Mila V. Tomaševića kao struktura koju je pogodno koristiti "kada je maksimalni broj ključeva u tabeli poznat". Ideja povećane tabele jeste uvođenje niza bitova pored sortiranog niza koji govore da li je ključ na nekoj poziciji u tom nizu validan, tj. da li on zapravo postoji u tom nizu ili je samo prividan ključ proširene tabele.
Nažalost, profesorima i saradnicima na predmetu je trebalo nekoliko godina da se dogovore oko toga kako se vrše operacije nad ovom tabelom, i na ovoj strani se skupljaju dosadašnji zaključci o načinu njihove upotrebe kako bi se na kolokvijumima i integralnim ispitima ostvario maksimum bodova na ovim zadacima.
Pretraga
Pretraga u proširenoj tabeli se vrši kao binarna pretraga, s tim što ukoliko se naiđe na ključ čiji je bit validnosti 0 moraju se proveriti (način provere nije određen) prethodni (algoritam za umetanje nam garantuje da će samo prvi ključ u sekvenci istih ključeva biti validan) ključevi sa tom vrednošću, ako se nađe jedan sa bitom validnosti 1 pretraga je uspešna, u suprotnom je pretraga neuspešna.
Važno je napomenuti da binarna pretraga ne sme da se radi odokativno.
- Mora se vršiti po algoritmu iz knjige. Ukoliko se ne vrši po algoritmu iz knjige, preporučuje se ispisivanje algoritma binarne pretrage po kojem se ta pretraga vrši.
- Pošto indeksiranje ključeva može da izmeni krajnji ključ do kojeg se dolazi, bitno je na barem jednoj tabeli naznačiti da li se ključevi indeksiraju od 0 ili od 1.
- Pri deljenju neparnog broja sa 2 u binarnoj pretrazi moguće je zaokružiti ili na niži ili na viši broj, sa napomenom na koji se broj zaokružuje. Nikako nije dozvoljeno zaokruživati čas na niži a čas na viši broj.
Umetanje
Pri umetanju se vrši algoritam poput onog za pretragu, s tim što se pri uspešnoj pretrazi baca greška jer ključ već postoji u tabeli. Na mestu gde se stalo s neuspešnom pretragom se počinje sa umetanjem.
- Ukoliko je na mestu za umetanje broja bit validnosti postavljen na 1, proverava se da li je ključ na kojem se završilo manji ili veći od ključa koji se umeće:
- Ukoliko je manji, proverava se da li je sledeći čvor validan. Ukoliko nije validan, umetanje se izvršava na tom mestu, a ukoliko nije taj ključ i svi naredni validni ključevi se pomeraju za jedno mesto udesno.
- Ukoliko je veći, postoje dva moguća pristupa, i oba bi trebalo napomenuti ukoliko se primenjuju:
- pomeriti taj i sve naredne validne ključeve za jedno mesto udesno, ili
- pogledati da li levo od trenutnog polja postoji ključ koji nije validan i na tom mestu postaviti ključ. Ukoliko ovo nije moguće, preporučuje se konzistentno primenjivanje prvog pristupa.
- Ukoliko pomeranje čvorova za jedno mesto udesno nije moguće, ponovo su dostupna dva pristupa koja je potrebno napomenuti pri primeni:
- bacanje greške (čvor se neće umetnuti u tabelu uopšte), ili
- pomeranje čvorova koji su potrebni za oslobađanje mesta za novi čvor ulevo (preporučeno).
- Ukoliko je na mestu za umetanje broja bit validnosti postavljen na 0, opet postoje dva pristupa umetanju u ovom slučaju:
- umetanje čvora na mesto do kojeg se došlo, ili
- umetanje čvora na sredinu intervala do kojeg se došlo, kako bi se umanjila potreba za pomeranjem ključeva u budućnosti (preporučeno).
- Nakon uspešnog određivanja mesta za umetanje ključa, potrebno je postaviti bit validnosti tog ključa na 1, sve prividne ključeve koji slede tom ključu postaviti na vrednost tog ključa i sve prividne ključeve koji prethode tom ključu postaviti na vrednost prethodnog validnog ključa. Ukoliko prethodni validan ključ ne postoji, ne raditi ništa.[2]
Brisanje
Brisanje je jedina jednostavna operacija sa ovom tabelom. Prilikom brisanja, prvo proveriti da li ključ postoji u tabeli i da li mu je bit validnosti postavljen na 1. Ako postoji i jeste postavljen, postaviti bit validnosti na 0, u suprotnom baciti grešku.