Left-leaning red–black tree
A left-leaning red–black tree is a type of self-balancing binary search tree. It is a variant of the red–black tree and guarantees the same asymptotic complexity for operations, but is designed to be easier to implement.
Properties of a left-leaning red–black tree
All of the red-black tree algorithms that have been proposed are characterized by a worst-case search time bounded by a small constant multiple of in a tree of keys, and the behavior observed in practice is typically that same multiple faster than the worst-case bound, close to the optimal nodes examined that would be observed in a perfectly balanced tree.Specifically, in a left-leaning red-black 2-3 tree built from random keys:
- A random successful search examines nodes.
- The average tree height is about
- The average size of left subtree exhibits log-oscillating behavior.
Papers
- . .
- Robert Sedgewick. Left-Leaning Red–Black Trees. Two versions:
- *
- *
-
Implementations
| Author | Date | Language | Variant | Notes | Link |
| Robert Sedgewick | 2008 | Java | From | ||
| David Anson | 2 Jun 2009 | C# | |||
| kazu-yamamoto | 2011 | Haskell | |||
| Lee Stanza | 2010 | C++ | Includes discussion | ||
| Jason Evans | 2010 | C | 2-3 | ||
| Nicola Bortignon | December 8, 2010 | ActionScript 3 | |||
| william at 25thandClement.com | 2011 | C | 2-3 variant using iteration with parent pointers | ||
| Maciej Piechotka | 2009 | Vala | |||
| Petar Maymounkov | 2010 | Go | 2-3 | ||
| Sebastien Chapuis | 2015 | C | |||
| Seungyoung Kim | 2015 | C | 2-3-4 variant | ||
| Robin Heggelund Hansen | 2018 | Elm | |||
| R Pratap Chakravarthy | 2019 | Rust |