Questions tagged [splay-trees]
The splay-trees tag has no usage guidance.
21
questions
1
vote
1answer
46 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 ...
0
votes
0answers
42 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 $...
0
votes
0answers
19 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
42 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
26 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
91 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 ...
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
99 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
127 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
122 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
82 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
243 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
61 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 ...
