Hvad er et binært træ?

Et binært træ er en type datastruktur, der bruges i computerprogrammering til at gemme, sortere og få adgang til oplysninger. Binære træer er den enkleste sort træ, men er meget nyttige og lette at implementere. En typisk implementering af et binært træ er afhængig af en rodnode, der er knyttet til en række noder, der udgør selve træet ved hjælp af 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ædatasstrukturer 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 rodnode peger på den øverste knude i selve træet.

Enhver knude i et træ, gemt for den øverste knude, vil have en overordnet knude, der er placeret over det i træets hierarki. Det kan også have underordnede noder, der er placeret under det. Du får adgang til en given knudepunkt gennem dem over det i træet og giver adgang til dem derunder.

Binære trædatastrukturer tillader, at hver knude ikke har mere end to børn. En given knude kan således have nul, en eller to børnknudepunkter knyttet til den. Almindelige binære træer tillader knudepunkter med et hvilket som helst antal børn på ethvert tidspunkt i træet. De har heller ingen begrænsninger for, hvordan værdier, der er gemt i noder, der omfatter et træ, er arrangeret.

Datastrukturer er mest nyttige, når de forbedrer hastigheden, hvorpå data kan fås adgang til en computer, og modificerede versioner af binære træer bruges til at forbedre deres effektivitet. Et binært søgetræ er et, hvor alle dataværdier, der er placeret i venstre faldende gren fra en given knude, har værdier, der er lig med eller mindre end den værdi, der er gemt i denne knude. Værdier på højre side af en knude i et ordnet binært træ skal til gengæld være større end værdien i basisnoden. Denne dataordre muliggør skrivning af en meget mere effektiv søgealgoritme.

Formen på et binært træ er også vigtigt for at bestemme effektiviteten af ​​en søgealgoritme. Den mindst effektive sort af et binært træ er en, hvor hver knude kun har et enkelt barn. En computer skal muligvis undersøge hvert dataelement 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æ en, hvor hver knude, der er gemt for dem i bunden af ​​træet, har to børn, og hvor alle bladknudepunkter, bundknudene i træet, er i samme afstand fra roden.