Hvad er et binært træ?

Et binært træ er en type datastruktur, der bruges til computerprogrammering til at gemme, sortere og få adgang til oplysninger.Binære træer er den enkleste række træer, men er meget nyttige og lette at implementere.En typisk implementering af et binært træ er afhængig af en rodknude, der er knyttet til en række knudepunkter, der udgør selve træet efter markørvariabler.Denne type træ henter sit navn fra det faktum, at ingen knude i træet kan have mere end to børn.

Trædatakonstruktioner findes i mange sorter.De består af forskellige noder, der er organiseret i et hierarkisk mønster.En enkelt knude, roden, er det adgangspunkt, gennem hvilket hele datatræet kan søges eller på anden måde manipuleres.Denne rodknudepunkt peger på den øverste knude i selve træet.

Enhver knude i et træ, med undtagelse af den øverste knude, har en overordnet knude, der er placeret over den i træets hierarki.Det kan også have børneknuder, som er placeret under det.Der er adgang til en given knude gennem dem over den i træet og giver adgang til dem under det.

Binære træsatakonstruktioner tillader, at hver knude ikke har mere end to børn.En given knude kan således have nul, en eller to børneknudepunkter knyttet til den.Almindelige binære træer tillader knudepunkter med et vilkårligt antal børn på ethvert tidspunkt i træet.De lægger heller ikke nogen begrænsninger for, hvordan de værdier, der er gemt i knudepunkter, der omfatter et træ, er arrangeret.

Datakonstruktioner er mest nyttige, når de forbedrer hastigheden, hvorpå data kan fås til at få adgang til en computer, og modificerede versioner af binære træer bruges til atforbedre deres effektivitet.Et binært søgetræ er et, hvor alle dataværdier placeret på venstre faldende gren fra en given knude har værdier, der er lig med eller mindre end den værdi, der er gemt i den knude.Værdier på højre side af en knude i et bestilt binært træ skal igen være større end værdien i baseknuden.Denne data, der bestiller, giver mulighed for at skrives en meget mere effektiv søgealgoritme.

Formen på et binært træ er også vigtig til bestemmelse af effektiviteten af en søgealgoritme.Den mindst effektive variation af et binært træ er et, hvor hver knude kun har et enkelt barn.En computer kan være nødt til at undersøge alle dataartikler i hele træet for at finde et enkelt stykke information i denne konfiguration.I modsætning hertil er det mest effektive binære træ et, hvor hver knudepunkt, der er reddet for dem i bunden af træet, har to børn, og hvor alle bladknudepunkter, de nederste knudepunkter i træet, er den samme afstand fra roden.