Hierarchical Data Structure

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)
    • Find shortest path in graph
  • 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

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a website or blog at WordPress.com

Up ↑

%d bloggers like this: