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.
All labels observed (1)
| Label | Occurrences |
|---|---|
| AVL tree canonical | 2 |
How this entity was disambiguated
This entity first appeared as the object of triple T13507258 — 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: AVL tree Context triple: [splay tree, relatedTo, AVL tree]
-
A.
AVL
AVL is the three-letter IATA airport code for Asheville Regional Airport serving the Asheville, North Carolina area.
-
B.
BST
BST is the time zone used throughout Bangladesh, set six hours ahead of Coordinated Universal Time (UTC+6).
-
C.
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.
-
D.
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.
-
E.
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.
- 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: AVL tree Target entity description: 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.
-
A.
AVL
AVL is the three-letter IATA airport code for Asheville Regional Airport serving the Asheville, North Carolina area.
-
B.
BST
BST is the time zone used throughout Bangladesh, set six hours ahead of Coordinated Universal Time (UTC+6).
-
C.
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.
-
D.
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.
-
E.
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.
- F. None of above. chosen
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
ⓘ
Georgy Adelson-Velsky ⓘ |
| 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 ⓘ |
| 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
ⓘ
level-order ⓘ post-order ⓘ pre-order ⓘ |
| 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 ⓘ |
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: AVL tree Description of subject: 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.
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.