Chapter 7. Building a Hierarchical Tree Structure

In the previous chapter, we discussed using a string as a non-linear data structure and tried to construct, use, and solve several problems in the string data type. In this chapter, we are going to discuss another non-linear data structure, which is a tree that stores data in a hierarchical form.

In this chapter, we are going to discuss the following topics:

• Introducing the tree data structure
• Understanding the binary search tree
• Balancing the binary search tree
• Implementing the priority queue using a binary heap

Technical requirements

To follow along with this chapter, including the source code, you will require the following:

• A desktop PC or Notebook with Windows, Linux, or macOS
• GNU GCC v5.4.0 or above
• Code Block IDE v17.12 (for Windows and Linux OS) or Code Block IDE v13.12 (for macOS)
• You will find the code files on GitHub at https://github.com/PacktPublishing/CPP-Data-Structures-and-Algorithms

Building a binary tree ADT

A binary tree is a hierarchical data structure whose behavior is similar to a tree, as it contains root and leaves (a node that has no child). The root of a binary tree is the topmost node. Each node can have at most two children, which are referred to as the left child and the right child. A node that has at least one child becomes a parent of its child. A node that has no child is a leaf. Please take a look at the following binary tree:

From the preceding binary tree diagram, we can conclude the following:

• The root of the tree is the node of element 1 since it's the topmost node
• The children of element 1 are element 2 and element 3
• The parent of elements 2 and 3 is 1
• There are four leaves in the tree, and they are element 4, element 5, element 6, and element 7 since they have no child

This hierarchical data structure is usually used to store information that forms a hierarchy, such as a file system of a computer.

To implement the binary in code, we need a data structure...

Building a binary search tree ADT

A binary search tree (BST) is a sorted binary tree, where we can easily search for any key using the binary search algorithm. To sort the BST, it has to have the following properties:

• The node's left subtree contains only a key that's smaller than the node's key
• The node's right subtree contains only a key that's greater than the node's key
• You cannot duplicate the node's key value

By having the preceding properties, we can easily search for a key value as well as find the maximum or minimum key value. Suppose we have the following BST:

As we can see in the preceding tree diagram, it has been sorted since all of the keys in the root's left subtree are smaller than the root's key, and all of the keys in the root's right subtree are greater than the root's key. The preceding BST is a balanced BST since it has a balanced left and right subtree. We also can define the preceding BST as a balanced BST since both the left and right subtrees have an equal height (we...

Building a balanced BST (AVL) ADT

As we discussed earlier in the Building a binary search tree ADT section, it's possible to have a skewed tree (either left or right) and cause the time complexity of several operations to become slow for O(h), where h is the height of the tree. In this section, we are going to discuss a balanced binary search tree to ensure that we won't get a skewed tree. There are several implementations needed to create a balanced BST. However, we will only focus on the AVL tree, which was invented by Adelson-Velskii and Landis in 1962, and is named after the inventors.

To make a balanced BST, we have to know the height of each node in the tree. So, we need to modify the BSTNode class by adding a new property named Height, as follows:

class BSTNode
{
public:
    int Key;
    BSTNode * Left;
    BSTNode * Right;
    BSTNode * Parent;
int Height;
};

This new property is used to track the height of each node. We will also create a new method to fetch the height of a node, which...

Building a binary heap ADT

A binary heap is a completely binary tree that is usually used to implement a priority queue. Please look at the following binary tree which is representing the priority queue:

As we can see, each node has its own key and there's also a number below each node to indicate the priority of the element (in this example, the maximum element has higher priority). The priority queue is usually represented in an array, so we can have the following array as a representation of the preceding priority queue tree:

To create a binary heap in C++, we will have the heapSize variable, which will be increased when an element is inserted and will be decreased when an element is removed. There are four basic operations in a priority queue, and they are as follows:

• IsEmpty() is used to check whether the queue is empty
• Insert(), similar to the Enqueue() operation in a Queue data structure, is used to insert a new element into the queue
• GetMax(), similar to the Peek() operation in a Queue...

Summary

In this chapter, we discussed the hierarchical data structure and stored information in the form of a tree. We started our discussion by creating a tree from several TreeNodes, and then built a binary search tree where we can search for a given key easily. Sometimes, we can have a skewed tree in a binary search tree, and so we build an AVL tree, which can balance all of the elements itself, so that now we can have a balanced binary tree. Another tree data structure implementation is the binary heap, which we used to build a priority queue, where we can access an element based on its priority.

In the next chapter, we are going to discuss how to construct and implement the hash structure in algorithm design.

QA section

• What is the difference between the TreeNode class in a binary tree and the TreeNode class in a binary search tree?
• What are the advantages of the binary search tree over the binary tree?
• How can the AVL tree have a balanced tree?

Further reading

For futher references, please visit these links:

• https://visualgo.net/en/bst
• https://www.geeksforgeeks.org/binary-tree-data-structure/
• https://en.wikipedia.org/wiki/Binary_search_tree
• http://en.cppreference.com/w/cpp/language/range-for
• https://en.wikipedia.org/wiki/Binary_heap
• https://visualgo.net/en/heap
• https://www.geeksforgeeks.org/binary-heap/