Binary Search Trees (BST):
A binary search tree, also known as an ordered binary tree. In
a binary search tree, all the nodes in the left sub-tree have a value less than
that of the root node. Correspondingly, all the nodes in the right sub-tree
have a value either equal to or greater than the root node. The same rule is
applicable to every sub-tree in the tree.
In the above figure, we can observe that the root node is
40, and all the nodes of the left subtree are smaller than the root node, and
all the nodes of the right subtree are greater than the root node.
Similarly, we can see the left child of root node is greater
than its left child and smaller than its right child. So, it also satisfies the
property of binary search tree. Therefore, we can say that the tree in the
above image is a binary search tree.
In the above tree, the value of
root node is 40, which is greater than its left child 30 but smaller than right
child of 30, i.e., 55. So, the above tree does not satisfy the property of
Binary search tree. Therefore, the above tree is not a binary search tree.
Example
of creating a binary search tree
Example : State whether the binary trees in below Fig. are binary search trees or not.
Example : Now, let's
see the creation of binary search tree using an example.
Suppose the
data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50
- First, we have to insert 45 into
the tree as the root of the tree.
- Then, read the next element; if it
is smaller than the root node, insert it as the root of the left subtree,
and move to the next element.
- Otherwise, if the element is larger
than the root node, then insert it as the root of the right subtree.
Now, let's
see the process of creating the Binary search tree using the given data
element. The process of creating the BST is shown below
Example : Create a binary search tree using the following data elements: 45, 39, 56, 12, 34, 78, 32, 10, 89, 54, 67, 81
No comments:
Post a Comment