SPLAY TREE The basic idea of the splay tree is that every time a node is accessed, it is pushed to the root by a series of tree rotations. This series. - презентация

1 SPLAY TREE The basic idea of the splay tree is that every time a node is accessed, it is pushed to the root by a series of tree rotations. This series of tree rotations is knowing as splaying. It is binary search tree Two types of splay tree i) single step (single rotation) ZIG ZAG

2 ii) Double step (Splaying) ZIG ZIG ZAG Splay is performed during Search, insert, delete Moves a node at the root Improved behavior during repeated access of data

3 Splay Operation To splay node x, traverse up the tree from node x to root, rotating along the way until x is the root. For each rotation: If x is root, do nothing. If x has no grandparent, rotate x about its parent. If x has a grandparent, if x and its parent are both left children or both right children, rotate the parent about the grandparent, then rotate x about its parent. if x and its parent are opposite type children (one left and the other right), rotate x about its parent, then rotate x about its new parent (former grandparent).

4 Node has no grandparent –Zig: If parent(k1) is the root, rotate parent(k1) to get k1 to the root (This is a terminal case).

5 The single rotation does not work here Because it use only left rotations z5 z4 z1 z3 z2 A DC E F B

6 Splaying The cost of any splay operation is O(log n). This implies that splay trees can actually adapt to perform searches on frequently requested items much faster than O(log n) in some cases.

7 Eg., z5 z1 z3 z2 A DC F B z4 E

8 Node and Parent are Same Side Zig-Zig If parent(x) is not the root and x and parent(x) are both left or both right children, rotate grandparent(x) followed by rotate parent(x).

9 Node and Parent are Different Sides Zig-Zag If parent(x) is not the root and x is a left child and parent(x) a right child or vice-versa, rotate parent(x) and then rotate the new parent(x).

10 Operations on Splay Trees Remove splay element to be removed if the element to be deleted is not in the tree, the node last visited on the search path is splayed disconnect left and right sub trees from root do one or both of: splay max item in TL (then TL has no right child) splay min item in TR (then TR has no left child) connect other sub tree to empty child of root

11 Insertion in order into a Splay Tree

12 An extreme example of splaying

13 When to splay? Whenever we search, insert, delete Which nodes are splayed after each operation? Search – If node found – use that node – If node not found use last node in the search path Insert – Use the new node Remove – Use the parent of the node that was actually deleted – I.e. the deepest node

14 Advantages: –Can be much more efficient if usage pattern is skewed. Good heuristics can have amortized running time similar to the running time of the best structure –Require less space as no balance information is required Disadvantages: –More local adjustments during look-up operations (balanced trees only make adjustments during updates) –Individual operations can be expensive – drawback for real- time applications