; In each node, there is a boolean value x.leaf which is true if x is a leaf. = All normal operations on a binary search tree are combined with one basic operation, called splaying. [ + | x {\displaystyle W=m} The actual cost of any zig-zig or zig-zag operation is 2 since there are two rotations to make. This last quantity is at least ak provided (1/a) + 1/a2) is at least 1. by find operations). , x , ] x y x . m The insert operation is similar to Binary Search Tree insert with additional steps to make sure that the newly inserted key becomes the new root. Static Finger Theorem — Assume that the items are numbered from 1 through n in ascending order. Such systems include typical disk drives, where the disk drive has to spend so long finding data on disk that it tries to amortize the huge (tens of millions of CPU clock cycles) seek cost over many returned bytes. If this is done correctly, the amortized cost (see AmortizedAnalysis) of each tree operation is O(log n), although particular rare operations might take as much as O(n) time. The splay tree was invented by Daniel Sleator and Robert Tarjan in 1985.[1]. 1 2 x The node to be deleted is first splayed, i.e. Insertion algorithm 3. When a leaf splits, it becomes two one-key nodes and the middle key moves up into its parent. Splaying the tree for a certain element rearranges the tree so that the element is placed at the root of the tree. • Tree reorganizes itself after each operation. + For example, splay tree operations take amortized O(log n) cost, but if your only operation is to access the same item n times in a row, the actual average running time is in O(1). u w / If the uncle is red, we can recolor the node's parent, uncle, and grandparent and get rid of the double-red edge between the new node and its parent without changing the number of black nodes on any path. How do we maintain this invariant? Use the split operation to split the tree at the value of. s c O be the number of times element x is accessed in S. If every element is accessed at least once, then the cost of performing S is log {\displaystyle t(x)} ) 1 The two sub-trees are then joined using a "join" operation. x However the amortized access cost of this worst case is logarithmic, O(log n). = 2 y ) / We check each case separately. [1][12], Another way to reduce restructuring is to do full splaying, but only in some of the access operations - only when the access path is longer than a threshold, or only in the first m access operations.[1]. From the invariant it follows that every path has between k and 2k nodes, where k is the "black-height," the common number of black nodes on each path. , ⁡ We thus have the recurrence. − q s (In the following diagrams, circles indicate nodes of interest and triangles indicate sub-trees of arbitrary size.) AVL trees solve this problem by maintaining the invariant that the heights of the two subtrees sitting under each node differ by at most one. Historically, it has proven hard to analyze splay trees for several reasons: Each lookup can significantly reshape the tree. Let From this we can prove that the height of the tree is O(log n). The code is not that big as it seems in the first look. log [1], Static Optimality Theorem — Let + Define: Φ will tend to be high for poorly balanced trees and low for well-balanced trees. This may cause further splits up the ancestor chain; the tree grows in height by adding a new root when the old root splits. So rotations can be used to transfer depth from the leftmost grandchild of a node to the rightmost and vice versa. 2) Splay the given key k. Then {\displaystyle W=n} ( ( I will just show the insert item and splay. But how do we do this? A simple amortized analysis of static splay trees can be carried out using the potential method.