binärträd

(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 data­struk­turer är trädet upp-och-ner­vä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ök­ningar. 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 genom­snitt­liga djupet som möj­ligt. Den genom­snitt­liga söktiden, om man söker efter värden som kan finnas var som helst i binär­trä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, num­mer­ord­ning 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]