# Questions tagged [splay-trees]

The tag has no usage guidance.

10 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
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 ...
12 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: ...
43 views

### Why is maximum size of root is 2n + 1 in Splay trees?

In the amortized analysis of Splaying in Dynamic trees, let us consider a splay tree $T$ with $n$ keys and $v$ be a node of $T$. We define $size(v)$ as the number of nodes in the subtree rooted at \$...
23 views

### (Searching + Splaying) in a Splay Tree

Given a tree To search for value 1, I do the following splay operations: i) Zag on 7 ii) Zag on 1 And hence obtain 1 in the root. But why would this be incorrect? i) Zag on 1 ii) Zag on 1 The ...
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 ...