splay tree application notes the application is lexicographic search tree (lstfigure an example of lst in lst all the circles and squares are the nodes of the tree each node will contain character and the square nodes are terminal nodes of the strings there are two kinds of edgessolid line edges and dashed line edges in lst solid line edges forms the splay tree and the nodes connected by solid line represent different strings the dashed line edges are used to represent single string therefore the order of the nodes connected by dashed line cannot be changed figure shows an example of lst form the figure it stores different words"at""as""bat""bats""bog""boy""dayand "hewhen string is requested you just splay the character in the string one by one figure shows how to splay character 'ain lst as you can seethe character 'awill not be splayed to the root because 'hand 'dare the prefix of 'abut it will move to the position most near the root in lstafter the string is accessedthe first character of the string will become the root as result the most frequent accessed string will be near the root and lst store the prefix for different strings this reduce the redundancy for storing the strings besides lstthe splay tree can also be used for data compressione dynamic huffman coding lovely professional university