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ærtrær er den enkleste tresorten, men er veldig nyttige og enkle å implementere. En typisk implementering av et binært tre er avhengig av en rotnode som er koblet til en serie noder som utgjør selve treet av pekervariabler. Denne typen tre henter navnet sitt fra det faktum at ingen node i treet kan ha mer enn to barn.

Tredatasstrukturer 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 gjennom eller på annen måte manipuleres. Denne rotnoden peker mot den øverste noden i selve treet.

Enhver node i et tre, lagret for den øverste noden, vil ha en overordnet node som ligger over den i hierarkiet til treet. Den kan også ha underordnede noder, som ligger under den. Du får tilgang til en gitt node gjennom de over den i treet og gir tilgang til dem under den.

Binære tredatastrukturer gjør at hver node ikke har mer enn to barn. En gitt knutepunkt 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 av en datamaskin på, og modifiserte versjoner av binære trær brukes for å forbedre effektiviteten. Et binært søketre er et der alle dataverdiene som ligger på venstre nedadgående 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ærtre må igjen være større enn verdien i basenoden. Denne databestillingen gjør det mulig å skrive en mye mer effektiv søkealgoritme.

Formen på et binært tre er også viktig for å bestemme effektiviteten til en søkealgoritme. Den minst effektive varianten 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 en der hver node som spares for dem som er i bunnen av treet, har to barn, og hvor alle bladnodene, bunnknutene i treet, er i samme avstand fra roten.