Röd-svart träd

Från Wikipedia
Hoppa till: navigering, sök

Röd-svart träd, datastruktur i form av ett så gott som balanserat binärt sökträd. Strukturen använder en extra bit för att hålla sig balanserat. Inget löv i trädet ligger mer än dubbelt så långt från roten som något annat löv. Ett röd-svart träd med n interna noder har som mest höjden log2(n+1).

Trädet har också kallats symmetriskt binärt B-träd.

Se även[redigera | redigera wikitext]