Welcome to the World of Trees!
In this chapter, we are going to explore Tree Algorithms. While "trees" might make you think of the ones in a park, in Computer Science, they are one of the most powerful ways to organize data. Whether you are searching for a file on your computer or looking up a word in a digital dictionary, there is likely a tree algorithm working behind the scenes! By the end of these notes, you’ll understand how these structures work and how to "walk" through them like a pro.
1. What is a Tree?
Before we look at algorithms, let’s quickly recap what a tree is. A Tree is a data structure that looks like an upside-down real tree. It starts at a single point and branches out.
Key Terms to Remember:
Node: An individual element in the tree (usually containing data like a number or name).
Root: The very top node of the tree. Every tree has exactly one root.
Edge: The lines or links that connect nodes together.
Parent: A node that has links to nodes below it.
Child: A node that has a link coming from a node above it.
Leaf: A node that has no children (the very "end" of a branch).
Quick Review: Every node (except the root) has exactly one parent, but a parent can have many children!
2. Binary Search Trees (BST)
A Binary Tree is a special type of tree where each node can have a maximum of two children (often called the Left Child and the Right Child).
A Binary Search Tree (BST) adds one very important rule to help us find data quickly:
1. Data smaller than the parent goes to the Left.
2. Data larger than the parent goes to the Right.
Why is this useful?
Because of this "Left = Smaller, Right = Larger" rule, searching for a value is incredibly fast. Instead of looking at every single item (like in a list), we can discard half the tree every time we move down a level. The time efficiency for searching a balanced BST is usually \( O(\log n) \).
Key Takeaway: A BST is designed for speed. It turns a long search into a series of simple "Left or Right?" decisions.
3. Tree Traversal Algorithms
Traversal is just a fancy word for visiting every node in the tree in a specific order. In the Oxford AQA 9645 syllabus, you need to know three "Depth-First" methods. Don't worry if the names sound similar; we have a trick to keep them straight!
Method 1: Pre-order Traversal
In Pre-order, we visit the root before we visit the children.
Order: Root \(\rightarrow\) Left \(\rightarrow\) Right
Used for: Making a copy of a tree or showing the structure of a directory.
Method 2: In-order Traversal
In In-order, we visit the root between the left and right children.
Order: Left \(\rightarrow\) Root \(\rightarrow\) Right
Amazing Fact: If you perform an In-order traversal on a Binary Search Tree, you will visit the nodes in perfect numerical or alphabetical order!
Method 3: Post-order Traversal
In Post-order, we visit the root after we have visited all its children.
Order: Left \(\rightarrow\) Right \(\rightarrow\) Root
Used for: Deleting a tree (you delete the children before the parent) or evaluating mathematical expression trees.
Memory Trick - "The Root Rule":
- Pre means "Before" \(\rightarrow\) Root is First.
- In means "Middle" \(\rightarrow\) Root is in the Middle.
- Post means "After" \(\rightarrow\) Root is Last.
4. The "Dot Trick" for Traversals
If you are asked to trace a traversal in an exam, use this "Secret Method." It works every time!
Step 1: Draw a tiny dot on each node in your tree.
- For Pre-order, put the dot on the Left side of the node.
- For In-order, put the dot on the Bottom of the node.
- For Post-order, put the dot on the Right side of the node.
Step 2: Imagine a pencil starting at the left of the Root. Draw a continuous line that "hugs" the outside of the tree (like a person walking around the edges).
Step 3: Every time your line passes a dot, write down that node's value. The order you write them in is your answer!
Quick Review: This physical "outline" method is the safest way to ensure you don't skip a node or get the order mixed up.
5. Adding a Node to a BST
To add a new piece of data to a Binary Search Tree, we follow the same logic we use for searching. We start at the root and compare our new value to the current node.
Step-by-Step Process:
1. Is the tree empty? If yes, the new value becomes the Root.
2. If not, compare the new value to the current node.
3. Is it smaller? Move to the Left child.
4. Is it larger? Move to the Right child.
5. Repeat this until you reach an empty spot (an "edge").
6. Place your new node there.
Common Mistake: Students sometimes try to "rearrange" the tree when adding a node. Don't do that! A new node is always added as a new "Leaf" node at the end of a branch.
Summary: Key Points for the Exam
Structure: Trees consist of Nodes and Edges. The top is the Root; the ends are Leaves.
BST Rule: Left child \( < \) Parent node; Right child \( > \) Parent node.
Traversals:
- Pre-order: Root, Left, Right (Copying)
- In-order: Left, Root, Right (Sorting)
- Post-order: Left, Right, Root (Deleting)
Efficiency: Searching a BST is much faster than a linear search, with a complexity of \( O(\log n) \) if the tree is balanced.
Don't worry if these traversals feel a bit confusing at first! Try drawing a small tree with 3 nodes (numbers 10, 5, and 15) and practice the "Dot Trick." Once you've done it twice, it will feel like second nature!