Questions tagged [splay-trees]
The splay-trees tag has no usage guidance.
27
questions
0
votes
1
answer
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 ...
0
votes
0
answers
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
0
votes
0
answers
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
0
votes
2
answers
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
0
answers
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
2
votes
0
answers
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
0
votes
1
answer
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 ...
- 3
1
vote
1
answer
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
0
votes
0
answers
93
views
General Proof on Potential Method and Amortized Analysis
Let $T$ be an arbitrary data structure for a dynamic set. For every state T of $T$, let $d_t \in \mathbb{N}$. Observe two Operations $O_1, O_2$ on $T$ whose runtimes are proportional to $d_t$ and $...
- 13
0
votes
0
answers
68
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 ...
- 101
1
vote
0
answers
53
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....
- 11
4
votes
1
answer
310
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 ...
- 205
2
votes
0
answers
32
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 ...
- 127
1
vote
1
answer
167
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. ...
- 279
0
votes
1
answer
253
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 ...
- 105
1
vote
1
answer
115
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
...
- 57
0
votes
1
answer
207
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 ...
- 9,471
1
vote
0
answers
127
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:
...
- 111
2
votes
1
answer
498
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,138
1
vote
0
answers
26
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: ...
- 113
0
votes
0
answers
32
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 ...
- 113
4
votes
1
answer
84
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 ...
- 41
1
vote
0
answers
92
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 $...
- 163
0
votes
1
answer
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
...
- 9
0
votes
0
answers
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 ...
9
votes
1
answer
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
7
votes
4
answers
2k
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 ...
- 2,175