Binärt sökträd
Wikipedia
Ett binärt sökträd är ett binärt träd (dvs varje nod har högst två barn) med följande egenskaper:
- varje nod har ett värde.
- det högra delträdet till en nod innehåller bara värden som är högre än värdet i noden.
- det vänstra delträdet till en nod innehåller bara värden som är lägre än värdet i noden.
Binära sökträd är användbara eftesom det finns effektiva sökalgoritmer som kan användas på dem. I genomsnitt är algoritmen av ordning Θ(log n) och i värsta fall Θ(n).
[redigera] Traversering
Att genomsöka alla noderna i ett träd kallas att tranversera trädet. Detta kan göras genom post-, pre- eller inordertreversering.
Om inordertranversering appliceras på ett binärt sökträd fås elementen i växande ordning.
