Röd-svart träd
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). [1]
Trädet har också kallats symmetriskt binärt B-träd.
Se även
[redigera | redigera wikitext]Referenser
[redigera | redigera wikitext]- ↑ Sedgewick, Robert (1988). Algorithms. Reading: Addison-Wesley. ISBN 0201066734