Finding Maximum and Minimum Values
Incidentally, we should note how easy it is to find the maximum and minimum values in a binary search tree. In fact, this process is so easy we will show code for it. Still, understanding how it works is important. For the minimum, go to the left child of the root; then go to the left child of that child, and so on, until you come to a node that has no left child. This node is the minimum, as shown in Figure below:
Binary Trees Minimum 47 22 67 63 71 33 17 11 60 51 50 49 53 FIGURE Minimum value of a tree.
Here’s some code that returns the node with the minimum key value:
Node* minimum() // returns node with minimum key value
{
Node* current, last;
current = root; // start at root
while(current != null) // until the bottom
{
last = current; // remember node
current = current.leftChild; // go to left child }
return last;
}
We’ll need to know about finding the minimum value when we set about deleting a node. For the maximum value in the tree, follow the same procedure, but go from right child to right child until you find a node with no right child. This node is the maximum. The code is the same except that the last statement in the loop is
C++ Code To Find Maximum Value In Binary Search Tree
public Node maximum() // returns node with maximum key value
{
Node current, last;
current = root; // start at root
while(current != null) // until the bottom
{
last = current; // remember node
current = current.rightChild; // go to right child
}
return last;
}
Note:
The binary search tree algorithm is a much fast algorithm than its similar algorithms that we have learnt before like Singly Linked List, Doubly Linked List and other similar algorithms. If we have 1,000,000 nodes and if we use other algorithms for search etc. it will take approximately 500,000 comparisons but if we do the same task with binary search algorithm it will take only 20 or fewer comparisons, so it is much more efficient than its similar algorithms.
No comments:
Post a Comment