Röd-svart träd

Röd-svart träd

Datastruktur

Datastruktur

Under­klass till	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	${\displaystyle O(n)}$
Rums­komp­lex­i­tet i medel	${\displaystyle 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). [1]

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

Se även

• AVL träd
• B-träd

Referenser

1. Sedgewick, Robert (1988). Algorithms. Reading: Addison-Wesley. ISBN 0201066734