# Questions tagged [splay-trees]

The tag has no usage guidance.

19 questions
Filter by
Sorted by
Tagged with
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 ...
1k views

### Is there a binary tree structure with fast access to recently accessed elements and worst $O \left( \log n \right )$ complexity?

The idea of splay trees is very nice as they move frequently accessed elements to the top, which can gain a considerable speed up in many applications. The drawback is that in the worst case an ...
72 views

### Make appends not degrade a splay tree

Splay trees offer armotized O(log n) access to tree elements. However, if you keep repeatedly appending elements to a splay tree, without splaying any other elements, it degrades into a linked list ...
28 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 ...
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 ...
93 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 ...
69 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. ...
43 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 ...
13 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....
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: ...
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: ...
45 views