Advanced misc data structure

• Treap (A Randomized Binary Search Tree)
• Ternary Search Tree
• Interval Tree
• Implement LRU Cache
• Sort numbers stored on different machines
• Find the k most frequent words from a file
• Given a sequence of words, print all anagrams together
• Tournament Tree (Winner Tree) and Binary Heap
• Decision Trees – Fake (Counterfeit) Coin Puzzle (12 Coin Puzzle)
• Spaghetti Stack
• Data Structure for Dictionary and Spell Checker?
• Binary Indexed Tree
• Cartesian Tree
• Cartesian Tree Sorting
• Sparse Set
• Centroid Decomposition of Tree
• Gomory-Hu Tree

K Dimensional Tree

• KD Tree (Search and Insert)
• K D Tree (Find Minimum)
• K D Tree (Delete)

Segment Tree

• Segment Tree | Set 1 (Sum of given range)
• Segment Tree | Set 2 (Range Minimum Query)
• Lazy Propagation in Segment Tree

B Tree

• B-Tree | Set 1 (Introduction)
• B-Tree | Set 2 (Insert)
• B-Tree | Set 3 (Delete)

Splay Tree

• Splay Tree | Set 1 (Search)
• Splay Tree | Set 2 (Insert)

Quadtree / Locate a tower

Discuss the Quadtree data structure and its application.

http://en.wikipedia.org/wiki/Quadtree

Question:

Given a city in form of a square. There are various cell towers located at various points in the square city (say (x,y)). The distribution

of towers is totally random. Now given an (x,y) point, design a data structure that will help you tell whether the cell tower is present at that

location or not.(of course optimal)

Quadtree

Discuss the Quadtree data structure and its application.

http://en.wikipedia.org/wiki/Quadtree

Question:

Given a city in form of a square. There are various cell towers located at various points in the square city (say (x,y)). The distribution

of towers is totally random. Now given an (x,y) point, design a data structure that will help you tell whether the cell tower is present at that

location or not.(of course optimal)

Interval Tree & Overlapping Intervals

Discuss the use and implementation for Interval trees. 

You have N pairs of intervals, say integers. You're required to identify all intervals that overlap with each other in O(N logN) time. For example, if you have

{1, 3} {12, 14} {2, 4} {13, 15} {5, 10}

the answer is {1, 3}, {12, 14}, {2, 4}, {13, 15}. Note that you don't need to group them, so the result can be in any order like in the example.

Red Black Tree

Discuss Red Black Tree and its application


Application:
Propose a tree based data structure to identify a node with nth rank with maximum efficiency 


Hint:Use a red-black tree with size of subtree as another element in the structure of each node.

size(node) = size(node->left)+sizeof(node->right)+1;

for each node rank = size(node->left)+1;

• Red-Black Tree Introduction
• Red Black Tree Insertion.
• Red-Black Tree Deletion
• Program for Red Black Tree Insertion

Suffix Tree

Discuss suffix trees and their application

 Useful Links:
http://www.allisons.org/ll/AlgDS/Tree/Suffix/
http://en.wikipedia.org/wiki/Suffix_tree

• Suffix Array Introduction
• Suffix Array nLogn Algorithm
• kasai’s Algorithm for Construction of LCP array from Suffix Array
• Suffix Tree Introduction
• Ukkonen’s Suffix Tree Construction – Part 1
• Ukkonen’s Suffix Tree Construction – Part 2
• Ukkonen’s Suffix Tree Construction – Part 3
• Ukkonen’s Suffix Tree Construction – Part 4,
• Ukkonen’s Suffix Tree Construction – Part 5
• Ukkonen’s Suffix Tree Construction – Part 6
• Generalized Suffix Tree
• Build Linear Time Suffix Array using Suffix Tree
• Substring Check
• Searching All Patterns
• Longest Repeated Substring,
• Longest Common Substring, Longest Palindromic Substring

Suffix Tree Applications

Suffix Trees can be used to solve a large number of string problems that occur in text-editing, free-text search, computational biology, and other application areas. Some examples are given below.

String Search
Searching for a substring, pat[1..m], in txt[1..n], can be solved in O(m) time (after the suffix tree for txt has been built in O(n) time).

Longest Repeated Substring
Add a special ``end of string'' character, e.g. `$', to txt[1..n] and build a suffix tree; the longest repeated substring of txt[1..n] is indicated by the deepest fork node in the suffix tree, where depth is measured by the number of characters traversed from the root,i.e., `issi' in the case of `mississippi'. The longest repeated substring can be found in O(n) time using a suffix tree.

Longest Common Substring
The longest common substring of two strings, txt1 and txt2, can be found by building a generalized suffix tree for txt1 and txt2: Each node is marked to indicate if it represents a suffix of txt1 or txt2 or both. The deepest node marked for both txt1 and txt2 represents the longest common substring.
Equivalently, one can build a (basic) suffix tree for the string txt1$txt2#, where `$' is a special terminator for txt1 and `#' is a special terminator for txt2. The longest common substring is indicated by the deepest fork node that has both `...$...' and `...#...' (no $) beneath it.

Note that the `longest common substring problem' is different to the `longest common subsequence problem' which is closely related to the `edit-distance problem': An instance of a subsequence can have gaps where it appears in txt1 and in txt2, but an instance of a substringcannot have gaps.

Palindromes
A palindrome is a string, P, such that P=reverse(P). e.g. `abba'=reverse(`abba'). e.g. `ississi' is the longest palindrome in `mississippi'.
The longest palindrome of txt[1..n] can be found in O(n) time, e.g. by building the suffix tree for txt$reverse(txt)# or by building the generalized suffix tree for txt and reverse(txt).

AVL Tree

Discuss insertions in AVL tree and its application

• AVL Tree | Set 1 (Insertion)
• AVL Tree | Set 2 (Deletion)
• AVL with duplicate keys