Left-leaning red–black tree
From Wikipedia, the free encyclopedia
| Left-leaning red–black tree | ||
|---|---|---|
| Type | Tree | |
| Invented | 2008 | |
| Invented by | Robert Sedgewick | |
| Time complexity in big O notation | ||
| Average | Worst case | |
| Space | O(n) | O(n) |
| Search | O(log n) | O(log n) |
| Insert | O(log n) | O(log n) |
| Delete | O(log n) | O(log n) |
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.
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, rkapsi | 2008 | Java | From this Sedgewick paper | Left-leaning Red–Black Tree (LLRB) | |
| David Anson | 2 Jun 2009 | C# | Maintaining balance: A versatile red-black tree implementation for .NET | ||
| kazu-yamamoto | 2011 | Haskell | llrbtree | ||
| Haskell | Data.Set.LLRBTree | ||||
| gradbot | 2010 | F# | f-sharp-llrbt | ||
| 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 at 25thandClement.com | 2011 | C | 2-3 variant using iteration with parent pointers | llrb.h: Left-leaning Red–Black Tree | |
| Vala | Gee.TreeMap | ||||
| Petar Maymounkov | 2010 | Go | GoLLRB |
Other
- Robert Segdewick. 20 Apr 2008. Animations of LLRB operations
- Open Data Structures - Section 9.2.2 - Left-Leaning Red–Black Trees
- Left-Leaning Red-Black Trees Considered Harmful
| ||||||||||||||||||||||||||
This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.