Page 166 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 7: Splay Trees

7.5 Splay Tree Application Notes

The application is Lexicographic Search Tree (LST).

Figure 7.1: An example of LST

b

d
a
0
h
a
t
a g
e
s y

t y

s

In a LST all the circles and squares are the nodes of the tree. Each node will contain a character.
And the square nodes are terminal nodes of the strings. There are two kinds of edges, solid
line edges and dashed line edges in LST. Solid line edges forms the splay tree and the nodes
connected by a solid line represent different strings. The dashed line edges are used to represent
a single string therefore the order of the nodes connected by a dashed line cannot be changed.
Figure 7.1 shows an example of a LST. Form the Figure 7.1, it stores different words: “at”, “as”,
“bat”, “bats”, “bog”, “boy”, “day” and “he”.

When a string is requested you just splay the character in the string one by one. Figure 7.2 shows
how to splay a character ‘a’ in a LST.
As you can see, the character ‘a’ will not be splayed to the root because ‘h’ and ‘d’ are the prefi x
of ‘a’ but it will move to the position most near the root. In LST, after the string is accessed, the
first character of the string will become the root as a result the most frequent accessed string

will be near the root. And LST store the prefi x for different strings this reduce the redundancy
for storing the strings. Besides LST, the splay tree can also be used for data compression, e.g.
dynamic Huffman coding.

LOVELY PROFESSIONAL UNIVERSITY 161