Splay tree

Uses your system voice; voice and rate in settings.

Snapshot

≈ 9 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

A splay tree is a binary search tree with the additional property that recently accessed elements are quick to access again. Like self-balancing binary search trees, a splay tree performs basic operations such as insertion, look-up and removal in O(log n) amortized time. For random access patterns drawn from a non-uniform random distribution, their amortized time can be faster than logarithmic, proportional to the entropy of the access pattern. For many patterns of non-random operations, also, splay trees can take better than logarithmic time, without requiring prior knowledge of the pattern. According to the unproven dynamic optimality conjecture, their performance on all access patterns is within a constant factor of the best possible performance that could be achieved by any other self-adjusting binary search tree, even one selected to fit that pattern. The splay tree was invented by Daniel Sleator and Robert Tarjan in 1985. All normal operations on a binary search tree are combined with one basic operation, called splaying. Splaying the tree for a certain element rearranges the tree so that the element is placed at the root of the tree. One way to do this with the basic search operation is to first perform a standard binary tree search for the element in question, and then use tree rotations in a specific fashion to bring the element to the top.…

A splay tree is a binary search tree with the additional property that recently accessed elements are quick to access again. Like self-balancing binary search trees, a splay tree performs basic operations such as insertion, look-up and removal in O(log n) amortized time. For random access patterns drawn from a non-uniform random distribution, their amortized time can be faster than logarithmic, proportional to the entropy of the access pattern. For many patterns of non-random operations, also, splay trees can take better than logarithmic time, without requiring prior knowledge of the pattern. According to the unproven dynamic optimality conjecture, their performance on all access patterns is within a constant factor of the best possible performance that could be achieved by any other self-adjusting binary search tree, even one selected to fit that pattern. The splay tree was invented by Daniel Sleator and Robert Tarjan in 1985. All normal operations on a binary search tree are combined with one basic operation, called splaying. Splaying the tree for a certain element rearranges the tree so that the element is placed at the root of the tree. One way to do this with the basic search operation is to first perform a standard binary tree search for the element in question, and then use tree rotations in a specific fashion to bring the element to the top. Alternatively, a top-down algorithm can combine the search and the tree reorganization into a single phase. include ifndef SPLAY_TREE define SPLAY_TREE template > class splay_tree { private: Comp comp; unsigned long p_size; struct node { node *left, *right; node *parent; T key; node(const T& init = T()) : left(nullptr), right(nullptr), parent(nullptr), key(init) { } ~node() { } } *root; void left_rotate(node *x) { node *y = x->right; if (y) { x->right = y->left; if (y->left) y->left->parent = x; y->parent = x->parent; } if (!x->parent) root = y; else if (x == x->parent->left) x->parent->left = y; else x->parent->right = y; if (y) y->left = x; x->parent = y; } void right_rotate(node *x) { node *y = x->left; if (y) { x->left = y->right; if (y->right) y->right->parent = x; y->parent = x->parent; } if (!x->parent) root = y; else if (x == x->parent->left) x->parent->left = y; else x->parent->right = y; if (y) y->right = x; x->parent = y; } void splay(node *x) { while (x->parent) { if (!x->parent->parent) { if (x->parent->left

x) right_rotate(x->parent); else left_rotate(x->parent); } else if (x->parent->left

x && x->parent->parent->left

x->parent) { right_rotate(x->parent->parent); right_rotate(x->parent); } else if (x->parent->right

x && x->parent->parent->right

x->parent) { left_rotate(x->parent->parent); left_rotate(x->parent); } else if (x->parent->left

x && x->parent->parent->right == x->parent) { right_rotate(x->parent); left_rotate(x->parent); } else { left_rotate(x->parent); right_rotate(x->parent); } } } void replace(node *u, node *v) { if (!u->parent) root = v; else if (u == u->parent->left) u->parent->left = v; else u->parent->right = v; if (v) v->parent = u->parent; } node* subtree_minimum(node *u) { while (u->left) u = u->left; return u; } node* subtree_maximum(node *u) { while (u->right) u = u->right; return u; } public: splay_tree() : root(nullptr), p_size(0) { } void insert(const T &key) { node *z = root; node *p = nullptr; while (z) { p = z; if (comp(z->key, key)) z = z->right; else z = z->left; } z = new node(key); z->parent = p; if (!p) root = z; else if (comp(p->key, z->key)) p->right = z; else p->left = z; splay(z); p_size++; } node* find(const T &key) { node *z = root; while (z) { if (comp(z->key, key)) z = z->right; else if (comp(key, z->key)) z = z->left; else return z; } return nullptr; } void erase(const T &key) { node *z = find(key); if (!z) return; splay(z); if (!z->left) replace(z, z->right); else if (!z->right) replace(z, z->left); else { node *y = subtree_minimum(z->right); if (y->parent != z) { replace(y, y->right); y->right = z->right; y->right->parent = y; } replace(z, y); y->left = z->left; y->left->parent = y; } delete z; p_size--; } /* //the alternative implementation void erase(const T &key) { node *z = find(key); if (!z) return; splay(z); node *s = z->left; node *t = z->right; delete z; node *sMax = NULL; if (s) { s->parent = NULL; sMax = subtree_maximum(s); splay(sMax); root = sMax; } if (t) { if (s) sMax->right = t; else root = t; t->parent = sMax; } p_size--; } / const T& minimum() { return subtree_minimum(root)->key; } const T& maximum() { return subtree_maximum(root)->key; } bool empty() const { return root == nullptr; } unsigned long size() const { return p_size; } }; endif // SPLAY_TREE size(r) = the number of nodes in the sub-tree rooted at node r (including r). rank(r) = log 2 (size(r)). Φ = the sum of the ranks of all the nodes in the tree. Φ will tend to be high for poorly balanced trees and low for well-balanced trees. To apply the potential method, we first calculate ΔΦ: the change in the potential caused by a splay operation. We check each case separately. Denote by rank' the rank function after the operation. x, p and g are the nodes affected by the rotation operation (see figures above).

Zig step

Zig-zig step

Zig-zag step

The amortized cost of any operation is ΔΦ plus the actual cost. The actual cost of any zig-zig or zig-zag operation is 2 since there are two rotations to make. Hence: When summed over the entire splay operation, this telescopes to 1 + 3(rank(root)−rank(x)) which is O(log n), since we use The Zig operation at most once and the amortized cost of zig is at most 1+3(rank'(x)−rank(x)). So now we know that the total amortized time for a sequence of m operations is: T_\mathrm{amortized}(m) = O(m \log n) To go from the amortized time to the actual time, we must add the decrease in potential from the initial state before any operation is done (Φ i ) to the final state after all operations are completed (Φ f ). \Phi_i - \Phi_f = \sum_x{\mathrm{rank}_i(x) - \mathrm{rank}_f(x)} = O(n \log n) where the big O notation can be justified by the fact that for every node x, the minimum rank is 0 and the maximum rank is log(n). Now we can finally bound the actual time: T_\mathrm{actual}(m) = O(m \log n + n \log n) Define size(r) = the sum of weights of nodes in the sub-tree rooted at node r (including r). Define rank(r) and Φ exactly as above. The same analysis applies and the amortized cost of a splaying operation is again: 1 + 3(\mathrm{rank}(root)-\mathrm{rank}(x)) where W is the sum of all weights. The decrease from the initial to the final potential is bounded by: \Phi_i - \Phi_f \leq \sum_{x\in tree}{\log{\frac{W}{w(x)}}} since the maximum size of any single node is W and the minimum is w(x). Hence the actual time is bounded by: O\left(\sum_{x \in sequence}{\left(1 + 3\log{\frac{W}{w(x)}}\right)} + \sum_{x \in tree}{\log{\frac{W}{w(x)}}}\right) = O\left(m + \sum_{x \in sequence}{\log{\frac{W}{w(x)}}} + \sum_{x \in tree}{\log{\frac{W}{w(x)}}}\right)

Text derived from https://en.wikipedia.org/w/index.php?oldid=1357662481 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.