АСП2/Проширена табела

Proširena tabela, 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.

1. 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.
2. 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.
3. 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:
  1. Ukoliko je manji, proverava se da li je sledeći čvor validan. Ukoliko nije validan, umetanje se izvršava na tom mestu, a ukoliko jeste taj ključ i svi naredni validni ključevi se pomeraju za jedno mesto udesno.
  2. Ukoliko je veći, postoje dva moguća pristupa, i oba bi trebalo napomenuti ukoliko se primenjuju:
     1. pomeriti taj i sve naredne validne ključeve za jedno mesto udesno, ili
     2. 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:
  1. bacanje greške (čvor se neće umetnuti u tabelu uopšte), ili
  2. 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:
  1. umetanje čvora na mesto do kojeg se došlo, ili
  2. 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.

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.