Trees
Q1. What are Binary Tree. Explain the Binary tree
representations with example .
Ans.
Binary Tree
A binary tree is made of nodes, where each node contains a "left" reference, a "right"
reference, and a data element. The topmost node in the tree is called the root.
Every node (excluding a root) in a tree is connected by a directed edge from exactly
one other node. This node is called a parent. On the other hand, each node can be
connected to arbitrary number of nodes, called children. Nodes with no children are
called leaves, or external nodes. Nodes which are not leaves are called internal nodes.
Nodes with the same parent are called siblings.
Binary Tree Representations
A binary tree data structure is represented using two methods. Those methods are as follows...
1. Array Representation
2. Linked List Representation
Consider the following binary tree...
1. Array Representation of Binary Tree
In array representation of a binary tree, we use one-dimensional array (1-D Array) to represent a binary
tree.
Consider the above example of a binary tree and it is represented as follows...
To represent a binary tree of depth 'n' using array representation, we need one dimensional array with
a maximum size of 2n + 1.
2. Linked List Representation of Binary Tree
We use a double linked list to represent a binary tree. In a double linked list, every node consists of
three fields. First field for storing left child address, second for storing actual data and third for storing
right child address.
In this linked list representation, a node has the following structure...
The above example of the binary tree represented using Linked list representation is shown as
follows...
Q2. Write short notes on:
a) Red-Black trees
b) splay trees
Ans (a).
Red-Black Trees
A red-black tree is a binary search tree with one extra attribute for each node:
the colour, which is either red or black. We also need to keep track of the parent of
each node, so that a red-black tree's node structure would be:
struct t_red_black_node {
enum { red, black } colour;
void *item;
struct t_red_black_node *left,
*right,
*parent;
}
For the purpose of this discussion, the NULL nodes which terminate the tree are
considered to be the leaves and are coloured black.
Basic red-black tree with
the sentinel nodes added.
Implementations of the red-
black tree algorithms will
usually include the sentinel
nodes as a convenient means
of flagging that you have
reached a leaf node.
They are the NULL black
nodes of property 2.
The number of black nodes on any path from, but not including, a node x to a leaf is
called the black-height of a node, denoted bh(x). We can prove the following lemma:
Ans (b). A splay tree is just a binary search tree that has excellent performance
in the cases where some data is accessed more frequently than others. The tree
self-adjusts after lookup, insert and delete operations.
A splay tree does not necessarily have mininum height, nor does it
necessarily have logarithmically bounded height.In fact a splay tree may
even be degenerate. However, it is based on the idea that if you recently used
something you'll likely need it again soon, so it keeps the most commonly used
data near the top where it is accessed most quickly.
A good animation of splay trees is here
How it Works
After each insert, delete, or lookup, you splay:
The node you just looked up, or
The node you just inserted, or
The parent of the node you just deleted
Q3. Suppose the numbers 7 , 5 , 1 , 8 , 3 , 6 , 0 , 9 , 4 , 2 are
inserted in that order into an initially empty binary search
tree. The binary search tree uses the usual ordering on
natural numbers.
What is the in order traversal sequence of the resultant tree?.
Ans.
We construct a binary search tree for the given elements.
We write the inorder traversal sequence from the binary search tree so obtained.
Following these steps, we have-
Q4. Give an algorithm for inserting an element into binary tree
Ans. Solution: Since the given tree is a binary tree, we can insert the element wherever we
want. To
insert an element, we can use the level order traversal and insert the element wherever we find
the node whose left or right child is NULL.
Q5. Give an algorithm for constructing binary tree from given Inorder
and Preorder traversals.
Solution: Let us consider the traversals below:
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F
