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, spar for 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 får tilgang til gjennom de over den i treet og gir tilgang til de under den.

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 omfatter et tre er ordnet.

Datastrukturer er mest nyttige når de forbedrer hastigheten som data kan nås av en datamaskin, og modifiserte versjoner av binære trær brukes tilforbedre 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 i basenoden.Denne databestillingen tillater at en mye mer effektiv søkealgoritme kan 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.