### Hierarchical Data Structure:

- Binary Tree
- Node can have at most two children
- Contain ROOT Node
- Every Node have following
- Reference of Left Node
- Reference of Right Node
- Data

- Traversal
- Depth First Traversal : In Order (LRtR) | Pre Order (RtLR) | Post Order (LRRt)
- Breadth First Traversal: Level Order Traversal

- Properties
- Max no of node at level = 2l-1
- Max no of node = 2h-1
- Minimum Possible Height =Ceil(Log2(n+1))
- No of leaf node = no of node with two child +1
- Time Complexity for traversal O(n)

- Usage :
- File System , Javascript DOM

- Binary Search Tree
- Left Node have key less then parent node key.
- Right Node have key greater than parent node key
- Both Left and Right Subtree should be binary tree.
- Time Complexity
- Search, Insert and Delete : O(h)
- If Tree is Balance h = O(logn)

- BST provide moderate access/search (quicker than Linked List and slower than arrays).
- BST provide moderate insertion/deletion (quicker than Arrays and slower than Linked Lists).

- Binary Heap
- Complete Binary Tree
- Types of Ordering
- Min Heap : Parent have minimum then child nodes
- Max Heap: Parent have maximum then child nodes

- Complexity
- Get Min/Max in Min/Max Heap => O(1)
- Extract Min/Max from Min/Max Heap => O(logn)
- Decrease Min?Max in Min?max heap => O(log)
- Insert/Delete => O(logn)

- Implementing priority queue
- Order statistics finding kth smallest element
- Cannot be used for searching particular elemment

- Hashing
- A function that convert bigger input to smaller particular int value
- Mapped integer value is used as index of table
- Properties
- Efficiently computable
- Uniformly distribute keys

- Collision Handling
- When two keys have same hash value
- Chaining : each cell of hash table point to linked list of records that have same hash function, requires additional memory
- Insert/Delete/Search : O(n) [worst case]
- Insert/Delete/Search : O(1) [average case]

- Hashing seems better than BST for all the operations. But in hashing, elements are unordered and in BST elements are stored in an ordered manner.
- Also BST is easy to implement but hash functions can sometimes be very complex to generate.
- In BST, we can also efficiently find floor and ceil of values.
- Hashing can be used to remove duplicates from a set of elements.
- Can also be used find frequency of all items.

- Graph
- Must have
- Finite set of vertices (Nodes)
- Finite Set of ordered pair of (u,v) called edges

- Classifications
- Undirected : BiDirectional And Directed : Unidirectional
- Weight Edge & Unweight Edge

- Representation of graph
- Adjacency Matrix
- Complexity : Traversal & Space => O(v^2)

- Adjacency List
- Complexity : Traversal => O(ElogV) & Space =>O(V+E)

- Adjacency Matrix
- Find shortest path in graph

- Must have
- Trie
- Efficient data structure for searching in dictionaries
- If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum string length and N is number of keys in tree.
- Using trie, we can search the key in O(M) time. So it is much faster than BST.
- Hashing also provides word search in O(n) time on average. But the advantages of Trie are there are no collisions (like hashing) so worst case time complexity is O(n).
- With Trie, we can find all words beginning with a prefix (This is not possible with Hashing).
- Require a lot of extra space. Tries are also known as radix tree or prefix tree.
- The most common use of Tries is to implement dictionaries due to prefix search capability.
- Tries are also well suited for implementing approximate matching algorithms, including those used in spell checking.
- It is also used for searching Contact from Mobile Contact list OR Phone Directory.

- Segment Tree
- Implemented when there are a lot of queries on a set of values.
- These queries involve minimum, maximum, sum, .. etc on a input range of given set.
- Queries also involve updation of values in given set.
- Segment Trees are implemented using array.
- Complexity
- Construction of segment tree : O(N)
- Query/Update : O(log N)
- Space : O(N) [Exact space = 2*N-1]

- It is used when we need to find Maximum/Minumum/Sum/Product of numbers in a range.

- Suffix Tree
- Suffix Tree is mainly used to search a pattern in a text.
- The idea is to preprocess the text so that search operation can be done in time linear in terms of pattern length.
- The pattern searching algorithms like KMP, Z, etc take time proportional to text length.
- This is really a great improvement because length of pattern is generally much smaller than text.
- Imagine we have stored complete work of William Shakespeare and preprocessed it.You can search any string in the complete work in time just proportional to length of the pattern.
- But using Suffix Tree may not be a good idea when text changes frequently like text editor, etc.
- Suffix Tree is compressed trie of all suffixes, so following are very abstract steps to build a suffix tree from given text.
- Generate all suffixes of given text.
- Consider all suffixes as individual words and build a compressed trie.

- Used to find find all occurrences of the pattern in string.
- It is also used to find the longest repeated substring (when test doesn’t change often), the longest common substring and the longest palindrome in a string.

Advertisements

## Leave a Reply