splay tree
E321044
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.
All labels observed (5)
| Label | Occurrences |
|---|---|
| splay tree canonical | 3 |
| binary search tree | 1 |
| link/cut tree | 1 |
| splay tree data structure | 1 |
| splay trees | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T3043248 — 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: splay tree Context triple: [Robert Tarjan, notableWork, splay tree]
-
A.
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.
-
B.
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.
-
C.
LCT
LCT is the ICAO airline designator assigned to TAR Aerolíneas, a regional carrier based in Mexico.
-
D.
DSA
DSA (Digital Signature Algorithm) is a widely used public-key cryptographic standard designed for creating and verifying digital signatures to ensure data integrity and authentication.
-
E.
Tree That Owns Itself
The Tree That Owns Itself is a famous white oak in Athens, Georgia, reputedly granted legal ownership of itself and the land immediately surrounding it.
- 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: splay tree Target entity description: 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.
-
A.
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.
-
B.
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.
-
C.
LCT
LCT is the ICAO airline designator assigned to TAR Aerolíneas, a regional carrier based in Mexico.
-
D.
DSA
DSA (Digital Signature Algorithm) is a widely used public-key cryptographic standard designed for creating and verifying digital signatures to ensure data integrity and authentication.
-
E.
Tree That Owns Itself
The Tree That Owns Itself is a famous white oak in Athens, Georgia, reputedly granted legal ownership of itself and the land immediately surrounding it.
- F. None of above. chosen
Statements (50)
| Predicate | Object |
|---|---|
| instanceOf |
binary search tree variant
ⓘ
data structure ⓘ self-adjusting binary search tree ⓘ |
| advantage |
adapts to access patterns
ⓘ
good amortized performance without storing balance factors ⓘ recently accessed elements become quick to access again ⓘ |
| balancingMethod | tree rotations during splaying ⓘ |
| canBe |
implemented iteratively
ⓘ
implemented recursively ⓘ |
| deleteOperationEffect | node to delete is splayed to the root ⓘ |
| disadvantage |
can be inefficient for strictly real-time worst-case requirements
ⓘ
no guaranteed worst-case O(log n) per operation ⓘ |
| goal |
move frequently accessed elements closer to the root
ⓘ
optimize average access time ⓘ |
| hasAuthor |
Daniel Sleator
ⓘ
Robert Tarjan ⓘ |
| insertOperationEffect | inserted node is splayed to the root ⓘ |
| invariant | inorder traversal yields keys in sorted order ⓘ |
| memoryOverhead | O(1) extra information per node ⓘ |
| nodeStores |
key
ⓘ
left child pointer ⓘ right child pointer ⓘ value ⓘ |
| primaryOperation |
rotation
ⓘ
splaying ⓘ |
| property |
binary search tree order
ⓘ
does not store explicit balance information ⓘ self-adjusting ⓘ |
| publicationYear | 1985 ⓘ |
| relatedTo |
AVL tree
ⓘ
red-black tree ⓘ skip list ⓘ treap ⓘ |
| rotationPattern |
zig
ⓘ
zig-zag ⓘ zig-zig ⓘ |
| searchOperationEffect | accessed node is splayed to the root ⓘ |
| supportsOperation |
delete
ⓘ
find-max ⓘ find-min ⓘ insert ⓘ join ⓘ search ⓘ split ⓘ |
| timeComplexityAmortized | O(log n) ⓘ |
| timeComplexityWorstCase | O(n) ⓘ |
| usedIn |
data compression algorithms
ⓘ
garbage collection algorithms ⓘ implementing associative arrays ⓘ implementing caches ⓘ |
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: splay tree Description of subject: 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.
Referenced by (7)
Full triples — surface form annotated when it differs from this entity's canonical label.
linked to: splay tree
linked to: splay tree
linked to: splay tree
linked to: splay tree