4 ms·
Interestingly, a red-black tree can be viewed as a BTree [0]. Another case where caching plays a huge role in determining the most efficient data structure (Se
by cheepin 13y ago
Interestingly, a red-black tree can be viewed as a BTree [0].
Another case where caching plays a huge role in determining the most efficient data structure (See vector vs list [1]).
[0]: http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Analogy_to_B-trees_of_order_4 http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Analogy_...
[1]: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector...
- nonsens3 13y agoRobert Sedgewick gives a very good analogy of a red-black tree to a 2-3 tree on his Coursera course (Algorithms, Part I) [0] - a bit different to what is discussed in Wikipedia, but very easy to understand and implement. [0]: https://class.coursera.org/algs4partI-004 https://class.coursera.org/algs4partI-004