Questions tagged [splay-trees]
The splay-trees tag has no usage guidance.
20
questions
0
votes
0answers
15 views
Time analysis of $m$ search operation in a Splay tree of nodes who have subtrees of size at least $\frac{n}{\log n}$
I know that the Worst-case for $m$ search operations in a Splay-tree is $O(m\log n +n \log n)$
The thing I'm not sure of is how this runtime depends on the size of the subtrees of the searched nodes.
...
0
votes
0answers
41 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 ...
1
vote
0answers
25 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....
2
votes
1answer
78 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 ...
0
votes
0answers
33 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 ...
2
votes
0answers
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 ...
1
vote
1answer
96 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. ...
0
votes
1answer
123 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 ...
1
vote
1answer
57 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
...
0
votes
1answer
111 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 ...
1
vote
0answers
81 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:
...
2
votes
1answer
236 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
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: ...
0
votes
0answers
28 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 ...
4
votes
1answer
75 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 ...
1
vote
0answers
59 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
1answer
120 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
...
0
votes
0answers
331 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
1answer
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 ...
7
votes
4answers
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 ...
