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. [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
muudaKahendotsingupuu
muudaKahendotsingupuu 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
muudaB-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(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
muudaKolmendotsingupuu 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
muudaVõtme järgi otsimine
muudaEeldusel, 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
muudasearch-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
muudasearchIterative(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
muudaJärjestatud puude puhul asub miinimum vasakpoolseimas tipus ning maksimum parempoolseimas tipus.
Miinimum
muudafindMinimum(node) if node is NULL return EMPTY_TREE min := node while min.left is not NULL min := min.left return min.key
Maksimum
muudafindMaximum(node) if node is NULL return EMPTY_TREE max := node while max.right is not NULL max := max.right return max.key
Viited
muuda- ↑ Wikipedia (2004). "Search Tree" (Inglise keeles).
{{netiviide}}
: CS1 hooldus: tundmatu keel (link) - ↑ Black, Paul and Pieterse, Vreda (2005). "Dictionary of Algorithms and Data Structures" (Inglise keeles).
{{netiviide}}
: CS1 hooldus: mitu nime: autorite loend (link) CS1 hooldus: tundmatu keel (link)