Hva er et binært tre?

Et binært tre er en type datastruktur som brukes i dataprogrammering for å lagre, sortere og få tilgang til informasjon. Binære trær er det enkleste variasjonen av tre, men er veldig nyttige og enkle å implementere. En typisk implementering av et binært tre er avhengig av en rotknute knyttet til en serie noder som utgjør selve treet av pekervariabler. Denne typen tre henter navnet fra det faktum at ingen node i treet kan ha mer enn to barn.

Treedatastrukturer kommer i mange varianter. De består av forskjellige noder, som er organisert i et hierarkisk mønster. En enkelt node, roten, er tilgangspunktet som hele datatreet kan søkes eller på annen måte manipuleres gjennom. Denne rotknuten peker på den øverste noden i selve treet.

Enhver node i et tre, bortsett fra den øverste noden, vil ha en overordnede node som er plassert over den i hierarkiet til treet. Den kan også ha barneknuter, som ligger under den. En gitt node er accessed gjennom de over det i treet og gir tilgang til de under det.

Binære tredatastrukturer lar hver node ikke ha mer enn to barn. En gitt node kan dermed ha null, en eller to barneknuter festet til den. Vanlige binære trær tillater noder med et hvilket som helst antall barn når som helst i treet. De legger heller ingen begrensninger for hvordan verdiene som er lagret i noder som utgjør et tre, er ordnet.

Datastrukturer er mest nyttige når de forbedrer hastigheten som data kan nås med en datamaskin, og modifiserte versjoner av binære trær brukes til å forbedre effektiviteten. Et binært søketre er et der alle dataverdier som er plassert på venstre synkende gren fra en gitt node har verdier som er lik eller mindre enn verdien som er lagret i den noden. Verdier på høyre side av en node i et ordnet binært tre må på sin side være større enn verdien ibasenoden. Denne databestillingen tillater at en mye mer effektiv søkealgoritme skal skrives.

Formen på et binært tre er også viktig for å bestemme effektiviteten til en søkealgoritme. Den minst effektive variasjonen av et binært tre er en der hver node bare har et enkelt barn. En datamaskin kan trenge å undersøke hvert dataelement i hele treet for å finne et enkelt stykke informasjon i denne konfigurasjonen. Det mest effektive binære treet, derimot, er et der hver node som sparer for de i bunnen av treet har to barn, og hvor alle bladknuter, bunnknuter i treet, er i samme avstand fra roten.