Questions tagged [splay-trees]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
Proper Illumination's user avatar
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 ...
vesii's user avatar
  • 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 ...
vesii's user avatar
  • 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: ...
caramba's user avatar
  • 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 ...
vesii's user avatar
  • 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 ...
BrockenDuck's user avatar
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 ...
addu390's user avatar
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 ...
jugc's user avatar
  • 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 $...
jugc's user avatar
  • 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 ...
kalpaj agrawalla's user avatar
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....
D Wot's user avatar
  • 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 ...
Silver Flash's user avatar
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 ...
Tyilo's user avatar
  • 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. ...
Wanderer's user avatar
  • 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 ...
Frou-Frou Fox's user avatar
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 ...
Gleb's user avatar
  • 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 ...
hengxin's user avatar
  • 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: ...
Maaour's user avatar
  • 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 ...
roctothorpe's user avatar
  • 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: ...
BadCatss's user avatar
  • 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 ...
BadCatss's user avatar
  • 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 ...
Joshua Vanlo's user avatar
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 $...
Mojo Jojo's user avatar
  • 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 ...
James's user avatar
  • 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 ...
oneCoderToRuleThemAll's user avatar
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 ...
wcochran's user avatar
  • 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 ...
Petr's user avatar
  • 2,175