red-black tree
E1045599
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.
All labels observed (2)
| Label | Occurrences |
|---|---|
| java.util.TreeMap | 1 |
| red-black tree canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T13507259 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: red-black tree Context triple: [splay tree, relatedTo, red-black tree]
-
A.
Redblacks
Redblacks is a professional Canadian Football League team based in Ottawa, Ontario.
-
B.
splay tree
A splay tree is a self-adjusting binary search tree data structure that moves frequently accessed elements closer to the root to optimize average access time.
-
C.
B-tree
A B-tree is a self-balancing tree data structure that maintains sorted data and allows efficient insertion, deletion, and search operations, commonly used to implement database indexes.
-
D.
BST
BST is the time zone used throughout Bangladesh, set six hours ahead of Coordinated Universal Time (UTC+6).
-
E.
BST
BST (British Summer Time) is the daylight saving time observed in the United Kingdom, set one hour ahead of Coordinated Universal Time (UTC+1) during the summer months.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: red-black tree Target entity description: 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.
-
A.
Redblacks
Redblacks is a professional Canadian Football League team based in Ottawa, Ontario.
-
B.
splay tree
A splay tree is a self-adjusting binary search tree data structure that moves frequently accessed elements closer to the root to optimize average access time.
-
C.
B-tree
A B-tree is a self-balancing tree data structure that maintains sorted data and allows efficient insertion, deletion, and search operations, commonly used to implement database indexes.
-
D.
BST
BST is the time zone used throughout Bangladesh, set six hours ahead of Coordinated Universal Time (UTC+6).
-
E.
BST
BST (British Summer Time) is the daylight saving time observed in the United Kingdom, set one hour ahead of Coordinated Universal Time (UTC+1) during the summer months.
- F. None of above. chosen
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
ⓘ
B-tree ⓘ splay tree ⓘ |
| documentedIn |
Algorithms (Sedgewick)
ⓘ
Introduction to Algorithms ⓘ |
| 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 ⓘ |
| originatedIn | 1972 ⓘ |
| popularizedBy |
Leonidas J. Guibas
ⓘ
Robert Sedgewick ⓘ |
| rotationTypes |
left rotation
ⓘ
right rotation ⓘ |
| supportsOperation |
deletion
ⓘ
insertion ⓘ search ⓘ |
| supportsTraversal |
in-order traversal
ⓘ
post-order traversal ⓘ pre-order traversal ⓘ |
| timeComplexityDeletion | O(log n) ⓘ |
| timeComplexityInsertion | O(log n) ⓘ |
| timeComplexitySearch | O(log n) ⓘ |
| typicalHeightBound | no more than 2 * log2(n + 1) ⓘ |
| typicalImplementationLanguage |
C
ⓘ
C++ ⓘ Java ⓘ Python (library or custom) ⓘ |
| usedIn |
associative arrays
ⓘ
ordered maps ⓘ ordered sets ⓘ standard library containers ⓘ symbol tables ⓘ |
| uses |
node colors
ⓘ
recoloring ⓘ rotations ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: red-black tree Description of subject: 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.
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.
linked to: red-black tree