Algorithm Course Preview: Tree Data Structures

devCamp is in the middle of launching an Algorithm Bootcamp course. Where the focus of the course will be on a practical approach to understanding algorithms and data structures. This is a preview of one of the guides from the upcoming course.

In this guide we'll discuss three types of trees from a high level perspective and examine how they can be utilized. And in subsequent guides we'll drill down each of the types in more detail.

There are a large number of tree types, however three types specifically are used the majority of the time (both in real world development and in Computer Science courses). The types are:

• Binary trees
• B-Trees
• Heaps

Binary trees

You don't have to look any further than its name to remember the most important requirement of binary trees. The word binary represents 2. Therefore it's easy to spot a binary tree because it follows the rule that each parent node has no more than 2 child nodes. This means that a binary tree can look like this:

Or like this:

Or even like this:

However it cannot break this 2 child rule. So this would not be a valid binary tree:

We'll spend quite a bit of time on binary trees in the next few guides. Including how to build a tree, add elements to it, and manage them in general. For right now simply remember that a binary tree is a tree where each parent can have no more than two child nodes.

B Trees

When learning about trees one of the most important structures to study is the B-Tree. B-Trees are used extensively when building databases. In fact if you take a look at the schema file in a Ruby on Rails application you'll see that the framework utilizes B-Trees for each database index.

B-Trees are different than binary trees because they allow for a node to have more than 2 children. A visual of a B-Tree could look something like this:

This type of digram is nice because it shows that a parent node can have more than a single child (the boxes represent individual nodes and pointers). However the concept of this type of tree didn't make sense to me until I thought of B-Trees like a file system tree. If I look at the tree of my file system I'll see something like this:

├── ui
│   └── itscaffold
│       ├── Gemfile
│       ├── Gemfile.lock
│       ├── README.md
│       ├── Rakefile
│       ├── app
│       │   ├── assets
│       │   │   ├── images
│       │   │   │   ├── about
│       │   │   │   │   ├── accounting.png
│       │   │   │   │   ├── datamanagement.png
│       │   │   │   │   ├── employeemanagement.png
│       │   │   │   │   ├── enterprise.png
│       │   │   │   │   ├── marketing.png
│       │   │   │   │   └── mobile.png
│       │   │   │   ├── header-bg.jpg
│       │   │   │   ├── header-logo-white.png
│       │   │   │   ├── header-logo.png
│       │   │   │   ├── logos
│       │   │   │   │   ├── aetuts.jpg
│       │   │   │   │   ├── creative-market.jpg
│       │   │   │   │   ├── designmodo.jpg
│       │   │   │   │   ├── envato.jpg
│       │   │   │   │   ├── microlancer.jpg
│       │   │   │   │   ├── themeforest.jpg
│       │   │   │   │   └── wordpress.jpg

If you look at the file system like a sideways B-Tree you'll see how parent nodes (directories) can have multiple nodes (files). We'll walk through how to create a B-Tree in its own guide. At a high level remember that B-Trees are a type of tree data structure that allow for parent nodes to have more than two child nodes. Another important component of B-Trees is that they are self balancing, we will also cover the importance of this feature later on since it deserves its own guide.

Heaps

The third type of tree type is the Heap. Heaps are a specialized subset of binary trees. This means that heaps have the same structure as a binary tree, including the rule that a parent node cannot have more than 2 child nodes.

So what makes the heap tree structure important? A few reasons that we'll dive into later on, however one of the top reason why developers utilize heaps is to build priority queues. A priority queue is like a normal queue, except that it allows for each element to be given a priority. If you remember back to our Disneyland Queue data structure analogy, a priority queue would be like adding the ability to allow single riders or handicap individuals onto a ride ahead of others in line.

We'll walk through how to utilize heaps and priority queues in its own dedicated guide, however at a high level simply remember that a heap is a subset of a binary tree that allows for priority driven behavior.

Summary

You should now have a solid mental model for the types of tree types that can be utilized when managing data, including: binary trees, B-Trees, and Heaps.

Want More?

If you want to learn more about algorithms you can start going through the algorithm course from the syllabus page here.