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.
