A-level Computer Science revision · Data structures and algorithms

Graphs, trees and hash tables

The idea

A graph has nodes connected by edges, which may be directed or weighted. A tree is a connected graph with no cycles and a root. In a binary search tree, each node's left subtree holds smaller values and right subtree larger ones. A hash table uses a hash function to map keys to positions, giving fast lookup; collisions are handled by chaining or open addressing.

  1. BST insert: go left if smaller, right if larger.
  2. Hash table: position = hash(key).
  3. Collisions: chaining (lists) or linear probing.

Watch out A collision is when two keys hash to the same position; it must be resolved.

See it worked

Worked example

Insert 50, 30, 70, 20 into an empty BST. Where is 20?

  1. 50 is the root.
  2. 30 < 50: left child.
  3. 20 < 50 and 20 < 30: left child of 30.

Answer Left child of 30

Your turn

Question 12 marks

A hash function is key MOD 10. At which index is key 47 stored?

Question 21 mark

What is a collision in a hash table?

Choose one
Question 31 mark

Which structure has no cycles and a single root?

Choose one

A-level Computer Science Pro, OCR H446

A-level Computer Science Pro

£119 once

Price rises to £199 on 1 January. Save £80 by joining before then.

At least 12 months of access

By paying you agree to our Terms and get access straight away, which ends your 14-day cancellation right.

No VAT is charged.

Independent practice for OCR A-level Computer Science (H446), not endorsed by OCR.

Privacy · Terms