АСП2/К1 2011

Први колоквијум 2011. године одржан је 24. октобра 2011. Поставка задатака је доступна са странице предмета.

1. задатак

Поставка

(30п) Користећи алгоритам бинарне претраге уређеног вектора као основу, написати на језику C (или C++) функцију за претрагу уређеног вектора јединствених целобројних кључева дужине н на задати кључ дељењем интервала претраге на три подинтервала приближно једнаке дужине. Написати главни програм који демонстрира употребу претходне функције. Користити фиксне податке (није потребно читати податке из датотеке или стандардног улаза). Коментарисати временску и просторну сложеност написане функције. Поредити временску сложеност написане функције и алгоритма бинарне претраге.

Решење

Временска сложеност је $O(log_3{n})$, а просторна $O(n)$.

FUN(arr, key)
high = n;
low = 1;
while(low <= high)
    left = (low+high)/3;
    right = 2(low+high)/3;
    if(arr[left]=key) return left;
    if(arr[right]=key) return right;
    if(key < arr[left]) high = left-1;
    if(key > arr[right]) low = right+1;
    if(key>arr[left] and key<arr[right])
        low = left+1;
        high = right-1;
    end_if
end_while
return 0;

2. задатак

Поставка

(20п) У стабло бинарног претраживања се редом умећу следећи кључеви: 22, 31, 24, 28, 26, 41, 45, 10, 6, 8, 9, 7, 4, 5, 2. Након уметања се редом бришу кључеви: 41, 6, 22, 10. Приказати изглед стабла претраживања након сваке од наведених измена. Ако добијено стабло не задовољава критеријум балансираности АВЛ стабла, трансформисати стабло применом основних трансформација за одржавање балансираности да би се добило АВЛ стабло. Приказати изглед стабла након примене сваке трансформације. Напомена: приликом брисања кључева, користити следбенике.

Решење

Стабло након уметања кључева 22,31,24,28,26 и 41

Стабло након уметања кључева 45,10,6 и 8

Стабло након уметања кључева 9 и 7

Стабло након уметања кључева 4 и 5

Стабло након свих уметања

Стабло након брисања кључева 41,6 и 22

Стабло након свих брисања

3. задатак

Поставка

(20п) Дефинисати АВЛ стабло и критични чвор. Када се јавља потреба за двоструком ротацијом? Објаснити ову операцију и илустровати општим сликама.

Решење

АВЛ стабло је стабло бинарног претраживања које испуњава критеријум да сваки чвор мора да има баланс 0, 1 или -1, где баланс представља разлику висина левог и десног подстабла.

Критични чвор је корен најмањег подстабла које није висински балансирано.

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

Почетно стање

Стабло након прве ротације удесно око сина

Стабло након ротације улево око критичног чвора

4. задатак

Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.

Поставка

(30п) Питања:

1. Дати псеудокод и објаснити секвенцијално претраживање са граничником. Какво побољшање оно доноси?
2. Објаснити организацију 2-3-4 стабла. Каква је њихова предност и како се имплементирају?
3. Објаснити стратегију добијања приближно оптималног стабла која узима у обзир и успешна и неуспешна претраживања.

Решење

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