Types of Trees : 2_Binary Search Tree(BST)

NEED:

The solution to our search problem is to store the collection of data to be searched using a binary tree in such a way that searching for a particular item takes minimal effort. The underlying idea is simple: At each tree node, we want the value of that node to either tell us that we have found the required item or tell us which of its two subtrees we should search for it in. For the moment, we shall assume that all the items in the data collection are distinct, with different search keys, so each possible node value occurs at most once, but we shall see later that it is easy to relax this assumption.

DEFINITION:

A binary tree is a binary search tree (BST) if and only if an inorder traversal of the binary tree results in a sorted sequence. The idea of a binary search tree is that data is stored according to order so that it can be retrieved very efficiently.

PROPERTIES:

•  Every element has a key and no two elements have the same key.
•  The keys in the left subtree are smaller than the key in the root.
•  The keys in the right subtree are larger than the key in the root.
•  The left and right subtrees are also binary search trees.

EXAMPLES:

&

NODES ORDER:

• Each node contains one key (also unique)
• The keys in the left subtree are < (less) than the key in its parent node
• The keys in the right subtree > (greater) than the key in its parent node
• Duplicate node keys are not allowed.

OPERATIONS:

Searching

1. Start at the root node as the current node

2. If the search key‘s value matches the current node‘s key then found a match

3. If the search key‘s value is greater than the current node‘s

a. If the current node has a right child, search right

b. Else, no matching node in the tree

4. If the search key is less than the current node‘s

a. If the current node has a left child, search left

b. Else, no matching node in the tree

Insertion

1. Always insert the new node as a leaf node

2. Start at the root node as the current node

3. If a new node‘s key < current‘s key

a. If the current node has a left child, search left

b. Else add the new node as current‘s left child

4. If new node‘s key > current‘s key

a. If the current node has a right child, search right

b. Else add the new node as current‘s right child

Deletion

Basically, it can be divided into two stages:

•  Search for a node to remove;
•  If the node is found, run the remove algorithm.

1. Node to be removed has no children: The algorithm sets the corresponding link of the parent to NULL and disposes of the node.

2. Node to be removed has one child: It this case, node is cut from the tree and algorithm links single child (with it's subtree ) directly to the parent of the removed node.

REMOVE ALGORITHM:

delete(value v, tree t) {

if ( isEmpty(t) )

error(`Error: given item is not in given tree')

else

if ( v < root(t) ) // delete from left sub-tree

return MakeTree(root(t), delete(v,left(t)), right(t));

else if ( v > root(t) ) // delete from right sub-tree

return MakeTree(root(t), left(t), delete(v,right(t)));

else // the item v to be deleted is root(t)

if ( isEmpty(left(t)) )

return right(t)

elseif ( isEmpty(right(t)) )

return left(t)

else // difficult case with both subtrees non-empty

return MakeTree(smallestNode(right(t)), left(t),

removeSmallestNode(right(t))

}

CHECKING BST CODE PROTOTYPE:

isbst(tree t) {

if ( isEmpty(t) )

return true

else

return ( allsmaller(left(t),root(t)) and isbst(left(t))

and allbigger(right(t),root(t)) and isbst(right(t)) )

} 

allsmaller(tree t, value v) {

if ( isEmpty(t) )

return true

else

return ( (root(t) < v) and allsmaller(left(t),v)

and allsmaller(right(t),v) )

}

allbigger(tree t, value v) {

if ( isEmpty(t) )

return true

else

return ( (root(t) > v) and allbigger(left(t),v)

and allbigger(right(t),v) )

}