Stack Overflow
Stack Overflow

Questions tagged [splay-tree]

A splay tree is a self-adjusting binary search tree with excellent amortized performance.

70 questions
55
votes
2 answers

Difference between AVL trees and splay trees

I am studying about various trees, and came across AVL trees and splay trees. I want to know What is difference between AVL trees and splay trees? On what basis do we select these tress? What are positive's and negative's of these trees? What are…
venkysmarty
  • 11,099
  • 25
  • 101
  • 184
6
votes
2 answers

Is std::map allowed to re-balance after read-only operations (like a Splay tree)

Some binary tree data structures (such as Splay trees) will re-balance on reads to move recently accessed items toward the root, such that the subsequent look-up time may be reduced. Are the standard containers (std::map, std::set) allowed to do…
Darren Engwirda
  • 6,915
  • 4
  • 26
  • 42
6
votes
1 answer

amortized cost of splay tree : cost + P(tf) - P(ti) ≤ 3(rankf(x) - ranki(x)) explanation

While reading about splay trees I found some expression about the rank of the splay node 'X' and the amortized cost in wikipedia. It is given as, { We can bound the amortized cost of any zig-zig or zig-zag operation by: amortized cost = cost + P(tf)…
poddroid
  • 845
  • 1
  • 14
  • 26
6
votes
1 answer

Intuition behind splay tree (self balancing trees)

I am reading the basics of splay trees. The amortized cost of an operation is O(log n) over n operations. Some rough basic idea is that when you access a node, you splay it i.e. you take it to root so next time this is quickly accessed and also if…
xyz
  • 8,607
  • 16
  • 66
  • 90
6
votes
3 answers

How can I implement a splay tree that performs the zig operation last, not first?

For my Algorithms & Data Structures class, I've been tasked with implementing a splay tree in Haskell. My algorithm for the splay operation is as follows: If the node to be splayed is the root, the unaltered tree is returned. If the node to be…
Jakob
  • 2,588
  • 5
  • 27
  • 34
6
votes
1 answer

A sequence that forms the same AVL and splay trees?

Is there such a sequence of numbers (1-7, all numbers used, only once each), that would form equal AVL and splay tree?
Issak
  • 96
  • 1
  • 8
4
votes
1 answer

How to use a SplayTreeMap on Firebase snapshot dictionary in dart/Flutter?

I'm successfully getting data back through StreamBuilder and need to sort it. How can I sort a Map of my snapshot data by keys? Also, If you give an example of doing this my value that would help also. I think I want to do a SplayTreeMap, but if…
Charles Jr
  • 8,333
  • 15
  • 53
  • 74
4
votes
1 answer

ZigZag and ZigZig operation in splay tree?

consider my tree is like this 5 / \ 3 7 / \ / \ 2 4 6 8 in that, when we search a element 2 that time zigzig operation will be performed, so first we rotate the parent…
Bhuvanesh
  • 1,269
  • 1
  • 15
  • 25
4
votes
3 answers

Splay tree insertion

Going through some excercises to hone my binary tree skills, I decided to implement a splay tree, as outlined in Wikipedia: Splay tree. One thing I'm not getting is the part about insertion. It says: First, we search x in the splay tree. If x does…
Lasse V. Karlsen
  • 380,855
  • 102
  • 628
  • 825
3
votes
3 answers

Why are persistent splay trees particularly useful in functional programming?

On the Splay Trees Wikipedia page it is said (in the Advantages section): Possibility of creating a persistent data structure version of splay trees—which allows access to both the previous and new versions after an update. This can be useful in…
Iulius Curt
  • 4,984
  • 4
  • 31
  • 55
3
votes
1 answer

Time complexity of Map containsKey and containsValue in Dart

What is the time complexity of Map.containsKey and Map.containsValue in Dart? I'd like to know for the following implementations: LinkedHashMap HashMap SplayTreeMap I assume for the hash map implementations containsKey is amortized constant time…
Suragch
  • 484,302
  • 314
  • 1,365
  • 1,393
3
votes
1 answer

Implementing the Rope data structure using binary search trees (splay trees)

In a standard implementation of the Rope data structure using splay trees, the nodes would be ordered according to a rank statistic measuring the position of each one from the start of the string, so the keys normally found in binary search tree…
curlew77
  • 393
  • 5
  • 15
3
votes
0 answers

How to manipulate a string (move substring to other part of string) in O(log n) using a rope or an order statistics splay tree

Two weeks ago I've finished an implementation of a splay tree that allows basic functions, like insert, delete, find key and and obtain the sum of a range of elements of the three. You can find this implementation here as reference for this question…
Nooblhu
  • 552
  • 15
  • 33
3
votes
2 answers

Is there any faster implementation for this Splay Tree range sum?

I have coded a splay tree. The nodes are represented like this. struct Node{ Node *l; /// The left Node Node *r; /// The right Node int v; /// The Value }; Now, I need to know the summation of all the numbers in the tree within a…
jbsu32
  • 1,036
  • 1
  • 11
  • 31
3
votes
2 answers

What is the Difference between Bottom-up and Top down methods in splay tree?

I have read about Splay tree and I found,there are two methods for constructing the splay tree. They are Bottom-up Top-down So I need to know What is the difference between the two methods and their working ?
Bhuvanesh
  • 1,269
  • 1
  • 15
  • 25
1
2 3 4 5