Left-leaning red–black tree
A left-leaning red–black (LLRB) 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.
| Left-leaning red–black tree | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | tree | |||||||||||||||
| Invented | 2008 | |||||||||||||||
| Invented by | Robert Sedgewick | |||||||||||||||
| Time complexity in big O notation | ||||||||||||||||
| ||||||||||||||||
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 log N in a tree of N keys, and the behavior observed in practice is typically that same multiple faster than the worst-case bound, close to the optimal log N nodes examined that would be observed in a perfectly balanced tree.
Specifically, in a left-leaning red-black 2–3 tree built from N random keys:
- A random successful search examines log2 N − 0.5 nodes.
- The average tree height is about 2 log2 N
- The average size of left subtree exhibits log-oscillating behavior.
External links
Papers
- Robert Sedgewick. Left-leaning Red–Black Trees. Direct link to PDF.
- Robert Sedgewick. Left-Leaning Red–Black Trees (slides). Two versions:
- Linus Ek, Ola Holmström and Stevan Andjelkovic. May 19, 2009. Formalizing Arne Andersson trees and Left-leaning Red–Black trees in Agda
- Julien Oster. March 22, 2011. An Agda implementation of deletion in Left-leaning Red–Black trees
- Kazu Yamamoto. 2011.10.19. Purely Functional Left-Leaning Red–Black Trees
Implementations
| Author | Date | Language | Variant | Notes | Link |
|---|---|---|---|---|---|
| Robert Sedgewick | 2008 | Java | From this Sedgewick paper | ||
| David Anson | 2 Jun 2009 | C# | Maintaining balance: A versatile red-black tree implementation for .NET | ||
| kazu-yamamoto | 2011 | Haskell | llrbtree (Data.Set.LLRBTree) | ||
| Lee Stanza | 2010 | C++ | Includes discussion | Balanced Trees, Part 4: Left Leaning Red–Black Trees | |
| Jason Evans | 2010 | C | 2-3 | rb.h | |
| Nicola Bortignon | December 8, 2010 | ActionScript 3 | AS3 implementation and discussion | ||
| William Ahern | 2011 | C | 2-3 variant using iteration with parent pointers | llrb.h: Left-leaning Red–Black Tree | |
| Maciej Piechotka | 2009 | Vala | Gee.TreeMap | ||
| Petar Maymounkov | 2010 | Go | 2-3 | GoLLRB | |
| Jim Fisher | 2012 | C | Verifying a balanced-tree index implementation in Verifast | ||
| Sebastien Chapuis | 2015 | C | C - Left-leaning rbtree implementation
| ||
| Seungyoung Kim | 2015 | C | 2-3-4 variant | C implementation | |
| Robin Heggelund Hansen | 2018 | Elm | Elm implementation | ||
| R Pratap Chakravarthy | 2019 | Rust | Rust implementation | ||
| Max Goren | 2022 | C++ | 2-3 | Full Recursive Implementation | C++ implementation |
| Valeriano Della Longa | 2021 | Swift | 2-3 | Conformance to BidirectionalCollection protocol with O(1) complexity for firstIndex, endIndex, first, last, min and max. | Swift implementation |
| Filza & Ahmed | 2021 | Python | https://www.youtube.com/channel/UCm68_MratG7meGtzTbkS_3g/featured |
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.