Splay Tree

1. Splay tree is another varient of binary search tree. In a splay tree, the recently accessed element is placed at the root of the tree.
2. A splay tree is defined a self - adjusted Binary Search Tree in which every operation on an element rearrange the tree so that the element is placed at the root position of the tree.
3. In a splay tree, every operation is performed at root of the tree. All the operations on a splay tree are involved with a common operation called "Splaying".
4. Splaying an element is the process of bringing it to the root position by performing suitable rotation operations.
5. In a splay tree, splaying an element rearrange all the elements in the tree so that splayed element is placed at root of the tree.
6. With the help of splaying an element we can bring most frequently used element closer to the root of the tree so that any operation on those element performed quickly.
7. In a splay tree, to splay any element we use the following rotation operations...
   1. Zig Rotation
   2. Zag Rotation
   3. Zig - Zig Rotation
   4. Zag - Zag Rotation
   5. Zig - Zag Rotation
   6. Zag - Zig Rotation

Tries

1. In computer science,tries is also called digital tree and sometimes radix tree or prefix tree.
2. Tries is used for storing strings in order to support fast pattern matching.
3. Tries are used for information retrieval.Tries is used to store the character in each node not the key.Path from root to node is associated with key.
4. Tries uses character of a key to guide the search process.
5. All the descendants of the node have a common prefix of the string associated with that node.
6. Following are the Types of Tries:

I. Standard Tries:

The standard tries for a set of strings S is an ordered tree such that:

a. Each node but the root is labeled with a character.

b. The children of a node are alphabetically ordered

c. The paths from the external nodes to the root yield the strings of S.

II. Compressed Tries:

1. Compressed Tries are with nodes of degree at least 2.
2. They are Obtained from standard tries by compressing chains of redundant nodes.

III. Suffix Tries:

1. A suffix trie is a compressed trie for all the suffixes of a text.
2. The suffix trie for a text X of size n from an alphabet of size d.
3. Suffix tries stores all the n(n−1)/2 suffixes of X in O(n) space.
4. Suffix tries supports arbitrary pattern matching and prefixes matching queries in O(dm) time, where m is the length of the pattern.