Introduction

In the previous chapter, we implemented different types of linear data structures to store and manage data in a linear fashion. In linear structures, we can traverse in, at most, two directions – forward or backward. However, the scope of these structures is very limited, and they can't be used to solve advanced problems. In this chapter, we'll explore a more advanced class of problems. We will see that the solutions we implemented previously are not good enough to be used directly. Due to this, we'll expand upon those data structures to make more complex structures that can be used to represent non-linear data.

After looking at these problems, we'll discuss basic solutions using the tree data structure. We'll implement different types of trees to solve different kinds of problems. After that, we'll have a look at a special type of tree called a heap, as well as its possible implementation and applications. Following that, we'll look...

Non-Linear Problems

Two main categories of situations that cannot be represented with the help of linear data structures are hierarchical problems and cyclic dependencies. Let's take a closer look at these cases.

Hierarchical Problems

Let's look at a couple of examples that inherently have hierarchical properties. The following is the structure of an organization:

Figure 2.1: Organization structure

As we can see, the CEO is the head of the company and manages the Deputy Director. The Deputy Director leads three other officers, and so on.

The data is inherently hierarchical in nature. This type of data is difficult to manage using simple arrays, vectors, or linked lists. To solidify our understanding, let's look at another use case; that is, a university course's structure, as shown in the following figure:

Figure 2.2: Course hierarchy in a university course structure

The preceding figure shows the course dependencies for some courses...

Tree – It's Upside Down!

As we discussed in the previous section, a tree is nothing but some objects or nodes connected to other nodes via a relationship that results in some sort of hierarchy. If we were to show this hierarchy in a graphical way, it would look like a tree, while the different edges would look like its branches. The main node, which is not dependent on any other node, is also known as a root node and is usually represented at the top. So, unlike an actual tree, this tree is upside down, with the root at its top!

Let's try to construct a structure for a very basic version of an organizational hierarchy.

Exercise 7: Creating an Organizational Structure

In this exercise, we will implement a basic version of the organizational tree we saw in the introduction to this chapter. Let's get started:

1. First, let's include the required headers:

   #include <iostream>

   #include <queue>

2. For simplicity, we'll assume that any person can have, at...

Variants of Trees

In the previous exercises, we've mainly looked at the binary tree, which is one of the most common kinds of trees. In a binary tree, each node can have two child nodes at most. However, a plain binary tree doesn't always serve this purpose. Next, we'll look at a more specialized version of the binary tree, called a binary search tree.

Binary Search Tree

A binary search tree (BST) is a popular version of the binary tree. BST is nothing but a binary tree with the following properties:

• Value of the parent node ≥ value of the left child
• Value of the parent node ≤ value of the right child

In short, left child ≤ parent ≤ right child.

This leads us to an interesting feature. At any point in time, we can always say that all the elements that are less than or equal to the parent node will be on the left side, while those greater than or equal to the parent node will be on the right side. So, the problem of searching an element keeps...

Heaps

In the previous chapter, we had a brief look at heaps and how C++ provides heaps via STL. In this chapter, we'll take a deeper look at heaps. Just to recap, the following are the intended time complexities:

• O(1): Immediate access to the max element
• O(log n): Insertion of any element
• O(log n): Deletion of the max element

To achieve O(log n) insertion/deletion, we'll use a tree to store data. But in this case, we'll 'use a complete tree. A complete tree is defined as a tree where nodes at all the levels except the last one have two children, and the last level has as many of the elements on the left side as possible. For example, consider the two trees shown in the following figure:

Figure 2.14: Complete versus non-complete tree

Thus, a complete tree can be constructed by inserting elements in the last level, as long as there's enough space there. If not, we will insert them at the leftmost position on the new level. This gives...

Graphs

Although a tree is a pretty good way to represent hierarchical data, we can't represent circular or cyclic dependencies in a tree because we always have a single and unique path to go from one node to another. However, there are more complex scenarios that have a cyclic structure inherently. For example, consider a road network. There can be multiple ways to go from one place (places can be represented as nodes) to another. Such a set of scenarios can be better represented using graphs.

Unlike a tree, a graph has to store data for the nodes, as well as for the edges between the nodes. For example, in any road network, for each node (place), we have to store the information about which other nodes (places) it connects to. This way, we can form a graph with all the required nodes and edges. This is called an unweighted graph. We can add weights, or more information, to each of the edges. For our road network example, we can add the distance of each edge (path) from one node (place...

Summary

In this chapter, we looked at a more advanced class of problems compared to the previous chapter, which helped us to describe a wider range of real-world scenarios. We looked at and implemented two major data structures – trees and graphs. We also looked at various types of trees that we can use in different situations. Then, we looked at different ways of representing data programmatically for these structures. With the help of this chapter, you should be able to apply these techniques to solve real-world problems of similar kinds.

Now that we've looked at linear and non-linear data structures, in the next chapter, we'll look at a very specific but widely used concept called lookup, where the goal is to store values in a container so that searching is super fast. We will also look at the fundamental idea behind hashing and how can we implement such a container.