Binært søgetræ

Et binært søgetræ er en forholdsvis enkel træstruktur til opbevaring af data. Dette er den største fordel. Ulemperne er, at træets effektivitet er afhængig af indsættelsesrækkefølgen, og hver knude kun refererer til to knuder på næste niveau, hvilket giver et ret højt træ.

Søgning 
I et binært søgetræ laves søgningen nemmest som en rekursiv funktion. Start ved roden og brug denne algoritme:

 Hvis søgetræet er tomt, blev data ikke fundet
 Hvis nøglen i den aktuelle knude er lig med søgenøglen er data fundet
 Hvis nøglen er mindre end nøglen i den aktuelle knude, så gentag søgningen i det venstre undertræ
 Hvis nøglen er større end nøglen i den aktuelle knude, så gentag søgningen i det højre undertræ

Sekventiel gennemgang 
Hvis alle knuder i et søgetræ skal behandles, kan det ske i tre rækkefølger:
 Pre-orden – Først behandles den aktuelle knude, så det venstre undertræ og til sidst det højre
 In-orden – Først behandles venstre undertræ, så den aktuelle knude og til sidst højre undertræ
 Post-orden – Først behandles venstre og højre undertræ og til sidst den aktuelle knude

Gennemgang af træet i in-orden giver data i sorteret rækkefølge. Hvis data skrives til en fil i post-orden, vil søgetræet kunne genskabes ved at indsætte data i samme rækkefølge, som de ligger i filen. Gennemgang i pre-orden er praktisk, hvis hele søgetræet skal slettes.

Indsættelse af data 
Når data skal indsættes bruges en variant af søgerutinen. Forskellen består i, at der hele tiden vedligeholdes en reference til den foregående knude. Efter endt søgning kan der opstå to situationer.

 Hvis der ikke er data, med samme nøgle som det nye dataelement, er den foregående knude det sted, hvor der skal tilføjes nye data. Den nye knude placeres til højre eller venstre alt efter om nøglen er større eller mindre end nøglen i den foregående knude.

 Hvis der er data med samme nøgle som i det nye element, er der tale om en dublet. Hvis der tillades dubletter, kan de nye data indsættes enten til højre eller venstre. Det skal blot være konsekvent.

Sletning af data 
Hvis hele det binære træ skal fjernes, er fremgangsmåden ret enkel. Man kan bruge en rekursiv algoritme:

 Hvis søgetræet er tomt, så stop
 Slet alle elementer i det ene undertræ
 slet alle elementer i det andet
 Slet den aktuelle knude

Algoritmen forudsætter, at referencer, der ikke længere peger på en knude, kan genkendes.

Sletning af enkelte elementer 
Sletning af en enkelt knude kan være besværlig. Der er tre situationer, at tage hensyn til:

 Knuden er en bladknude. I dette tilfæde fjernes referencen til knuden og knuden slettes.
 Knuden refererer til en anden knude. Da der kun refereres til en anden knude, kan knuden slettes som om den var en del af en kædet liste.
 Knuden refererer til to andre knuder. Dette er det besværlige tilfælde. For at undgå at tabe et par undertræer bliver selve knuden ikke slettet. I stedet findes knuden med den største nøgle i det venstre (nøglemæssigt mindste) undertræ. Denne knudes indhold kopieres over i den knude, der skulle slettes. Den knude, der blev kopieret fra er en bladknude, så den fjernes let.

Kilder 
 File organization and Processing af Allan L. Tharp 
 Pascal Plus Datastructures, Algorithms and Advanced Programming af Nell Dale og Susan C. Lilly 

Datastrukturer