ABSTRACT DATA STRUCTURES | TREES
SECTION 1 | WHAT ARE TREES?
Trees are a visual representation of a hierarchical data structure to show how data is organized. Tree structures are used in many different ways in computer systems, a well known tree structure method is the way your folders are structured on your drive or cloud storage.
In a 'Binary Tree' each point in a tree is called a node. Nodes can have a maximum of 1 link to a parent node(a node above) and a maximum of 2 links down to children nodes(nodes below).
A non-binary tree structure could have multiple nodes branching from a parent node, the same way a folder structure works.
A 'node' is a point in a system, for example this could be a point in a network or a position in an array highlighting, forming or representing a star point, end point, or intersection.
They are used extensively in programming and data structure. Binary trees can help with organizing data for rapid access, such as in binary search trees or heaps, they are also used in algorithms that process trees, like syntax trees in compilers or HTML/XML parsing.
SECTION 2 | PARTS OF A TREE
ROOT: The node at the top of the tree
PARENT: Any node that has a child node below
LEFT-CHILD: The node on the left below a parent
RIGHT-CHILD: The node on the right below a parent
SUBTREE: A branch to the left or right of a parent that has at least one child of its own.
LEAF: The last nodes at the bottom of the tree
SECTION 3 | TYPES OF TREES
There are 3 main types of Binary trees discussed at IB level, Balanced Binary Trees, Unbalanced Binary Trees, Degenerate Trees. Here we take a look at each tree type.
BALANCED BINARY TREES
A balanced binary tree is a binary tree structure in which the left and the right subtrees of every node differ in height by no more than 1.
An example of a balanced binary tree is an AVL tree (named after inventors Adelson-Velsky and Landis). This is a self-balancing binary search tree, meaning it automatically maintains its height as minimal as possible whenever the tree is modified.
USE CASE: Balanced binary trees are very good for "dictionary" problems where the code inserts and looks up items by a key (like a map or a database index in programming), because the balance guarantees that the path to any leaf (which corresponds to a key lookup) is in O(log n), n being the number of nodes.
UNBALANCED BINARY TREES
An unbalanced binary tree is one where the distribution of nodes isn't even, causing the tree to lean to one side. This could be due to the nature of the data inserted into the tree or from deletions that leave one side of the tree sparse.
USE CASE: While unbalanced trees are generally inefficient compared to balanced trees, there can still be use cases for them. For example, if we are certain that our data will always be inserted in a certain order that keeps the tree relatively balanced, we might decide to use an unbalanced tree for simplicity.
DEGENERATE TREES
A degenerate tree is a tree where each parent node has only one associated child node. This effectively makes the tree perform like a linked list data structure.
USE CASE: Degenerate trees aren't typically used on purpose, as they have poor performance for most operations. However, they may result from certain sequences of operations on a binary tree. For example, continually adding nodes to only one side of the tree will result in a degenerate tree. As a linked list, though, they can be used for simple linear traversal.
These are some of the types of binary trees. Each has its own advantages, disadvantages, and specific use cases. It is crucial to use the right type of binary tree to suit your needs for efficient data storage and manipulation.
SECTION 4 | HOW BINARY TREES WORK
This video talks about Full Binary Trees, Complete Binary Trees and Perfect Binary Trees. The video also looks at Balanced Binary Trees, Unbalanced Binary Trees and Degenerate Binary Trees.
Video: CS Rocks: How Binary Trees Work
SECTION 5 | CREATING A TREE FROM A LIST
Here we look at the process of creating an unbalanced binary tree from a list of numbers.
We'll start with the list [5, 2, 7, 1, 4, 6, 9].
Here's the basic idea for creating an unbalanced binary tree: You start with the first number as the root of the tree. Then for each number, you traverse the tree, starting from the root, and place the number in the correct spot. If the number is smaller than the current node, you go left; if it's larger, you go right. You do this until you find an empty spot where you can place your number.
Here's the step-by-step breakdown:
-
Start with an empty tree. Our list of numbers is [5, 2, 7, 1, 4, 6, 8, 9].
-
Take the first number, 5. Since the tree is empty, 5 becomes the root.
-
The next number is 2. 2 is less than 5, so it becomes the left child of 5.
-
The next number is 7. 7 is greater than 5, so it becomes the right child of 5.
-
The next number is 1. Starting at the root, we see that 1 is less than 5, so we go left. Then, 1 is less than 2, so it becomes the left child of 2.
-
The next number is 4. We start at the root. 4 is less than 5, so we go left. Then, 4 is greater than 2, so it becomes the right child of 2.
-
The next number is 6. Starting at the root, 6 is greater than 5, so we go right. Then, 6 is less than 7, so it becomes the left child of 7.
-
Finally, we insert the number 8. Starting at the root, 8 is greater than 5, so we go right. Then, 8 is greater than 7, so it becomes the right child of 7. And then the final 9
So, the final binary tree would look like this:
As you can see, this tree is unbalanced. There are more nodes on the right side of the root node than on the left. Similarly, within the subtree rooted at the node 2, there are more nodes on the right side than on the left.
Note: While the above tree is an unbalanced binary tree, it is not a worst-case scenario. If we had inserted the numbers in a sorted order (either ascending or descending), we would have ended up with a degenerate tree, which would have been the most unbalanced possible tree.
This video is a walk through of creating a tree from a given list. In this video the list is an unsorted list and the Tree produced is an unbalanced Binary Tree.
Video
How to Construct a Binary Search Tree
SECTION 6 | TREE TRAVERSAL
Traversal can be broken up into 2 categories; Depth First and Breadth First.
The depth-first methods are:
Pre-Order: First Visit
In-Order: Second or last visit - whichever comes first
Post-Order: Last visit
The breath-first method is:
Level-order: Traverse the tree from top to bottom and visit left to right : like reading a book.
PRE-ORDER TRAVERSAL
Pre-order traversal is commonly used in algorithms where the operation at a node should be performed before the operations at its children, like when creating a copy of a tree.
1: Visit Node
2: Traverse Left
3: If Null Traverse Right
PRE-ORDER TRAVERSAL: 1, 2, 4, 5, 3, 7
Video
IN-ORDER TRAVERSAL
In-order traversal is often used when you want to retrieve data from a binary search tree in ascending order.
We can think of In-order traversal as visiting the node on the second visit. A leaf node's second visit would be after checking the null value of branches, so it may actually be the first visit however we can still view it as the second visit as it traverses the null value.
1: Traverse Left
2: Visit Node
3: Traverse Right
IN-ORDER TRAVERSAL: 4, 2, 5, 1, 3, 7
Video
POST-ORDER TRAVERSAL
Post order traversal is typically used when the operation at a node depends on the results of the operations at its children, like when deleting a tree.
If we assign a West and East side to the node, then the traversal must reach both the West and East points of the node before visiting. Traversing the north or south of a node does not count as a pass.
1: Traverse Left
2: Traverse Right
3: Visit Node
POST-ORDER TRAVERSAL: 4, 5, 2, 7, 3, 1
Video: Post-order Tree Traversal