Binary Search Trees (OCR A Level Computer Science)

Binary Search Trees

What is a Binary Search Tree?

• A binary search tree is a rooted tree where the nodes of the tree are ordered

• It is ordered to optimise searching

• If the order is ascending, the nodes on the left of the subtree have values that are lower than the root node, the nodes to the right have a higher value than the root node

How do you Insert a value in a Binary Search Tree?

• To insert the value '2' into the binary tree above we need to compare the item to the nodes in the tree 

1. Compare 2 to 10; 2 is smaller than 10, so you go down to the left child

2. Compare 2 to 7; 2 is smaller than 7 so you go down to the left child

3. Compare 2 to 1; 2 is higher than 1 so you go down to the right and add as a child node of 1

Removing Data from a Binary Search Tree

How do you delete data from a Binary Search Tree?

To delete a node from the Binary Search Tree then there are 3 possibilities:

1. The Node is a Leaf Node

• If the node to be deleted is a leaf node, then we can directly delete this node as it has no child nodes. Node 4 does not have any child nodes so it can be deleted straight away

2. The Node has only 1 child

• If the node to be deleted has 1 child, then we copy the value of the child in the node and then delete the node. In the diagram, '2' has been replaced by '4', which was its child node originally

3. The Node has 2 children

• If the node to be deleted has 2 children, then we replace the node with the in-order successor of the node or simply the minimum node in the right subtree if the right subtree of the node is not empty. We then replace the node with this minimum node and delete the node