Binary Search Trees
Computer Science: OCR A Level, topic 4.2.8
Binary Search Trees
A binary search tree is a tree data structure used for efficient searching of data.
Binary search trees
- Binary search trees share the same properties as trees, with the exception that each node can have no more than two ‘child’ nodes.
- Binary search trees are very quick to search.
Storing data
- After storing the first piece of data in the root node:
- The second entry is stored in a child node to the left of the root if it has a lesser value.
- The second entry is stored in a child node to the right if it has a greater value.
Example
- The procedure for storing ‘Tiger’, ‘Zebra’, ‘Lion’, ‘Gazelle’ and ‘Rhino’ in the order given is as follows:
- 'Tiger’ takes the root node.
- ‘Zebra’ is greater than ‘Tiger’ alphabetically, so is stored as a child node to the right of the root.
Step 2
- ‘Lion’ comes before ‘Tiger’ and so is stored as a child node to the left of the root.
Step 3
- ‘Gazelle’ comes before ‘Tiger’ and before ‘Lion’, so is stored as a left child to the ‘Lion’ node.
- ‘Rhino’ also comes before ‘Tiger’, but after ‘Lion’ so is stored on the right of this node.