unit splay trees unit splay trees notes contents objectives introduction splay trees operations splay operation rotations splay tree application summary keywords self assessment review questions further readings objectives after studying this unityou will be able todescribe splay trees explain splay tree operation introduction splay trees are binary search trees that achieve our goals by being self-adjusting in quite remarkable wayevery time we access node of the treewhether for insertion or retrievalwe perform radical surgery on the treelifting the newly accessed node all the way upso that it becomes the root of the modified tree other nodes are pushed out of the way as necessary to make room for this new root nodes that are frequently accessed will frequently be lifted up to become the rootand they will never drift too far from the top position inactive nodeson the other handwill slowly be pushed farther and farther from the root it is possible that splay trees can become highly unbalancedso that single access to node of the tree can be quite expensive later in this sectionhoweverwe shall prove thatover long sequence of accessessplay trees are not at all expensive and are guaranteed to require not many more operations even than avl trees the analytical tool used is called amortized algorithm analysissincelike insurance calculationsthe few expensive cases are averaged in with many less expensive cases to obtain excellent performance over long sequence of operations splay trees splay trees were invented by sleator and tarjan this data structure is essentially binary tree with special update and access rules it has the property to adapt optimally to sequence of tree operations more preciselya sequence of operations on tree with initially nodes takes time ( ln (nm ln ( )lovely professional university