AVL tree
E1045598
An AVL tree is a self-balancing binary search tree data structure that maintains strict height balance to ensure efficient insertion, deletion, and lookup operations.
Statements (51)
| Predicate | Object |
|---|---|
| instanceOf |
data structure
ⓘ
self-balancing binary search tree ⓘ |
| balanceFactorDefinition | height(left subtree) - height(right subtree) ⓘ |
| balanceFactorRange | -1 to 1 ⓘ |
| definedInPublication | An algorithm for the organization of information ⓘ |
| deleteTimeComplexityAverage | O(log n) ⓘ |
| deleteTimeComplexityWorst | O(log n) ⓘ |
| ensures | logarithmic height ⓘ |
| hasOperation |
delete
ⓘ
insert ⓘ search ⓘ traversal ⓘ |
| hasProperty |
dynamic
ⓘ
height-balanced ⓘ ordered ⓘ |
| hasRotationType |
left-right rotation
ⓘ
right-left rotation ⓘ single left rotation ⓘ single right rotation ⓘ |
| heightUpperBound | 1.44 log2(n+2) - 0.328 ⓘ |
| insertTimeComplexityAverage | O(log n) ⓘ |
| insertTimeComplexityWorst | O(log n) ⓘ |
| introducedBy |
Evgenii Landis
NERFINISHED
ⓘ
Georgy Adelson-Velsky NERFINISHED ⓘ |
| introducedInYear | 1962 ⓘ |
| isMoreStrictlyBalancedThan | red-black tree ⓘ |
| isSubtypeOf |
binary search tree
ⓘ
search tree ⓘ |
| maintainsInvariant |
balance factor constraint
ⓘ
binary search tree order property ⓘ |
| namedAfter | Adelson-Velsky and Landis NERFINISHED ⓘ |
| nodeStores |
height or balance factor
ⓘ
key ⓘ value ⓘ |
| rebalancingOperation | rotation ⓘ |
| requiresRebalancingWhen | balance factor is less than -1 or greater than 1 ⓘ |
| searchTimeComplexityAverage | O(log n) ⓘ |
| searchTimeComplexityWorst | O(log n) ⓘ |
| spaceComplexity | O(n) ⓘ |
| supportsTraversalOrder |
in-order
GENERATED
ⓘ
level-order GENERATED ⓘ post-order GENERATED ⓘ pre-order GENERATED ⓘ |
| typicallyHas |
faster lookups than red-black tree
ⓘ
slower insertions than red-black tree ⓘ |
| usedFor |
dictionary implementation
ⓘ
efficient deletion ⓘ efficient insertion ⓘ efficient search ⓘ in-memory indexing ⓘ set implementation ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.