Претрага стабла

У информатици, претрага стабла је структура података која се користи за налажење одређене вредности унутар скупа. Да би стабло функционисало као стабло за претрагу, кључ сваког чвора мора бити већи од свих кључева у левом подстаблу и мањи од свих кључева у десном подстаблу.^[1]

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

Врсте стабала

Бинарно стабло претраге

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

Временска сложеност за претрагу у бинарном стаблу претраге је у просеку $O(logn).$

Б-стабла

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

Због променљивог распона броја потомака, Б-стабла су оптимизована за системе који читају велике блокове података. Користе се и у базама података.

Временска сложеност за претрагу у Б-стаблу је $O(logn)$

(а, б)-стабло претраге

(а, б)-стабло је структура у којој су сви њени листови на истој дубини. Сваки чвор има најмање а-потомака и највише б-потомака, док корен има најмање 2 потомка, а највише б-потомака.

а и б може одлучивати следећом формулом:^[2]

$2\leq a\leq {\frac {(b+1)}{2}}$

Временска сложеност претраге (а, б)-стабла је $O(logn)$

Тернарно стабло претраге

Тернарно стабло претраге је тип стабла које има 3 чвора: мањег сина, истог сина и већег сина. Сваки чвор чува један знак и само стабло је у редоследу као и бинарно стабло претраге, само је изузетак могућност трећег чвора.

Претрага тернарног стабла претраге обухвата пребацивање у ниску ради тестирања да ли пут садржи тражени кључ. Временска сложеност претраге је $O(logn)$

Алгоритми за претрагу

Претрага вредности

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

Псеудокодови за проналазак кључа имплементирани на рекурзивни и итеративни начин:

Рекурзивна имплементација

search-recursive(key, node)
    if node is NULL
        return EMPTY_TREE
    if key < node.key
        return search-recursive(key, node.left)
    else if key > node.key
        return search-recursive(key, node.right)
    else
        return node

Итеративна имплементација

searchIterative(key, node)
    currentNode := node
    while currentNode is not NULL
        if currentNode.key = key
            return currentNode
        else if currentNode.key < key
            currentNode := currentNode.left
        else
            currentNode := currentNode.right

Претрага најмањег и највећег елемента

У сортираном стаблу, намањи елемент је лист који се налази скроз лево, а највећи елемент је лист који се налази скроз десно.^[3]

Псеудокодови за налазак најмањег и највећег елемента:

Претрага најмањег

findMinimum(node)
    if node is NULL
        return EMPTY_TREE
    min := node
    while min.left is not NULL
        min := min.left
    return min.key

Претрага највећег

findMaximum(node)
    if node is NULL
        return EMPTY_TREE
    max := node
    while max.right is not NULL
        max := max.right
    return max.key

Види још

Референце

^ Блацк, Паул анд Пиетерсе, Вреда (2005). „сеарцх трее”. Дицтионарy оф Алгоритхмс анд Дата Струцтурес
^ Тоал, Раy. „(а, б) Треес”
^ Гилдеа, Дан (2004). „Бинарy Сеарцх Трее”

[1] Блацк, Паул анд Пиетерсе, Вреда (2005). „сеарцх трее”. Дицтионарy оф Алгоритхмс анд Дата Струцтурес

[2] Тоал, Раy. „(а, б) Треес”

[3] Гилдеа, Дан (2004). „Бинарy Сеарцх Трее”

[1]

[2]

[3]