Data er almindeligt gemt i binært træ strukturer ved hjælp af specialiserede algoritmer. Mange fordele kommer fra lagring af data i en træstruktur . For eksempel er at søge en ordnet binære træ meget hurtigere end sortering en sekventiel datastruktur , såsom en matrix . Et træ datastruktur kan antage mange typer af mønstre i løbet af dataadgang og modifikation. Forståelsen af ​​disse mønstre kan hjælpe dig med at designe bedre algoritmer til at optimere et træ algoritme. Grundlæggende elementer i en Binary Tree

Et binært træ består af knuder , som lagrer data og pege på andre knuder i træet. Rodknuden er udgangspunktet for træet og indtager den øverste niveau . Det kan have op til to barn noder . Disse barn noder kan også have op til to barn noder . Antallet af børn knudepunkter i en given knude kaldes graden af ​​knuden . En knude uden børn og en vis grad af nul kaldes et blad . Længden i knudepunkter fra roden node til den længst bladnoden er højden af træet . Dybden af ​​en knude er afstanden fra roden node til det . Hver knude, der har den samme dybde siges at være på samme niveau .
Full Binary Tree

En fuld binært træ er et træ , hvor hver node har præcis to eller nul børn. Med andre ord , enten hver knude har to børn eller er et blad . Et eksempel på en fuld binært træ er den Binary beslutning Diagram eller BDD .
Perfect Binary Tree

En perfekt binært træ har de samme egenskaber fuld binært træ , men alle blade knuder er på samme niveau , hvilket betyder, at dybden af ​​alle bladene er den samme i en perfekt binært træ . Da det er også en fuld binært træ , alle knuder undtagen blade noder har en vis grad af 2. .
Balanced Binary Tree

En afbalanceret binært træ er et, hvor dybden af ​​hvert blad node er enten det samme eller afviger med en værdi på én . Tilføjelse og fjernelse af noder fra en balanceret binært træ kan ubalance det, så en række tilpasninger kaldet rotationer skal finde sted for at genskabe balancen i træet. Holde et træ balanceret sikrer, at det gennemsnitlige søgetid for enhver node er optimal. Betydelig overliggende er nødvendig for at opretholde balancen i et træ.
Degenererede Binary Tree

degenereret binært træ er en, hvor hver node undtagen bladnoden har præcis én barneknudepunkt . Det har de samme egenskaber ved en linket liste , hvilket øger søgetiden for enhver node med et betydeligt beløb. For eksempel overveje en sag, hvor knuden bliver søgt efter er bladet node. Hele træet skal gennemløbes for at finde denne node. Med en afbalanceret binært træ , kun finde en bladnoden kræver en række node gennemskæringer svarende til dybden af ​​bladnoden . Med store træer , kan forskellen i ydelse være betydelige.