0

3.1kviews

Short note on Splay Tree and Trie

**1 Answer**

0

3.1kviews

Short note on Splay Tree and Trie

0

26views

written 5.7 years ago by | modified 5.7 years ago by |

**Splay Tree**

- 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.
- 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.
- 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".
- Splaying an element is the process of bringing it to the root position by performing suitable rotation operations.
- 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.
- 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.
- In a splay tree, to splay any element we use the following rotation operations...
- Zig Rotation
- Zag Rotation
- Zig - Zig Rotation
- Zag - Zag Rotation
- Zig - Zag Rotation
- Zag - Zig Rotation

**Tries**

- In computer science,tries is also called digital tree and sometimes radix tree or prefix tree.
- Tries is used for storing strings in order to support fast pattern matching.
- 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.
- Tries uses character of a key to guide the search process.
- All the descendants of the node have a common prefix of the string associated with that node.
- 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:**

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

**III. Suffix Tries:**

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

ADD COMMENT
EDIT

Please log in to add an answer.