Statements (49)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
gptkb:architecture
self-balancing binary search tree |
| gptkbp:category |
gptkb:tree
search tree binary search tree balanced tree |
| gptkbp:hasApplication |
database indexing
priority queues memory management associative array implementation |
| gptkbp:hasAverageCaseTimeComplexity |
O(log n)
|
| gptkbp:hasBestCaseTimeComplexity |
O(log n)
|
| gptkbp:hasHeightBound |
2*log(n+1)
|
| gptkbp:hasInvariant |
no two red nodes in a row
same black height for all paths |
| gptkbp:hasLeaf |
NIL node
|
| gptkbp:hasNodeColor |
black
red |
| gptkbp:hasProperty |
logarithmic time complexity for delete
logarithmic time complexity for insert logarithmic time complexity for search |
| gptkbp:hasRule |
all leaves are black
root is always black red nodes cannot have red children every path from root to leaf has same number of black nodes |
| gptkbp:hasWorstCaseTimeComplexity |
O(log n)
|
| https://www.w3.org/2000/01/rdf-schema#label |
Red–black tree
|
| gptkbp:inventedBy |
gptkb:Rudolf_Bayer
1972 |
| gptkbp:isBalanced |
yes
|
| gptkbp:operator |
search
deletion insertion rotation recoloring |
| gptkbp:relatedTo |
gptkb:2–3_tree
AVL tree B-tree |
| gptkbp:usedFor |
searching
deletion insertion maintaining sorted data |
| gptkbp:usedIn |
gptkb:Java_TreeMap
gptkb:Java_TreeSet gptkb:STL_map gptkb:STL_set computer science |
| gptkbp:bfsParent |
gptkb:Leonidas_Guibas
|
| gptkbp:bfsLayer |
7
|