Binärt sökträd

Ett binärt sökträd är ett binärträ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.

Ett binärt sökträd av storlek 9 och höjd 3. Rotvärdet är 8 och löven är 1, 4, 7 och 13

Binära sökträd är användbara eftersom 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).

Operationer

Alla de olika operationer man kan göra på ett binärt sökträd använder sig av en jämförelseoperator, som definieras som en funktion som tar in två parametrar och bestämmer ordningen på dessa två. I nedanstående algoritmer så använder vi tecknen < och > för att beteckna mindre eller större än.

Sökning

Att söka i ett binärt sökträd kan göras effektivt då trädet byggts upp för att klara av just detta. Vi börjar med att undersöka rotnoden och har då tre alternativ: värdet är större än noden och vi hittar då värdet i det högra delträdet, värdet är mindre än noden och vi hittar då värdet i det vänstra delträdet eller så är värdet lika med noden och vi har då hittat vårt svar. Efter denna jämförelse går vi till nästa nod (antingen åt höger eller vänster) och gör samma jämförelse där. Vi upprepar detta tills vi hittat vårt värde.

Sökning i ett träd med n noder har komplexiteten O(n) i värsta fall (med ett obalanserat träd där alla högra eller vänstra delträd är tomma, ett degenererat träd med samma egenskaper som en länkad lista). Med ett balanserat träd är komplexiteten O(log n).

Ett exempel i programspråket Python:

 def search_binary_tree(node, key):
     if node is None:
         return None  # nyckeln återfanns inte
     if key < node.key:
         return search_binary_tree(node.left, key)
     elif key > node.key:
         return search_binary_tree(node.right, key)
     else:  # nyckeln har samma värde som nodens värde
         return node.value  # hittat nyckel!

Traversering

Att genomsöka alla noderna i ett träd kallas att traversera trädet. Detta kan göras genom post-, pre- eller inordertraversering.

Om inordertraversering appliceras på ett binärt sökträd fås elementen i växande ordning.

Insättning

Tack vare det binära trädets uppbyggnad är det lätt att göra en insättning. Insättning görs vid den första lediga lövnoden. Efter insättning görs vanligtvis en sortering av trädet så att eventuella rotationer för att balansera trädet kan utföras.

Att sätta in ett objekt i ett binärt träd går till som följer. Om trädet inte redan har en rot så sätts objektet in som rot. Om trädet har en rot så jämförs objektet med roten. Om objektet är mindre än roten så ska objektet ligga i rotens vänstra gren. Om den vänstra grenen är tom så sätts objektet in där. Annars jämförs med det vänstra barnet på samma sätt.

Om objektet är större än roten så görs motsvarande i rotens högra gren.

Så här ser det ut om man lägger in strängarna "må", "ti", "on", "to", "fr", "lö" och "sö" i ett tomt binärt sökträd. Mindre och större än, < och >, är här definierade som före och efter i alfabetisk ordning.

• Insättning av "må". Eftersom trädet är tomt så sätts "må" in som rot.
• Insättning av "ti". Eftersom "ti" är större än "må" så ska det ligga till höger om "må". Eftersom "må" inte har något högra barn så läggs "ti" in som högra barn.
• Insättning av "on". "on" är större än "må" men mindre än "ti". Alltså läggs det som vänstra barn till "ti".
• "to" är större än "må" och "ti".
• "fr" är mindre än "må" så ska det ligga till vänster om "må". Eftersom "må" inte har något vänstra barn så läggs "fr" in som "må":s vänstra barn.
• "lö" och "sö" läggs in på samma sätt.