27-11-2012, 01:28 PM
Splay Trees
1Splay Trees[.ppt (Size: 349 KB / Downloads: 81)
Splay Trees are Binary Search Trees
BST Rules:
items stored only at internal nodes
keys stored at nodes in the left subtree of v are less than or equal to the key stored at v
keys stored at nodes in the right subtree of v are greater than or equal to the key stored at v
An inorder traversal will return the keys in order
Splay Tree Definition
a splay tree is a binary search tree where a node is splayed after it is accessed (for a search or update)
deepest internal node accessed is splayed
splaying costs O(h), where h is height of the tree – which is still O(n) worst-case
O(h) rotations, each of which is O(1)
Amortized Analysis of Splay Trees
Running time of each operation is proportional to time for splaying.
Define rank(v) as the logarithm (base 2) of the number of nodes in subtree rooted at v.
Costs: zig = $1, zig-zig = $2, zig-zag = $2.
Thus, cost for playing a node at depth d = $d.
Imagine that we store rank(v) cyber-dollars at each node v of the splay tree (just for the sake of analysis).
Performance of Splay Trees
Recall: rank of a node is logarithm of its size.
Thus, amortized cost of any splay operation is O(log n).
In fact, the analysis goes through for any reasonable definition of rank(x).
This implies that splay trees can actually adapt to perform searches on frequently-requested items much faster than O(log n) in some cases. (See Theorems 3.10 and 3.11.)