(binary tree) – en trädformad datastruktur där varje nod har högst två barn. (”Barn” är grenar, kanter, som går till direkt underordnade noder.) – En datamängd är fördelad bland noderna. Som alla trädformade datastrukturer är trädet upp‑och‑nervänt med roten överst. Det kan bara finnas en rot. En nod kan ha noll, en eller två barn. En nod med noll barn kallas för löv. – Binärträd används ofta för lagring av information och för att möjliggöra sökningar. De värden som står i varje nod är då ofta hänvisningar. – Att balansera ett binärträd är att fördela noderna så att djupet från rot till löv blir så likartat som möjligt i alla förgreningar. Binärträdets höjd (det största djupet som finns i trädet) ska alltså ligga så nära det genomsnittliga djupet som möjligt. Den genomsnittliga söktiden, om man söker efter värden som kan finnas var som helst i binärträdet, blir kortast om trädet är balanserat. – Att sortera ett binärträd är att se till att värdena på noderna är ordnade enligt ett system – alfabetisk, nummerordning eller annat. Det innebär att nya värden måste läggas in på en bestämd plats i trädet, inte bara där det är enklast att lägga det. I ett sorterat träd kan man lätt ta kortaste vägen till ett visst värde. – Att se till att ett binärträd är både balanserat och sorterat kan vara omöjligt.
[datastrukturer] [9 mars 2017]