# Questions tagged [splay-trees]

The tag has no usage guidance.

27 questions
Filter by
Sorted by
Tagged with
24 views

### Splay Trees - Sequential Access Theorem & lower bound for comparison-based sorting

The following theorem was proven by R.E. Tarjan in 1984: Theorem (Sequential Access Theorem). If we access each of the nodes of an arbitrary initial tree once, in symmetric order, the total time ...
31 views

### What type of tree traversal should be performed to obtain the same splay tree?

I'm trying to figure the following: Given splay tree number 1. Perform a tree traversal on it and insert each node into splay tree number 2 in that order. What type of tree traversal should be ...
• 223
38 views

### How the depth of the vertices changes along the route in the splay tree after search

Studying for the exam in "Advanced Algorithms" course. I'm trying to solve the following question: This question discusses a search operation for a vertex ...
• 223
48 views

### Splay Tree remove step by step

I am having some difficulties understanding how the remove() operation works step by step with the splay tree. My tree looks like so: ...
• 103
1 vote
53 views

### Algorithm to recreate a Splay tree

Let's say I have some splay tree as following: I want to recrate the exact same Splay tree using insert(key) method. Is there an algorithm that given some Splay ...
• 223
42 views

### Efficient Implementation of join and split operations on semisplaying tree

Splaying trees are a heavily researched of theoretical computer science as they are conjectured to be optimal binary trees. They were first presented by Sleator & Tarjan in Self-Adjusting Binary ...
• 121
46 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
300 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
93 views

• 163
133 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 ...
372 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 ...
• 265