Binære træer

Binære træer er datastrukturer i form af træer, hvor hver forgrening højst har to deltræer. Er træet yderligere balanceret, dvs. alle deltræer har samme dybde (et B-træ), benævnes det AVL træ efter ophavsmændene Adelson, Velskij og Landis. Disse datastrukturer er bekvemme i forbindelse med søgning, da den maksimale søgevej højst kan få en længde, der er totalslogaritmen til antallet af elementer.

Binære træer benyttes i indekseringsmetoder for filsystemer og databasesystemer. Nøglerne opbygges i to niveauer: et sekvenssæt og et indekssæt. Sekvenssættet er et enkeltniveauindeks til data, som giver hurtig sekventiel adgang til disse. Indekssættet indeholder en træstruktur af nøglerne til sekvenssættet og giver derfor hurtig direkte adgang til dette.