Binært søgetræ

Binært træ med 4 niveauer

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:

1. Hvis søgetræet er tomt, blev data ikke fundet
2. Hvis nøglen i den aktuelle knude er lig med søgenøglen er data fundet
3. Hvis nøglen er mindre end nøglen i den aktuelle knude, så gentag søgningen i det venstre undertræ
4. 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:

1. Hvis søgetræet er tomt, så stop
2. Slet alle elementer i det ene undertræ
3. slet alle elementer i det andet
4. 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.

Tidskompleksitet

Operation	Relativ tid
Find	O(log2 N)
Indsæt	O(log2 N)
Slet	O(log2 N)

Kilder

• File organization and Processing af Allan L. Tharp ISBN 0-471-61766-0
• Pascal Plus Datastructures, Algorithms and Advanced Programming af Nell Dale og Susan C. Lilly ISBN 0-669-24830-4