Binary Tree Memorandum for Beginners (Part 1)

I wrote a commentary article on binary trees for a certain job, but due to various reasons, it was not used. It's a childish article, but I wrote it at the moment, so please let me have a memorial service here.

All of these articles are called "Digital Series 10 Algorithms and Data Structures that Connect to the Future" (Supervisor: Shojiro Nishio, Authors: Takahiro Hara, Satoshi Mizuta, Takenao Okawa, Publisher: Mitsuaki Nanjo, Publisher: Kyoritsu Shuppan Co., Ltd.) I refer to the book. It is a good book for beginners with abundant illustrations and pseudo-code, so please read it if you are interested.

Although it is labeled as "for beginners", this article is an unfriendly article with no illustrations, so if you really have a refreshing idea of binary trees, you may read it. If you read this article and don't understand what it means, it's not your fault, but the author's fault.

What is a binary tree?

A tree structure is one of the same data structures as a stack or queue. For example, the organizational chart of a company has a fine wooden structure. The positions of the president, design manager, server engineer, etc. are called nodes. The line connecting each node is called an edge. The nodes at both ends of the side are called the parent at the top and the child at the bottom. In other words, the design manager is the parent of the designer, and the designer is the child of the design manager. Like the president, the top node is called the root. A node that has no children, such as a designer or engineer, is called a leaf. A tree structure in which each node has two or less children is called a binary tree. In other words, a binary tree is made up of a combination of nodes and edges.

Implementation example

C++

BinaryTree.cpp

#include <iostream>
using namespace std;

int main()
{
	string binaryTree[7] = {"President", "Design manager", "Engineer manager",
												  "designer", "", "Server engineer", "Infrastructure engineer"};

	//Parent is 0
	cout << binaryTree[0] << endl;
	//The children of the engineer manager (index 2) are server engineers and infrastructure engineers.
	cout << binaryTree[2 * 2 + 1] + ", " + binaryTree[2 * 2 + 2] << endl;
}

Java

BinaryTree.java

public class BinaryTree {
	public static void main(String[] args) {
		String[] binaryTree = {"President", "Design manager", "Engineer manager",
													 "designer", "", "Server engineer", "Infrastructure engineer"};

		//Parent is 0
		System.out.println(binaryTree[0]);
		//The children of the engineer manager (index 2) are server engineers and infrastructure engineers.
		System.out.println(binaryTree[2 * 2 + 1] + ", " + binaryTree[2 * 2 + 2]);
	}
}

Explanation about implementation

Binary trees can be achieved by using arrays. Formally, the root index is set to 0 first. For nodes other than the root, when the parent index is k, the left child index is 2k + 1 and the right child index is 2k + 2. If you have one child, make that child the left child and the right child empty. After assigning an index to each node, it is completed by storing the data of the contact in the array according to the index.

Usage example

The tree structure is a data structure suitable when there is an order relationship such as hierarchy and size between data. Since the data is arranged regularly, you can search quickly if you decide in advance how to arrange it. There are heap trees and binary search trees as binary trees that utilize this property.

Precautions for application

As I mentioned earlier, it works well for ordinal data, but conversely, it is powerless for unordered data. Also, even if there is an order relationship, if the inputs are given in that order, a tree shaped like a list will be created, with only the left or right child. Furthermore, if you use the array implementation described earlier, you will have to allocate memory to empty children, which is wasteful. It is a characteristic of arrays that memory is wasted for sparse data. In other words, the array implementation is suitable for dense dichotomies with no empty children in the middle. A dense binary tree is especially called a complete binary tree. To be precise, a binary tree that has no vacancy at the nodes that are not leaves and all the leaves are left-justified is called a complete binary tree. A binary tree that is not a complete binary tree can be realized using classes to eliminate wasted memory.

Part 2 is here