Kasutaja:HendrikTU/Otsingupuud

Allikas: Vikipeedia
Jump to navigation Jump to search

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. [1]


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. [2]

Puutüübid[muuda | muuda lähteteksti]

Kahendotsingupuu[muuda | muuda lähteteksti]

Binary search tree
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[muuda | muuda lähteteksti]

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[muuda | muuda lähteteksti]

(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[muuda | muuda lähteteksti]

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[muuda | muuda lähteteksti]

Võtme järgi otsimine[muuda | muuda lähteteksti]

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[muuda | muuda lähteteksti]

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[muuda | muuda lähteteksti]

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[muuda | muuda lähteteksti]

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

Miinimum[muuda | muuda lähteteksti]

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

Maksimum[muuda | muuda lähteteksti]

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

Viited[muuda | muuda lähteteksti]

  1. Wikipedia. "Search Tree". 2004. Inglise keeles.
  2. Black, Paul and Pieterse, Vreda. "Dictionary of Algorithms and Data Structures". 2005. Inglise keeles.