Röd-svart träd

Röd-svart träd

Datastruktur

Datastruktur, height-balanced binary search tree

Namngiven av	Leonidas J. Guibas, Robert Sedgewick
Upp­täc­ka­re eller upp­fin­na­re	Rudolf Bayer
Upp­täckts­da­tum	1972
Rums­komp­lex­i­tet i värsta fall	$O(n)$
Rums­komp­lex­i­tet i medel	$O(n)$

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 log₂(n+1).

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

Se även

• AVL träd
• B-träd