All Questions
Tagged with binary-search-trees splay-trees
6 questions
0
votes
1
answer
54
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
1
answer
54
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
361
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
1
vote
0
answers
69
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
0
votes
1
answer
216
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,641
1
vote
0
answers
137
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