Röd-svart träd
Röd-svart träd
Datastruktur ![Redigera Wikidata](//upload.wikimedia.org/wikipedia/commons/thumb/6/63/Arbcom_ru_editing.svg/8px-Arbcom_ru_editing.svg.png)
![Redigera Wikidata](http://upload.wikimedia.org/wikipedia/commons/thumb/6/63/Arbcom_ru_editing.svg/8px-Arbcom_ru_editing.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/41/Red-black_tree_example_with_NIL.svg/260px-Red-black_tree_example_with_NIL.svg.png)
Underklass till | height-balanced binary search tree ![]() | |
---|---|---|
Namngiven av | Leonidas J. Guibas, Robert Sedgewick ![]() | |
Upptäckare eller uppfinnare | Rudolf Bayer ![]() | |
Upptäcktsdatum | 1972 ![]() | |
Rumskomplexitet i värsta fall | ![]() | |
Rumskomplexitet i medel | ![]() |
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
Referenser
- ^ Sedgewick, Robert (1988). Algorithms. Reading: Addison-Wesley. ISBN 0201066734