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

Проширена табела, један од најбескориснијих изума човечанства и један од честих задатака на колоквијумима из Алгоритама и структура података 2, први пут је формално дефинисана на страни 218 књиге "Алгоритми и структуре података" Мила V. Томашевића као структура коју је погодно користити "када је максимални број кључева у табели познат". Идеја повећане табеле јесте увођење низа битова поред сортираног низа који говоре да ли је кључ на некој позицији у том низу валидан, тј. да ли он заправо постоји у том низу или је само привидан кључ проширене табеле.

Нажалост, професорима и сарадницима на предмету је требало неколико година да се договоре око тога како се врше операције над овом табелом, и на овој страни се скупљају досадашњи закључци о начину њихове употребе како би се на колоквијумима и интегралним испитима остварио максимум бодова на овим задацима.

Претрага

Претрага у проширеној табели се врши као бинарна претрага, с тим што уколико се наиђе на кључ чији је бит валидности 0 морају се проверити (начин провере није одређен) претходни (алгоритам за уметање нам гарантује да ће само први кључ у секвенци истих кључева бити валидан) кључеви са том вредношћу, ако се нађе један са битом валидности 1 претрага је успешна, у супротном је претрага неуспешна.

Важно је напоменути да бинарна претрага не сме да се ради одокативно.

1. Мора се вршити по алгоритму из књиге. Уколико се не врши по алгоритму из књиге, препоручује се исписивање алгоритма бинарне претраге по којем се та претрага врши.
2. Пошто индексирање кључева може да измени крајњи кључ до којег се долази, битно је на барем једној табели назначити да ли се кључеви индексирају од 0 или од 1.
3. При дељењу непарног броја са 2 у бинарној претрази могуће је заокружити или на нижи или на виши број, са напоменом на који се број заокружује. Никако није дозвољено заокруживати час на нижи а час на виши број.

Уметање

При уметању се врши алгоритам попут оног за претрагу, с тим што се при успешној претрази баца грешка јер кључ већ постоји у табели. На месту где се стало с неуспешном претрагом се почиње са уметањем.

• Уколико је на месту за уметање броја бит валидности постављен на 1, проверава се да ли је кључ на којем се завршило мањи или већи од кључа који се умеће:
  1. Уколико је мањи, проверава се да ли је следећи чвор валидан. Уколико није валидан, уметање се извршава на том месту, а уколико јесте тај кључ и сви наредни валидни кључеви се померају за једно место удесно.
  2. Уколико је већи, постоје два могућа приступа, и оба би требало напоменути уколико се примењују:
     1. померити тај и све наредне валидне кључеве за једно место удесно, или
     2. погледати да ли лево од тренутног поља постоји кључ који није валидан и на том месту поставити кључ. Уколико ово није могуће, препоручује се конзистентно примењивање првог приступа.
• Уколико померање чворова за једно место удесно није могуће, поново су доступна два приступа која је потребно напоменути при примени:
  1. бацање грешке (чвор се неће уметнути у табелу уопште), или
  2. померање чворова који су потребни за ослобађање места за нови чвор улево (препоручено).
• Уколико је на месту за уметање броја бит валидности постављен на 0, опет постоје два приступа уметању у овом случају:
  1. уметање чвора на место до којег се дошло, или
  2. уметање чвора на средину интервала до којег се дошло, како би се умањила потреба за померањем кључева у будућности (препоручено).
• Након успешног одређивања места за уметање кључа, потребно је поставити бит валидности тог кључа на 1, све привидне кључеве који следе том кључу поставити на вредност тог кључа и све привидне кључеве који претходе том кључу поставити на вредност претходног валидног кључа. Уколико претходни валидан кључ не постоји, не радити ништа.
  • У књизи не пише да се табела на овај начин ажурира и уколико се након неуспешне претраге завршило на валидном кључу. При одлуци око примењивања процедуре изнад у том случају обавезно напоменути интерпретацију тог дела књиге.

Брисање

Брисање је једина једноставна операција са овом табелом. Приликом брисања, прво проверити да ли кључ постоји у табели и да ли му је бит валидности постављен на 1. Ако постоји и јесте постављен, поставити бит валидности на 0, у супротном бацити грешку.