5

The amortized cost of entering an element to splay tree is $O(\log n)$ so in the worst case $n$ operations would do $O(n\log n)$ steps. There is a conjecture about splay tree that says that it is as optimal as a binary search tree up to constant factor called Dynamic optimality conjecture. Tango trees are online, self adjacent trees that achive $O(\log \log ...


4

It really does not matter for the analysis. The key lemma for analyzing the splay-tree performance is the access lemma. It states that the amortized costs of a splay(x) operation is less than $1+3(r(t)-r(x))$, where $t$ is the root of the tree and $r(u):=\lfloor \log (\text{weight of $u$'s subtree}) \rfloor$. The weight of a subtree is the sum of the ...


3

I am not quite sure what you want to achieve with your data structure. Indeed, Splay-trees are a cool data structure. They are known to have the static optimality property. This means if you know the distribution of you search queries in advance and you built the optimal binary search tree for this distribution, then a splay-tree (without knowing the ...


2

It sounds like you're looking for a binary search tree with the working-set property; this is a good bit weaker than dynamic optimality. In fact, there are no known binary search trees with dynamic optimality, according to Iacono's "In pursuit of the dynamic optimality conjecture" from June 2013. But, if you're looking for the simpler working-set property, ...


1

There has been various real world applications that use splay tree. One of the most prominent example is the gcc compiler that applies splay tree. There are many other examples. In fact, ACM Kanellakis Theory and Practice Award 1999 was given to Daniel Sleator and Robert Tarjan for their seminal work on the splay tree data structure. It looks like you have ...


1

Here is a helper fact. (Simple cost of splaying) Let $c(v)$ be the time it takes to find an element $v$ in a splay tree. There exists a constant $c_0$ independent of the splay tree and $v$ such that $c(v)\le c_0d(v)$, where $d(v)$ is the depth of $v$. Here is the sketch of a proof. There are two tasks that contribute to $c(v)$. To locate $v$ by going ...


1

No, you cannot merge two splay trees whose ranges may overlap in $O(\log N)$, where $N$ is the total number of nodes. You may have to move at least $\Theta(N)$ nodes in general or average situations. It contains no information at all when we know "whose ranges may overlap". The ranges of any two splay trees may overlap. It contains no information at all ...


1

This is a good question whose answer can help us understand how splay tree tends to keep away from being imbalanced. No, it is impossible for any rooted tree with more than 5 vertices to become a linear tree after operation splay() one of the deepest vertices, i.e. its depth is one less than the number of vertices. Why? For the sake of contradiction, let ...


1

It's true that if you consider a long sequence of operation, it's possible to point at one operation and say "that one operation might take a really long time" (e.g., $O(n)$ time). That's in some sense the essence of amortized analysis. An amortized running time of $O(\log n)$ means that the average time per operation is $O(\log n)$, but it's still true ...


1

Just follow the algorithm. First you have to do a zag-zag-rotation, which gives you 0 \ 1 \ 4 / 3 / 2 Then you have to do another zag-zag-rotation and you obtain as the result of splay(4) the tree 4 / 1 / \ 0 3 / 2


Only top voted, non community-wiki answers of a minimum length are eligible