Questions tagged [splay-trees]

The tag has no usage guidance.

21 questions
Filter by
Sorted by
Tagged with
35 views

n search operations on an arbitrary Splay tree

For an arbitrary spay tree with n nodes, if we perform n find operations, is there a way of generalizing what the tree would ...
1 vote
137 views

Splay Tree: Repeatedly searching for the same key that's not in the Tree

In a splay tree, doing $m$ sequential search operations for the same key that is in the tree has a time complexity in $O(n+m)$ where n is the number of nodes in the tree. Since the first search has a ...
• 13
64 views

• 163
126 views

Rotations in splay trees

I am having some difficulties splaying the element 4 to the root. Considering the following splay tree. 0 \ 1 \ 2 \ 3 \ 4 ...
352 views

Proof by induction for a splay tree?

I'm preparing for an exam about Trees. One of the questions that appear in Mark Allen Weiss' "Data Structures and Algorithms Analysis in C++" is: Prove by induction that if all nodes in a splay ...
1k views

Splay tree with odd number of rotations

When inserting an item into a splay tree, rotations are performed in pairs based on either a zig-zag or zig-zig pattern. When there is an odd number of rotations to be performed, one could either do ...
• 266