Opplysningene er ofte lagret i binære trestrukturer som bruker spesialiserte algoritmer . Mange fordeler kommer fra lagring av data i en trestruktur. For eksempel søker en sortert binært tre er mye raskere enn sortering en sekvensiell data struktur som en matrise. Et tre datastruktur kan anta mange typer mønstre i løpet av tilgang til data og modifisering. Å forstå disse mønstrene kan hjelpe deg å designe bedre algoritmer for å optimalisere et tre algoritme . Grunnleggende komponentene i en Binary Tre

binærtreet består av noder , som lagrer data og peker på andre noder i treet. Rotnoden er utgangspunktet av treet og ligger i øverste nivå . Det kan ha opptil to barn noder . Disse underordnede noder kan også ha opptil to barn noder . Antallet barn noder av en gitt node er kalt graden av noden . En node uten noen barn og en grad av null , kalles et blad . Lengden i knutepunkter fra rotnoden til lengst bladnoden er høyden av treet. Dybden i en node er avstanden fra rotnoden til den. Hver node som har samme dybde sies å være på samme nivå .
Full Binary Tre

En full binært tre er et tre der hver node har nøyaktig to eller null barn . Med andre ord har hver node enten to barn eller er et blad . Et eksempel på et komplett binært tre er Binary Decision Diagram, eller BDD .
Perfect Binary Tre

En perfekt binært tre har de samme egenskapene til fullstendig binært tre , men alle de bladnoder er på samme nivå , noe som betyr at dybden av alle bladene er den samme i en perfekt binært tre . Siden det er også et komplett binært tre , alle noder unntatt løvnodene har en grad av to .
Balansert Binary Tre

En balansert binært tre er en der dybden av hvert blad node er enten den samme eller forskjellig fra en verdi på en. Legge til og fjerne noder fra et balansert binært tre kan ubalanse det, så en rekke justeringer kalles rotasjoner må finne sted for å balansere treet. Å holde et tre balanserte sikrer at den gjennomsnittlige søketiden for en hvilken som helst node er optimal. Betydelig overhead er nødvendig for å opprettholde balansen i et tre.
Degenerate Binary Tre

utarte binært tre er en der hver node unntatt bladnoden har nøyaktig en barnenode . Den har de samme egenskapene til en lenket liste , noe som øker søketiden for enhver node med et betydelig beløp . For eksempel vurdere en sak der noden som søkte etter er bladnoden . Hele treet må bli krysset for å finne denne noden . Med en balansert binært tre , å finne en løvnode krever bare en rekke node gjennomløping lik dybden av bladnoden . Med store trær , kan forskjellen i ytelse være betydelig.