Binary trees

A binary tree can be defined recursively as

• an empty tree, containing no nodes or
• a node, called the root, usually containing some data, with at most 2 subtrees, each of which is itself a binary tree

Terminology

Node - a part of the tree holding some data

Branches - connections between nodes

Root - the node that has no parent, i.e., is at the top of the tree

Leaf - a node that has no subtrees, i.e., is at the bottom of the tree

Parent - a node that is connected to the root of a subtree

Level - all the nodes that are at the same depth in the tree, i.e., there are the same number of branches to get 'back to' the root, are at the same level. The root is at level 0

Child - the root of a subtree that is connected 'upwards' to its parent

Sibling - the next node at the same level

Binary tree search

Thinking of any particular binary tree, how many searches will it take to find a certain item?

Efficiency

Thinking of any particular binary tree, how many searches will it take to find a certain item (in the best and worst cases) if the tree has n nodes?

Does the number of searches (in both cases) differ depending on whether the item is in the tree or not?

Does the number of searches (in both cases) depend on the structure of the tree?

What is the worst case? What is the best case?

A binary tree has n items in it, and takes s searches (in the worst case) to find an item. If another n items are added to the tree how many searches will it need to find an item (in the worst case) if the tree is perfectly balanced, i.e., each node (apart from the leaf nodes) has two subtrees.

Balance

A perfectly balanced binary tree is one where every node, has 0 or 2 subtrees. The leaves have 0 subtrees, and the 'internal' nodes each have 2.

Stack, queue and list operations

Queue - FIFO Stack - LIFO

Simple graph traversal algorithms

(see: AQA supplementary materials, document called: 'Unit guide: COMP3 - Graph traversals')

A graph traversal algorithm aims to 'explore' every vertex.

If the algorithm is searching for a particular vertex (eg. the exit to a maze) then it considers whether each vertex is the one it is looking for.

After evaluation, if it has not found what it was looking for, the algorithm adds every vertex adjacent to the current one onto a 'list' of vertices to visit next.

The type of structure used to store this 'list' of vertices determines how the algorithm moves through the graph.

• Queue
  • FIFO (first in, first out)
  • ${\displaystyle \implies }$ siblings are processed before their children
  • ${\displaystyle \implies }$ 'Breadth-first traversal'
  • all vertices on the same level are processed before moving to the next level
• Stack
  • LIFO (last in, first out)
  • ${\displaystyle \implies }$ children are processed before the siblings of the current vertex
  • ${\displaystyle \implies }$ 'Depth-first traversal'

These algorithms also have to keep track of the state of each vertex:

• Undiscovered
  • The algorithm has yet to discover this vertex
• Discovered
  • A vertex is discovered once the algorithm has evaluated the vertex, and added its children to the list of vertices to visit. However not all of them have been evaluated yet
• Completely explored/Processed
  • All adjacent vertices have been discovered

Simulations

Simulations model real and imaginary situations. They may be used to test scenarios that wouldn't be feasible in real life for cost or time reasons. Many computer games could be considered simulations.

You should know how to simulate simple queues.