Questions tagged [splay-trees]
The splay-trees tag has no usage guidance.
21
questions
0
votes
1
answer
35
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
137
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
64
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
51
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
41
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
191
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
28
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 ...
- 126
1
vote
1
answer
133
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
183
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
77
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
180
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,179
1
vote
0
answers
88
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
367
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,128
1
vote
0
answers
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: ...
- 111
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 ...
- 111
4
votes
1
answer
80
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
80
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
126
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
352
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 ...
- 266
7
votes
4
answers
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 ...
- 2,087