red-black tree

E1045599

data structure search tree self-balancing binary search tree

A red-black tree is a type of self-balancing binary search tree that guarantees logarithmic time for insertion, deletion, and lookup by enforcing specific color and structural properties on its nodes.

Try in SPARQL Jump to: Surface forms Statements Referenced by

All labels observed (2)

Label	Occurrences
java.util.TreeMap	1
red-black tree canonical	1

Statements (51)

Predicate	Object
instanceOf	data structure ⓘ search tree ⓘ self-balancing binary search tree ⓘ
advantageOver	simple binary search tree in worst-case performance ⓘ
comparedWith	AVL tree NERFINISHED ⓘ B-tree NERFINISHED ⓘ splay tree NERFINISHED ⓘ
documentedIn	Algorithms (Sedgewick) NERFINISHED ⓘ Introduction to Algorithms NERFINISHED ⓘ
ensures	tree height is O(log n) ⓘ
hasProperty	balanced ⓘ binary ⓘ height-balanced in O(log n) ⓘ logarithmic-time operations in worst case ⓘ ordered ⓘ
introducedBy	Rudolf Bayer NERFINISHED ⓘ
isSubtypeOf	binary search tree ⓘ
maintainsInvariant	all leaves (NIL nodes) are black ⓘ every node is either red or black ⓘ every path from a node to descendant leaves has the same number of black nodes ⓘ red nodes have black parents ⓘ the root is black ⓘ
nodeDegree	at most 2 children per node ⓘ
originalName	symmetric binary B-tree NERFINISHED ⓘ
originatedIn	1972 ⓘ
popularizedBy	Leonidas J. Guibas NERFINISHED ⓘ Robert Sedgewick NERFINISHED ⓘ
rotationTypes	left rotation ⓘ right rotation ⓘ
supportsOperation	deletion ⓘ insertion ⓘ search ⓘ
supportsTraversal	in-order traversal GENERATED ⓘ post-order traversal GENERATED ⓘ pre-order traversal GENERATED ⓘ
timeComplexityDeletion	O(log n) ⓘ
timeComplexityInsertion	O(log n) ⓘ
timeComplexitySearch	O(log n) ⓘ
typicalHeightBound	no more than 2 * log2(n + 1) GENERATED ⓘ
typicalImplementationLanguage	C NERFINISHED ⓘ C++ NERFINISHED ⓘ Java NERFINISHED ⓘ Python (library or custom) ⓘ
usedIn	associative arrays ⓘ ordered maps ⓘ ordered sets ⓘ standard library containers ⓘ symbol tables ⓘ
uses	node colors ⓘ recoloring ⓘ rotations ⓘ

Referenced by (2)

Full triples — surface form annotated when it differs from this entity's canonical label.

splay tree → relatedTo → red-black tree ⓘ

java.util → containsClass → red-black tree ⓘ

this entity surface form: java.util.TreeMap