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 muuda
Kahendotsingupuu muuda
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
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
(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
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
Võtme järgi otsimine muuda
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
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
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
Järjestatud puude puhul asub miinimum vasakpoolseimas tipus ning maksimum parempoolseimas tipus.
Miinimum muuda
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
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
- ↑ 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)