{"id":398,"date":"2018-07-19T06:52:21","date_gmt":"2018-07-19T06:52:21","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=398"},"modified":"2018-12-12T11:27:53","modified_gmt":"2018-12-12T11:27:53","slug":"splay-trees","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/splay-trees\/","title":{"rendered":"Splay Trees"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n

Welcome to the e-PG Pathshala Lecture Series on Data Structures. In this module we will discuss another self balbalanced tree \u2013 Splay Trees.<\/p>\r\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of the module are as follows:\r\n\r\n \r\n\r\n\u2022\u00a0 To understand the idea behind Splay Trees\r\n\r\n\u2022\u00a0 To discuss the cases of SplayTrees\r\n\r\n\u2022\u00a0 To describe the operations of Splay Trees\r\n\r\n\u2022\u00a0 To outline the advantages of Splay Trees\r\n\r\n \r\n\r\n27.1 Basic Idea<\/strong>\r\n\r\n \r\n

The basic idea of the splay tree is thatevery time a node is accessed, assuming that access to this node will be needed immediately, it is pushed up to the root by a series of tree rotations<\/em><\/strong> knowing assplaying so that the search time for that node is the minimum. The idea is that if the node being splayedis deep, manynodes on the path to that node are alsodeep and by restructuring the tree, wemake access to all of those nodes cheaperin the future, again assuming that nodes nearer a node already accessed will be needed sooner than other nodes.<\/p>\r\n \r\n

We carry out a\u201c<\/strong>Blind\u201d rebalancing height information is kept. In spite of this the worst-case time per operation is O(n<\/em>) but the worst-case amortized time is O(log n<\/em>). We had already discussed amortized analysis as the worst case analysis of the average cost per operation of a sequence of operations. During Insert\/find operations we always rotate the inserted node or the node that is searched to the root. <\/em>We maintain the property of good locality where we move the commonly accessed keys high up the tree so that they become easier and easier to find.<\/p>\r\n\r\n<\/div>\r\n\"\"\r\n

\r\n

Figure 27.1 Splay Tree<\/strong><\/p>\r\n \r\n

We move the node n (the node just inserted or just searched for) to the root by a series of zig-zag and zig-zig rotations. When we are forced to make a deep access, we ensure that we also fix up a lot of deep nodes towards the root (Figure 27.1).<\/p>\r\n \r\n\r\n27.2 Splay Trees<\/strong>\r\n\r\n \r\n

Splay trees are binary search trees (BSTs) that are not perfectly balanced all the time but allow search and insertion operations to try to balance the tree so that future operations can run faster. The splay trees are based on the heuristic that if a node X is accessed once, it is likely to be accessed again.A fter node X is accessed, we perform \u201csplaying\u201d operations to bring X up to the root of the tree. We perform splaying in such a manner that it leaves the tree more or less balanced as a whole.<\/p>\r\n \r\n\r\n27.2.1 Motivating Example<\/strong>\r\n\r\n \r\n

Let us understand the concept of splay trees using a motivating example. In the example shown in Figure 27.2, after we search for 12, splaying with 12 makes the tree balanced<\/strong>and 12 moves to the root. Subsequent accesses for 12 will take O(1)<\/strong> time, We perform splay with active (recently accessed)<\/strong> nodes, they will move towards the root and inactive nodes will slowly move further from the root<\/p>\r\n \r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n27.3 Six Cases of Splaying<\/strong>\r\n\r\n \r\n

Let X be a non-root node, i.e., has at least 1 ancestor. Let P be its parent node and Let G be its grandparent node (if it exists). Now let us consider a path from G to X. Every time we traverse a left subtree, we have \u201czig\u201dtype of splay and correspondingly every time we traverse a right subtree, we have \u201czag\u201d type of splay. Now with this basis let us discuss the six cases of splaying (Figure 27.3). The first case is a \u201czig\u201d, when X is the left child of P. The second case is a \u201czag\u201d, when X is the right child of P. Next is \u201czig-zig\u201d when X is the left child of P and in turn P is left child of G. The fourth case is \u201czig-zag\u201d, when P is left child of G, but X is the right\u00a0child of P. The fifth case is \u201czag-zig\u201d, when P is right child of G, and X is the left child of P. The fifth case is \u201czag-zig\u201d, when P is right child of G, and X is the left child of P, the final sixth case is \u201czag-zag\u201d, when X is the right child of P and in turn P is right child of G.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n\r\n27.4 Splay Operation<\/strong>\r\n\r\n \r\n

Now let us discuss the splay operation in detail. We traverse the tree from node x we want to splay to root, rotating along the way until xis the root.<\/p>\r\n \r\n\r\nRotation<\/strong>\r\n\r\n \r\n\r\nNow at each rotation, if x is the root, do nothing.\r\n\r\nIf x has no grandparent, rotate x about its parent<\/strong>.\r\n\r\nIf x has a grandparent,\r\n