Trees (OCR A-Level Computer Science): Revision Notes
Trees
Overview
A tree is a hierarchical data structure consisting of nodes. Trees are used to represent relationships, such as family trees, organisational charts, and file systems. In Computer Science, trees are widely used for efficient data searching, sorting, and hierarchical data representation.
Structure of a Tree
- Node: The fundamental unit of a tree, containing data and references to child nodes.
- Root: The topmost node in the tree.
- Edge: A connection between a parent and a child node.
- Parent: A node that has one or more child nodes.
- Child: A node that has a parent node.
- Leaf: A node with no children.
- Subtree: A smaller tree within a larger tree, consisting of a node and its descendants.
Types of Trees
- Binary Tree: Each node has at most two children, typically referred to as the left and right child.
- Binary Search Tree (BST): A binary tree where the left child contains values less than the parent, and the right child contains values greater than the parent.
- Multi-branch Tree: A tree where nodes can have more than two children.
Use Cases for Trees
- Binary Search Trees: Efficient for searching, insertion, and deletion (O(log n) time complexity in a balanced tree).
- File Systems: Organising files and directories.
- Heaps: Priority queues.
- Trie: Searching words in a dictionary.
Implementing a Tree
Dynamic Implementation Using Linked Nodes
A tree can be implemented dynamically using linked nodes.
Example: Pseudocode for a Binary Tree Node:
CLASS Node
DATA value
POINTER left
POINTER right
CLASS BinaryTree
POINTER root
METHOD Add(value)
IF root IS NULL
root ← NEW Node(value)
ELSE
CALL AddRecursive(root, value)
METHOD AddRecursive(current, value)
IF value < current.value
IF current.left IS NULL
current.left ← NEW Node(value)
ELSE
CALL AddRecursive(current.left, value)
ELSE
IF current.right IS NULL
current.right ← NEW Node(value)
ELSE
CALL AddRecursive(current.right, value)
Static Implementation Using an Array
A binary tree can also be implemented using an array where:
- The root is at index 0.
- The left child of a node at index i is at 2*i + 1.
- The right child is at 2*i + 2.
Tree Traversals
Depth-First Traversal (Post-Order)
In post-order traversal, the nodes are visited in this order:
Left Subtree → Right Subtree → Root
Example Post-Order Traversal:
Given Tree:
A
/ \\
B C
/ \\
D E
Post-Order: D → E → B → C → A
Pseudocode for Post-Order Traversal:
METHOD PostOrder(node)
IF node IS NOT NULL
CALL PostOrder(node.left)
CALL PostOrder(node.right)
OUTPUT node.value
Breadth-First Traversal
Also known as Level-Order Traversal, nodes are visited level by level, from left to right.
Example Breadth-First Traversal:
Given Tree:
A
/ \\
B C
/ \\
D E
Breadth-First: A → B → C → D → E
Pseudocode for Breadth-First Traversal:
METHOD BreadthFirst(root)
INITIALISE queue
ENQUEUE root
WHILE queue IS NOT EMPTY
current ← DEQUEUE queue
OUTPUT current.value
IF current.left IS NOT NULL
ENQUEUE current.left
IF current.right IS NOT NULL
ENQUEUE current.right
Adding and Removing Nodes in a Binary Search Tree
Adding a Node:
1. Start at the root. 2. Traverse left if the value is smaller or right if it is larger. 3. Insert the node at the appropriate leaf position.
Removing a Node:
1. If the node has no children: Remove it directly. 2. If the node has one child: Replace it with its child. 3. If the node has two children: Replace it with the in-order successor (smallest value in the right subtree).
Note Summary
Common Mistakes
- Incorrect Traversal Order: Mixing up the order of operations in depth-first traversals (e.g., performing in-order instead of post-order).
- Unbalanced Trees: Not considering balancing techniques for binary search trees, which can degrade performance to O(n).
- Improper Index Calculation in Arrays: Miscalculating the left or right child index in static implementations.
- Null Pointer Errors: Forgetting to check if a node is null before accessing its children.
Key Takeaways
- Trees are hierarchical data structures, with binary trees and multi-branch trees being common types.
- Depth-first (Post-Order) and Breadth-First Traversals are essential for exploring and processing tree nodes.
- Trees can be dynamically implemented using linked nodes or statically using arrays.
- Properly manage insertion and deletion in Binary Search Trees to maintain their efficiency.