Binärträd

Från Rilpedia

Texten från svenska Wikipedia

Konceptuell bild av ett binärt träd‎

Ett binärträd är en datastruktur av trädtyp i vilken varje nod har högst två barn. En vanlig användning är i form av ett binärt sökträd.

Definitioner

• En riktad kant är länken mellan en nod och ett barn (pilarna i bilden)
• Rotnoden är noden utan några föräldrar (noden längt upp i bilden). Det kan bara finnas en rotnod.
• Förälder är noden ovanför som har en riktad kant ner till den aktuella noden.
• Ett barn är en en nod under den aktuella noden som vi har en riktad kant till.
• Ett löv är en nod utan några barn
• Djupet för en nod är antalet steg från rotnoden till noden. Rotnoden är på djup 0, dess barn är på djup 1 osv.
• Höjden för trädet är det största djupet i trädet. Ett träd med bara en rotnod har höjd 0.
• Syskon är noder med samma förälder
• Delträd eller Subträd är en del av trädet.

Se även

• B-träd