Kasutaja:HendrikTU/Otsingupuud

Arvutiteaduses nimetatakse otsingupuud andmestruktuuriks, mida kasutatakse hulgast võtme järgi otsimiseks. Selleks, et puu toimiks otsingupuuna, peab iga tipu võti olema suurem kui mistahes selle tipu vasakpoolses alampuus oleva tipu võti ja väiksem kui mistahes selle tipu parempoolses alampuus oleva tipu võti.

Kui puu on võrdlemisi tasakaalus, on otsingupuude eeliseks nende efektiivne ajakulu. On olemas erinevaid selliseid andmestruktuure, mis võimaldavad efektiivselt elemente kustutada või lisada.

Puutüübid

Kahendotsingupuu

Kahendotsingupuu

Kahendotsingupuu on tipupõhine andmestruktuur, kus igal tipul on võti ja kaks alampuud: vasak- ja parempoolne. Iga tipul peab olema võti suurem kui selle tipu vasakpoolses alampuus oleva tipu võti ja väiksem kui parempoolses alampuus oleva tipu võti.

Kahendpuust otsimise ajaline keerukus on halvimal juhul puu kõrgus. See võib olla nii väike, kui O(log n) n elemendiga puu puhul.

B-puu

B-puu on kahendotsingupuu üldistus, kuna igal tipul võib olla mistahes arv alampuid. B-puud võivad potentsiaalselt ruumi raisata, kuna kõik tipud ei sisalda ilmtingimata andmeid. B-puid ei ole vaja nii tihti tasakaalustada kui teisi tüüpi puid.

Ajaline keerukus B-puude puhul on O(log n).

(a,b)-puu

(a,b)-puu on otsingupuu, kus kõik lehed on sama sügavusega. Igal tipul on vähemalt a ja ülimalt b last ning juurel on vähemalt 2 ja ülimalt b last.

Kolmendotsingupuu

Kolmendotsingupuu on puu, mille igal tipul võib olla 3 last. Igas tipus on üks tähemärk ning puu ülesehitus on sarnane kahendotsingupuuga, kuid kolmendotsingupuul võib olla kolmas tipp.

Ajaline keerukus kolmendotsingupuude puhul on O(log n).

Otsingualgoritmid

Võtme järgi otsimine

Eeldusel, et puu on järjestatud, saame me võtta võtme ja otsida seda puust. Järgnevad algoritmid on kirjutatud kahendotsingupuudeks, kuid sarnane idee kehtib ka muude otsingupuude puhul.

Rekursiivne

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

Iteratiivne

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

Miinimumi ja maksimumi otsimine

Järjestatud puude puhul asub miinimum vasakpoolseimas tipus ning maksimum parempoolseimas tipus.

Miinimum

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

Maksimum

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