# Questions tagged [splay-trees]

The tag has no usage guidance.

18 questions
Filter by
Sorted by
Tagged with
9 views

### Splay tree amortized analysis cost using Access Lemma

Currently studying for an algorithms exam and I came across this question and solution, but I can't understand the solution where it references nodes of depth less than $4\log n$ and not restructuring....
27 views

### Doubt on Performance Comparison of Splay Trees

I'm trying to understand splay tree performance compared to a standard balanced tree like AVL/red-black. In practice, I am pretty skeptical of the amortized bounds Tarjan and Sleator proves in their ...
17 views

### How to reconstruct an existing splay tree by insertion?

I'm trying to figure out the same problem as stated in this question. In brief, I want to reconstruct an existing splay tree (printed on paper) on Splay Tree Visualization by inserting the values in ...
27 views

### Can every node of a link/cut tree be accessed in $O(n)$ time?

Per the Sequential Access Theorem we can access every node of a splay tree in $O(n)$ time, when accessing the nodes in a specific order. Given a link/cut tree, is it possible to access all of its ...
61 views

### Prove that a sequence of increasing find operations on a splay tree takes $\mathcal{O}(n)$ time

When studying about splay trees, I found the following statement: Suppose we have a splay tree and a sequence of Find operations, where the elements we are searching for are in increasing order. ...
88 views

### Merging two splay trees whose ranges may overlap in $O(\log N)$

I have two splay trees, $A$ and $B$. When every element in $A$ is smaller than every element in $B$, we can merge them in $O(\log N)$. My question is; when all elements of $A$ are not necessarily ...
42 views

### Example of tree with > 6 vertices, tree would have depth = n after splay() deepest vertex

How to build tree with more than 6 vertices, that after operation splay() would have depth = number of vertices? Is it possible? UPD: Example for n = 4: insert 60 insert 10 insert 20 insert 50 ...
74 views

### The validity of the potential function for splay tree

The paper "Self-Adjusting Binary Search Trees" defines (Page 658) the potential function for analyzing the amortized cost of a sequence of $m$ splay operations as the sum of the ranks of all nodes in ...
69 views

### Splay Tree - Insert Permutation

Let $T$ be a Splay Tree. For a given permutation $\sigma$ on a set $S = \{1,2,3,...n \}$ we defined the following function: ...
91 views

### Splay trees: why are depths of nodes on the access path halved?

The original paper describing splay trees Self-Adjusting Binary Search Trees by Sleator and Tarjan claims that: Splaying not only moves x to the root, but roughly halves the depth of every node ...
24 views

### Accounting value of Splay trees?

In Splay trees, by definition - the required element x - rises to the root of the tree, using the operations: zig, zig-zig, zig-zag. And the formula zig of the step is this: ...
27 views

### Proof of Zig-Zig step

There was a question connected with one of the video lecture lessons that I'm currently watching. Let two trees be given - the original and the tree after the zig-zig step: Calculate the cost of ...