АСП2/К1 2008

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

1. задатак

Поставка

(20п) Посматра се низ целобројних кључева, имплементиран у виду једноструко уланчане листе. Кључеви се умећу у произвољном редоследу, али није неопходно задржати поредак. Потребно је изабрати ефикасну методу претраге описаног низа. Од интереса су следећи параметри: брзина претраге, брзина уметања и брисања кључа, време режије. Разматрају се следећи приступи:

1. Бинарна претрага
2. Секвенцијална претрага са транспозицијом кључева

Коментарисати ефикасност понуђених метода према наведеним параметрима. За методу која се процени као боља скицирати поступак претраге на један кључ.

Решење

1. За бинарну претрагу је неопходно чувати уређену листу, па је и уметање и брисање кључа исте сложености, као и налажење кључа, што у случају уланчане листе није добра сложеност (своди се на секвенцијалну претрагу).
2. Секвенцијална претрага са транспозицијом кључева има много бољу сложеност за дату структуру - уметање је О(1). Брисање се своди на налажење па је сложеност О(н), а претрага је такође О(н), са могућим убрзањем уколико се често претражују исти елементи.

Пример секвенцијалне претраге на кључ 3 са транспозицијом

2. задатак

Поставка

(30п) У АВЛ стабло се редом умећу следећи кључеви: 30, 12, 15, 14, 22, 35,18, 26, 32, 20, 33, 31, 24, 25, 28, 27. Након уметања се редом бришу кључеви: 22, 15, 32. Приказати изглед стабла након сваке од наведених измена. Напомена: приликом брисања кључева, мењати им места са претходницима.

Решење

Уколико желите да задатак проверите корак по корак, то можете урадити на линку.

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

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

3. задатак

Поставка

(20п) Скицирати и објаснити алгоритам одређивања претходника задатог чвора у стаблу бинарног претраживања. Илустровати примерима различите случајеве.

Решење

Уколико чвор има лево подстабло, његов претходник је најдешњи потомак његовог левог сина, а уколико нема лево подстабло, његов претходник је његов најнижи предак чији је десни син такође његов предак. У примеру испод, претходник од 3 је 1, а претходник од 6 је 5.

Пример

4. задатак

Поставка

(30п) Питања:

1. Објаснити шта су самоподешавајућа стабла, принцип на којем су заснована и дискутовати перформансе.
2. Зашто се уводе 2-3 стабла? Објаснити њихову организацију и главне особине.
3. Дефинисати оптимално стабло бинарног претраживања и навести основну особину на којој се заснива алгоритам за његово одређивање.

Решење

1. Самоподешавајућа стабла су стабла бинарног претраживања код којих се распоред кључева заснива на временској локалности. То значи да се приликом сваке операције (уметање, брисање и претрага) тражени кључ, или њему најближи (уколико је у питању неуспешна операција) пребаци у корен низом ротација зиг или заг типа. Сложеност је О(н) у најгорем случају, јер се не гарантује балансираност стабла (немају никакав критеријум балансираности).
3. Оптимално стабло бинарног претраживања је оно стабло чија је цена најмања, где цену дефинишемо као: $C = \sum_{i}^{m-n} p_{i}(h_{i} + 1) + \sum_{i}^{m-n} q_{i}h_{i}$, где су Пи вероватноће приступа кључевима Кн...Км, а Qи вероватноће приступа екстерним чворовима. Особина на којој се заснива алгоритам за налажење оптималног стабла бинарног претраживања је да су сва подстабла оптималног стабла претраживања такође оптимална.