A binary search tree is a binary tree that may be empty or non-empty. It must satisfy the following properties:
Each element is distinct
The elements in the left subtree of the root are less than the root
The elements in the right subtree of the root are greater than the root
The left and right subtrees of the root are also binary search trees
Binary search trees produce infix, postfix, and prefix notations with the same properties as a regular binary tree
The infix is the easiest to derive. Why?
Assume that a particular ORDERED Binary Search tree exists which produces the following POSTORDER traversal sequence with 24 nodes:
6 15 10 20 35 27 80 100 89 79 52 140 170 153 101 190 251 210 350 375 400 519 307 172
Write down the corresponding INORDER and PREORDER traversal sequence of this binary tree.
The way that a binary search tree is set up makes processing of the tree easy to implement.
Starting at the root of the tree, compare the data field against the item being searched for:
if the item < data field, go left
if the item > data field, go right
repeat the process until you reach a null pointer or find the item.
ptr = root
found = false
while (ptr is not null AND !found)
if search value < ptr->data
ptr = ptr->leftChild
else if search value > ptr->data
ptr = ptr->rightChild
else
found = true
endwhile
Starting at the root of the tree, compare the data field against the item to insert:
if the item < data field, go left
if the item > data field, go right
repeat the process until you reach a null pointer or find a duplicate item. If you find a duplicate, do not insert. If find a null pointer, insert.
ptr = root
parentPtr = null
found = false
while (ptr is not null AND !found)
parentPtr = ptr
if insert value < ptr->data
ptr = ptr->leftChild
else if insert value > ptr->data
ptr = ptr->rightChild
else
found = true
endwhile
if insert value is found
duplicate item in tree
else
if parentPtr is null
insert as root of tree
else if item < parentPtr->data
insert as parentPtr's left child
else
insert as parentPtr's right child
endif
endif
This is the hardest of the processes to implement.
There are three cases that need to be considered when deleting a node from a binary search tree:
the node to delete is a leaf
the node to delete has one child
the node to delete has two children
Case 1: make the appropriate pointer of the nodes parent null
Case 2: make the appropriate pointer of the nodes parent point to the child
Case 3: the node to be deleted will have its data field replaced by the data field of a chosen node and then the chosen node will be deleted. There are two ways to choose a node:
Inorder successor - smallest value in the node's right subtree
Inorder predecessor - largest value in the node's left subtree
After the successor/predecessor has been copied, it can be treated as either a case 1 or 2 node.
ptr = root
parentPtr = null
found = false
while (ptr is not null AND !found)
if delete value < ptr->data
parentPtr = ptr
ptr = ptr->leftChild
else if delete value > ptr->data
parentPtr = ptr
ptr = ptr->rightChild
else
found = true
endwhile
if delete value is not found
nothing to delete
else
if ptr has two children // case 3
ptrSucc = ptr->right //find the inorder successor
parentPtr = ptr
while ptrSucc has a left child
parentPtr = ptrSucc
ptrSucc = ptrSucc->left
endwhile
ptr->data = ptrSucc->data //node to delete now has succ. value
ptr = ptrSucc
endif
/* below this -- case 1 and 2 are combined */
subtreePtr = ptr->left
if subtreePtr is null
subtreePtr = ptr->right
endif
if parentPtr is null //tree consists of root only
root = subtree
else if parentPtr->left is ptr //if left child is being deleted,
parentPtr->left = subtreePtr //then subtree is new left child
else //right child is being deleted
parentPtr->right = subtreePtr //new right child is subtree
endif
delete ptr
endif
ptrPred = ptr->left parentPtr = ptr while ptrPred has a right child parentPtr = ptrPred ptrPred = ptrPred->right endwhile ptr->data = ptrPred->data //node to delete now has pred. value ptr = ptrPred