Splay Tree

A splay tree is a self-balancing binary search tree. A splay tree guarantees that any M consecutive tree operations starting from an empty tree take at most O(MlogN) time. The net effect is: there is no bad input sequences.

Good performance for a splay tree depends on the fact that it is self-balancing, and indeed self optimizing, in that frequently accessed nodes will move nearer to the root where they can be accessed more quickly. This is an advantage for nearly all practical applications, and is particularly useful for implementing caches; however it is important to note that for uniform access, a splay tree's performance will be considerably (although not asymptotically) worse than a somewhat balanced simple binary search tree.

The basic idea of the splay tree is that after a node is accessed, it is pushed to the root by a series of avl tree rotations. The intuition behind this: when a node is accessed, it is likely to be accessed again in the near future in many real applications. The side effect is a balancing tree to some extent.

The splay tree does NOT require the maintenance of height or balance information, thus saving space and simplifying the code to some extent. Splay trees are much simpler to program than AVL trees.

Assume X be a node on the access path at which we are rotating. X has both a parent (P) and a grandparent (G).
Splay Operations: 1) zig-zag case, where X is a right child and P is a left child (or vice versa). we perform a double rotation, exactly like an AVL double rotation. 2) zig-zig case. X and P are both left children. 3) zig-case. X's only parent is the root.

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

avl Tree: balanced binary search tree

An avl (Adelson-Velskii and Landis) tree is a binary search tree with a balance condition, the height of the left and right subtrees can differ by at most 1. The depth of the tree is O(logn).

After an insertion, only nodes that are on the path from the insertion point to the root might have their balance altered because only those nodes have their subtrees altered.

Possible violation might occur in four cases:

1. An insertion into the left subtree of the left child
2. ...................................right........................................
3. .................................... left ........................ right .....
4. .................................. right ....................... right .....

1. and 4. could be fixed by single rotate

2. and 3. could be fixed by double rotate

Rotation operations only need a few pointer changes. The node will need to record the height info within it.

Deletion in avl Tree is somewhat more complicated than insertion. And lazy-deletion is probably the best strategy.


Reference: Data structures and Algorithm Analysis in C++ Page 136

B-Trees

a B-tree is a tree data structure that keeps data sorted and allows searches, insertions, and deletions in logarithmic amortized time. It is most commonly used in databases and filesystems.

A B-tree is kept balanced by requiring that all leaf nodes are at the same depth. This depth will increase slowly as elements are added to the tree, but an increase in the overall depth is infrequent, and results in all leaf nodes being one more hop further removed from the root.

B-trees have substantial advantages over alternative implementations when node access times far exceed access times within nodes. This usually occurs when most nodes are in secondary storage such as hard drives. By maximizing the number of child nodes within each internal node, the height of the tree decreases, balancing occurs less often, and efficiency increases. Usually this value is set such that each node takes up a full disk block or an analogous size in secondary storage. While 2-3 B-trees might be useful in main memory, and are certainly easier to explain, if the node sizes are tuned to the size of a disk block, the result might be a 129-513 B-tree.

Search: Search is performed in the typical manner, analogous to that in a binary search tree. Starting at the root, the tree is traversed top to bottom, choosing the child pointer whose separation values are on either side of the value that is being searched. Binary search is typically (but not necessarily) used within nodes to find the separation values and child tree of interest.

---------------------------------------
2-3 Tree

* Every non-leaf node has 2 or 3 children
* All data is kept in the leaves
* All leaves are at the same level (the bottom level)
* All data is kept in sorted order
* Every non-leaf node will contain 1 or 2 fields.

These contain one or two fields which indicate the range of values in its subtrees. If a node has two children, it will have one field; if the node has three children, it will have two fields. Each non-leaf node will contain a value in field 1 which is greater than the largest item in its left sub-tree, but less than or equal to the smallest item in its right sub-tree (or center sub-tree, if it has three children). If that node has three children, field 2 contains a value which is greater than the largest value in the center sub-tree, but less than or equal to the smallest item in its right sub-tree. The purpose of these values is to direct a search function to the correct sub-tree and eventually to the correct data node.

The biggest drawback with the 2-3 tree is that it requires more storage space than the normal binary search tree.
---------------------------------------
2-3-4 Trees

A 2-3-4 tree is a B-tree of order 4.

2-3-4 trees are relatively difficult to implement in most programming languages because of the large number of special cases involved in operations on the tree. Red-black trees (see below) are simpler to implement, so they tend to be used instead.
---------------------------------------

http://en.wikipedia.org/wiki/B-tree
http://en.wikipedia.org/wiki/2-3_tree

Red-Black Tree

A binary search tree is a red-black tree if:

1. Every node is either red or black
2. Every leaf (nil) is black
3. If a node is red, then both its children are black
4. Every simple path from a node to a descendant leaf contains the same number of black nodes

Black-height of a node x, bh(x), is the number of black nodes on any path from x to a leaf, not counting x. A red-black tree with n internal nodes has height at most 2lg(n+1).

Suffix Array

Suffix array: an array of pointers to characters. The pointers in the array point to every suffix in the string, hence the name "suffix array". Suffix array can be used to efficiently search a large text.

Applications:

1. Find the longest duplicated substring of characters in it.
The duplicated substring mush appear in two different suffixes. We sort the suffix array to bring together equal suffix. and then scan through this array comparing adjacent elements to find the longest repeated string. The running time is O(nlogn) due to sorting.

1.1. Given a new input string, How would you search a suffix array to find the longest match in the stored text?
1.2. Given two input texts, find the longest string that occurs in both.

2. Locate every occurrence of a substring within the string.
Finding every occurrence of the substring is equivalent to finding every suffix that begins with the substring. Thanks to the lexicographical ordering, these suffixes will be grouped together in the suffix array, and can be found efficiently with a binary search. If implemented straightforwardly, this binary search takes O(mlogn) time, where m is the length of the substring. To avoid redoing comparisons, extra data structures giving information about the longest common prefixes (LCPs) of suffixes are constructed, giving O(m + logn) search time.

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

Suffix Tree

The suffix tree for a string S is a tree whose edges are labeled with strings, and such that each suffix of S corresponds to exactly one path from the tree's root to a leaf. It is thus a radix tree for the suffixes of S.

Constructing such a tree for the string S takes time and space linear in the length of S.

Applications:
1. Check if a string P of length m is a substring in O(m) time


Subsequence, Substring, Suffix, Prefix

• Subsequence is a generalization of substring, suffix and prefix. Finding the longest string which is equal to a subsequence of two or more strings is known as the longest common subsequence problem.

• Substring of a string is a prefix of a suffix of the string, and equivalently a suffix of a prefix.

Lexicographical order(Lexicographic), dictionary order, alphabetic order
one may assume that all words have the same length, by adding blank spaces at the end, and considering the blank space as a special character which comes before any other letter in the alphabet. This also allows ordering of phrases.

References:
http://en.wikipedia.org/wiki/Suffix_%28computer_science%29
http://en.wikipedia.org/wiki/Suffix_tree
http://en.wikipedia.org/wiki/Lexicographical_order

Binary Search Tree

Binary Search Tree: for each node, all elements in its left tree are less than or equal to (<=) the node, and all the elements in its right tree are larger than the node. A binary search tree is different from a binary tree.

Binary Search Tree is good at insert and lookup. On average, binary tree will locate a node in O(logn) time. BST is a good way to practice recursion.

Typical operations on BST:
1. Search
2. Delete min value
3. Delete max value
4. Remove node
We need to consider several cases: 1) leaf node, simply delete it 2) node with only one child, then we delete the node and bypass its parent pointer to the node's child 3) node with two children. We first need to find the min node in the node's right tree, replace the node with this min value and then remove the min node.
5. Delete BST
You can implement this with an elegant recursive function.


struct node
{
int data;
struct node * left;
struct node * right;
}

Lookup()

BST Checking: Check every node to see whether it meets the BST definition.

*****
Q1: Print each path from root to leaf

void PrintArr(int path[], int pathLen)
{
int i;
for(i=0;idata;
pathLen++;
}

if(node->left == NULL && node->right == NULL)
PrintArr(path, pathLen);
else
{
RecurPrintPath(node->left, path, pathLen);
RecurPrintPath(node->right, path, pathLen);
}
}

void PrintPaths(struct node * node)
{
int path[1000];

RecurPrintPath(node, path, 0);
}

NOTE: A good recursion with a helper function. Watch how path and pathLen changes and the according values in different recursion level.

Q2: Print a binary tree level by level. Top down or Bottom up. How about one level per line for the output?

The top down idea is similar to breadth-first search (BFS) using QUEUE data structure. The bottom up idea can be achieved by recursively print the top down method or we can use a stack to simulate this procedure.

code snippet:

Top-Down

while(!Q.empty())
{
printf("%d ", Q.front()->data);
if(Q.front()->left!=NULL)
Q.push(Q.front()->left);
if(Q.front()->right!=NULL)
Q.push(Q.front()->right);
Q.pop();
}

Bottom-up

while(!Q.empty())
{
//printf("%d ", Q.front()->data);
S.push(Q.front());
if(Q.front()->right!=NULL)
Q.push(Q.front()->right);
if(Q.front()->left!=NULL)
Q.push(Q.front()->left);
Q.pop();
}

while(!S.empty())
{
printf("%d ", S.top()->data);
S.pop();
}
----------------Recursive Version-------------------

void PrintLevelRecur(queue <.struct node *.> Q)
{
if(Q.empty())
return;

struct node * tmp = NULL;

if(Q.front()->left!=NULL)
Q.push(Q.front()->left);
if(Q.front()->right!=NULL)
Q.push(Q.front()->right);

tmp = Q.front();
Q.pop();

PrintLevelRecur(Q);

printf("%d ", tmp->data);


}
void PrintLevelbyLevel(struct node * node) //wrapper function
{
queue<.struct node *.> Q;

if(node!=NULL)
Q.push(node);

PrintLevelRecur(Q);
}

Dynamic 2 dimension array