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