Session 5-Tree & Binary Tree

Subtopic:
-Binary Tree Termology
-Advantages of Tree
-Binary Search Tree
-Threaded Binary Tree

Binary Tree Termology

• The depth of a node is the number of edges from the root to the node.
• The height of a node is the number of edges from the node to the deepest leaf.
• The height of a tree is a height of the root.
• A full binary tree.is a binary tree in which each node has exactly zero or two children.
• A complete binary tree is a binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right.

A complete binary tree is very special tree, it provides the best possible ratio between the number of nodes and the height. The height h of a complete binary tree with N nodes is at most O(log N).

Advantages of Tree

Trees are so useful and frequently used, because they have some very serious advantages:

• Trees reflect structural relationships in the data
• Trees are used to represent hierarchies
• Trees provide an efficient insertion and searching
• Trees are very flexible data, allowing to move subtrees around with minumum effort

Binary Search Tree

We consider a particular kind of a binary tree called a Binary Search Tree (BST). The basic idea behind this data structure is to have such a storing repository that provides the efficient way of data sorting, searching and retriving.

Insertion

The insertion procedure is quite similar to searching. We start at the root and recursively go down the tree searching for a location in a BST to insert a new node. If the element to be inserted is already in the tree, we are done (we do not insert duplicates). The new node will always replace a NULL reference.

Searching
Searching in a BST always starts at the root. We compare a data stored at the root with the key we are searching for (let us call it as toSearch). If the node does not contain the key we proceed either to the left or right child depending upon comparison. If the result of comparison is negative we go to the left child, otherwise - to the right child. The recursive structure of a BST yields a recursive algorithm.

Deletion
Deletion is somewhat more tricky than insertion. There are several cases to consider. A node to be deleted (let us call it as toDelete)

• is not in a tree;
• is a leaf;
• has only one child;
• has two children.

If toDelete is not in the tree, there is nothing to delete. If toDelete node has only one child the procedure of deletion is identical to deleting a node from a linked list - we just bypass that node being deleted

Deletion of an internal node with two children is less straightforward. If we delete such a node, we split a tree into two subtrees and therefore, some children of the internal node won't be accessible after deletion. In the picture below we delete 8:

Threaded Binary Tree
A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node.   

• We have the pointers reference the next node in an inorder traversal; called threads
• We need to know if a pointer is an actual link or a thread, so we keep a boolean for each pointer

Types of threaded binary trees:

• Single Threaded: each node is threaded towards either the in-order predecessor or successor (left or right) means all right null pointers will point to inorder successor OR all left null pointers will point to inorder predecessor.
• Double Threaded: each node is threaded towards both the in-order predecessor and successor (left and right) means all right null pointers will point to inorder successor AND all left null pointers will point to inorder predecessor.