Questions tagged [splay-trees]

The tag has no usage guidance.

8 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
0answers
26 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 ...
1
vote
0answers
22 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: ...
1
vote
0answers
84 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 ...
1
vote
0answers
22 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: ...
1
vote
0answers
37 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 $...
0
votes
0answers
30 views

Splay tree amortized cost analysis

I am looking into the amortized analysis of splay trees and seem to be missing something. Pretty much every resource uses the accounting method which I believe I grasp. What confuses me is the part ...
0
votes
0answers
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 ...
0
votes
0answers
305 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 ...