In the part 1, we discussed Tree in brief. In this part, we
will discuss Binary Tree. Binary Tree has two additional constraints in
addition to what regular tree has. Any node in Binary Tree should not have more
than 2 children. Value at the left child should always be lesser than parent’s
value and value at the right child should not be lesser than parent’s value.
Only these two additional characteristics make any tree a Binary Tree. Here is the basic Java code of Tree Node
class Node
{
Int value;
node leftChild;
node rightChild;
}
We will discuss 3 common operations of Binary Tree.
- Find
- Insert
- Delete
Find
Finding a node with a specific key is the simplest all the 3
major operation. Start from root and traverse down the tree until key is found or
leaf node is reached. Here are three steps to
- Check the value of current node, if value is same as search key, return location.
- If value of current node is greater than search key, go to the left sub-tree
- If value of current node in lesser than search key, go to right sub-tree.
Start with setting root as current, execute the above three
steps unless leaf node is hit or value has been found. If program hits leaf
node traversing down the tree searching for key, it means search key not found.
public Node findValnode(int value)
{
Node
current = root;
while(current
!= null)
{
if(current.getValue()
== value)
{
return
current;
}
else
if(value < current.getValue())
current
= current.getLeftChild();
else
current
= current.getRightChild();
}
return
null;
}
Insert
To insert a node, we must find place to insert the node.
Insertion is almost same as finding a node. Take value to insert as search key
and insert the value at found place. If value is not found in the tree, it will
be added to any leaf node as either left child or right child depending upon
its value. Even if value is found and duplicate is allowed in tree, it will be
added in right sub-tree to the found node. Below are the steps to insert a
node.
- Create a node with the given value
- Search the given value in the tree.
- Insert the node as left child/ right child, depending upon its value, to the leaf node where Tree Traversing ended.
Below is the java code for Insertion in tree.
public void insert(int value)
{
Node
node = new Node();
node.setValue(value);
if(root
== null)
{
root
= node;
}
else
{
Node
current = root;
Node
parent = root;
while(true)
{
parent
= current;
if(value
< current.getValue())
current
= current.getLeftChild();
else
current
= current.getRightChild();
if(current
== null && value < parent.getValue())
{
parent.setLeftChild(node);
break;
}
else
if(current == null && value >= parent.getValue())
{
parent.setRightChild(node);
break;
}
}
}
}
Delete
Delete is the most complicated common operation of Binary
Tree. First find the node to delete, use same approach as for Find operation.
Once the node is found, there are three cases to consider before deleting the
node
Case
1.
The node to be deleted is leaf node
Case
2.
The node to be deleted has only one child
Case
3.
The node to be deleted has two children
Case 1: It is simplest of all above cases. To delete a leaf
node, change the appropriate child field in node’s parent to null
Case 2: This case is
also not that complicated. Node to be deleted has only two connections: one to
its parent and second to its child. To delete the node, just remove the node
from the sequence. Connect the node’s parent directly to its child.
Case 3: This is little tricky and complicated. If the
deleted node has 2 children, we cannot just replace it with one of these
children. There are various cases to consider.
Good news is there is trick to handle these cases. Find the
inorder successor of the node to be deleted.
Literally speaking, inorder successor is the next highest value in the
tree. It means, this successor should be in the right sub tree of the node to
be deleted. For sake of information, inorder, preorder and postorder are the
three ways a binary tree can be traversed. We will discuss the Tree Traversal
Algorithms in detail in some other post. For this post, let not digress from
the main topic and let keep this post simple. Here is java code to find inorder
successor of a node (This is just for reference)
private Node getSuccessor(Node delNode)
{
Node
successorParent = delNode;
Node
successor = delNode;
Node
current = delNode.getRightChild();
while(current
!= null)
{
// left children,
successorParent
= successor;
successor
= current;
current
= current.getLeftChild();
}
//
if successor not
if(successor
!= delNode.getRightChild()) // right child,
{
// make connections
successorParent.setLeftChild(successor.getRightChild());
successor.setRightChild(delNode.getRightChild());
}
return
successor;
}
Once we have successor in hand, there are two cases to
handle to delete the node.
Successor is the
right child of the node to be deleted
If the successor is the right child of the node to be
deleted, then this right child does not have left child. Let refer node to be
deleted as current node. The deletion can be done in two steps
- Remove reference to current from its parents and set reference to successor in that place
- Set successor left child to point to current’s left child.
Successor Is Left
Descendant of Right Child of the node to be deleted
If the successor is the left descendant of right child of
the node to be deleted, deletion takes place in four steps. Let refer node to
be deleted as current node.
- Plug the right child of the successor into the left child of its parent.
- Plug the right child of the current to the right child of its successor
- Unplug current node from the its parent and set successor in that place
- Unplug left child of the current and set it into successor left child
No comments:
Post a Comment