Tree Data Structure

Siblings - Nodes with the same parent

Depth of a node- number of edges from the root to the node.

Height of a node - number of edges from the node to the deepest leaf. 

Height of a tree - height of a root.

Binary Tree- tree where each node can have no more than two children (a node can have just one)

full binary tree - A binary tree in which each node has exactly zero or two children. There are no nodes with exactly one child.

Complete binary - completely filled, with the possible exception of the bottom level, which is filled from left to right.

Binary Search Tree - A binary tree is a binary search tree (BST) if and only if an inorder traversal of the binary tree results in a sorted sequence.

Binary Search Tree

• The keys in a binary search tree are always stored in such a way as to satisfy the binary-search-tree property:

Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y:key <= x:key. If y is a node in the right subtree of x, then y:key >= x:key.

• The expected height of a randomly built binary search tree on n distinct keys is O(lg n)

Tree Traversals

• In-Order - Left , Root, Right
• Pre-Order - Root, Left, Right
• Post- Order  Left, Right ,Root

INORDER-TREE-WALK(x)

if x !=NIL

INORDER-TREE-WALK(x:left)

print x:key

INORDER-TREE-WALK(x:right)

Complexity θ(n)

Tree Search

TREE-SEARCH(x,k)

if x == NIL or k == x:key

return x

if k < x:key

return TREE-SEARCH(x:left)

else

return TREE-SEARCH(x:right)

ITERATIVE-TREE-SEARCH(x, k)

while x != NIL and k != x:key

if k < x:key

x = x:left

else

x = x:right

return x

Complexity O(h) - h = Height of the tree

Minimum And Maximum

TREE-MINIMUM(x)

while x:left != NIL

x = x:left

return x

TREE-MAXIMUM(x)

while x:right !=NIL

x = x:right

return x

Complexity O(h)

Height of Tree

int height(node)

{

if (node = null)

    return 0;

else

    left = height(node->left);

    right = height(node->right);

    return 1 + max(left, right);

}

Complexity θ(n)

Tree Insert /Delete

Complexity O(h)

Red Black Trees

• One of many search-tree schemes that are “balanced” in order to guarantee that basic dynamic-set operations take O(lg n) time in the worst case.
• By constraining the node colors on any simple path from the root to a leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced.
• A red-black tree with n internal nodes has height at most 2 lg(n +1)
• Insert and delete will run in O(lg n) time

• A red-black tree is a binary tree that satisfies the following red-black properties:
• Every node is either red or black.
• The root is black.
• Every leaf (NIL) is black.
• If a node is red, then both its children are black.
• For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Trie

• Trie is an efficient information retrieval data structure.
• Using trie, search complexities can be brought to optimal limit (key length).
• If we store keys in binary search tree, a well balanced BST will need time proportional to O(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.
• However the penalty is on trie storage requirements. Memory requirements of trie is O(ALPHABET_SIZE * key_length * N) where N is number of keys in trie.
• There are efficient representation of trie nodes (e.g. compressed trie, ternary search tree, etc.) to minimize memory requirements of trie.
• TRIE has a wide variety of applications in :
• Spell checking. Word completion
• Data compression
• Computational biology
• Routing table for IP addresses
• Storing/Querying XML documents etc.
• For alphabetical keys, each node has an array of (27) pointers to its branches, one for each of the 26 alphabet characters and one for blank (“ ”). The keys are stored in leaf (information) nodes. To access an information node containing a key, we need to move down a series of branch nodes following appropriate branch based on the alphabetical characters composing the key. All trie_node fields that neither intern node nor to an leaf node are represented using null pointers.