[JAVA] Binary tree memorandum for beginners (Part 5 Binary search tree)

Part 4 is here

Binary search tree

This time, I will explain about the binary search tree. Again, the structure is simple: the parent data is always larger than the left child's data, and the right child's data is always larger than the parent's data. This is not always a complete binary tree, so it is achieved using classes.

C++

BST.cpp


#include <iostream>
using namespace std;

class BST
{
public:
	friend class Main;
	int value;
	BST *left;
	BST *right;

	BST(int);
	~BST();
};

void inorder(BST *);
BST *insertNode(BST *, int);
BST *deleteNode(BST *, int);
BST *deleteNodeEl(BST *, BST *, BST *, bool);

BST::BST(int value):value(value), left(0), right(0){}

BST::~BST()
{
	delete left;
	delete right;
}

void inorder(BST *root)
{
	if (root->left != 0) {
		inorder(root->left);
	}
	cout << root->value << " ";
	if (root->right != 0) {
		inorder(root->right);
	}

	return;
}

//A function that inserts a new node into a binary search tree
//Returns BST after insertion
BST *insertNode(BST *root, int value)
{
  //Do nothing if there is already value
	if (root->value == value) {
		return root;
	}

  //If the current position is greater than value
	else if (root->value > value) {
    //If there is no child on the left
		if (root->left == 0) {
			root->left = new BST(value);
		}
    //If you have a child on the left
		else {
			root->left = insertNode(root->left, value);
		}
	}

  //If the current position is greater than value
	else {
    //If there is no right child
		if (root->right == 0) {
			root->right = new BST(value);
		}
    //If you have the right child
		else {
			root->right = insertNode(root->right, value);
		}
	}

	return root;
}

//A function that deletes nodes that have value in the data
//Returns the deleted BST
BST *deleteNode(BST *root, int value)
{
	BST *parent = 0;
	BST *present = root;
	bool directionIsLeft = false;

	while (present != 0) {
		//When the data at the current position is larger than the value
		if (present->value > value) {
			parent = present;
			directionIsLeft = true;
			present = present->left;
		}
		//When value is larger than the data at the current position
		else if (present->value < value) {
			parent = present;
			directionIsLeft = false;
			present = present->right;
		}
		//When value and current position data match
		else {
			//At least one has no children
			if (present->left == 0 || present->right == 0) {
				return deleteNodeEl(root, present, parent, directionIsLeft);
			}
			//If you have both children
			else {
				BST *right = present->right;
				parent = present;
				directionIsLeft = false;

				//Find the minimum value below the right child
				while (right->left != 0) {
					parent = right;
					right = right->left;
					directionIsLeft = true;
				}

				//At the time of exiting the previous while, right indicates the node with the minimum value below the right child.
				//Exchange present and right data
				present->value = right->value;
				right->value = value;
				return deleteNodeEl(root, right, parent, directionIsLeft);
			}
		}
	}

	return root;
}

//A function that reconstructs a binary search tree after deleting a present when there are one or less children
//Returns the reconstructed BST
BST *deleteNodeEl(BST *root, BST *present, BST *parent, bool directionIsLeft)
{
	//If you have no children
	if (present->left == 0 && present->right == 0) {
		//If the current position is the root
		if (parent == 0) {
			delete present;
			return NULL;
		}
		//If the current position is not the root
		else {
			if (directionIsLeft) {
				parent->left = 0;
			}
			else {
				parent->right = 0;
			}
			delete present;
			return root;
		}
	}

	//If you have only one child
	else if (present->left == 0 || present->right == 0) {
		//If you have the right child
		if (present->right != 0) {
			//If the current position is the root
			if (parent == 0) {
				BST *right = present->right;
				delete present;
				return right;
			}
			//If the current position is not the root
			else {
				if (directionIsLeft) {
					parent->left = present->right;
				}
				else {
					parent->right = present->right;
				}
				delete present;
				return root;
			}
		}

		//If you have a child on the left
		else {
			//If the current position is the root
			if (parent == 0) {
				BST *left = present->left;
				delete present;
				return left;
			}
			//If the current position is not the root
			else {
				if (directionIsLeft) {
					parent->left = present->left;
				}
				else {
					parent->right = present->left;
				}
				delete present;
				return root;
			}
		}
	}

	delete present;
	return root;
}

int main()
{
	BST *root = new BST(20);
	root = insertNode(root, 10);
	root = insertNode(root, 26);
	root = insertNode(root, 5);
	root = insertNode(root, 14);
	root = insertNode(root, 23);
	root = insertNode(root, 25);

	//Duplicate insertion is not allowed
	root = insertNode(root, 25);
	inorder(root);
	cout << endl;

	cout << "10: " << boolalpha << searchNode(root, 10) << endl;
	cout << "23: " << boolalpha << searchNode(root, 23) << endl;

	//You can't search for what you don't have
	cout << "15: " << boolalpha << searchNode(root, 15) << endl;

	root = deleteNode(root, 25);
	root = deleteNode(root, 14);

	//You can't delete what you don't have
	root = deleteNode(root, 14);
	inorder(root);
	cout << endl;
}

Java

BST.java


public class BST {
	int value;
	BST left;
	BST right;

	BST(int value) {
		this.value = value;
		this.left = null;
		this.right = null;
	}

	public static void inorder(BST root) {
		if (root.left != null) {
			inorder(root.left);
		}
		System.out.print(root.value + " ");
		if (root.right != null) {
			inorder(root.right);
		}

		return;
	}

	//A function that inserts a new node into a binary search tree
	//Returns BST after insertion
	public static BST insertNode(BST root, int value) {
		//Do nothing if there is already value
		if (root.value == value) {
			return root;
		}

		//If the current position is greater than value
		else if (root.value > value) {
			//If there is no child on the left
			if (root.left == null) {
				root.left = new BST(value);
			}
			//If you have a child on the left
			else {
				root.left = insertNode(root.left, value);
			}
		}

		//If the current position is greater than value
		else {
			//If there is no right child
			if (root.right == null) {
				root.right = new BST(value);
			}
			//If you have the right child
			else {
				root.right = insertNode(root.right, value);
			}
		}

		return root;
	}

	//A function that deletes nodes that have value in the data
	//Returns the deleted BST
	public static BST deleteNode(BST root, int value) {
		BST parent = null;
		BST present = root;
		boolean directionIsLeft = false;

		while (present != null) {
			//When the data at the current position is larger than the value
			if (present.value > value) {
				parent = present;
				directionIsLeft = true;
				present = present.left;
			}
			//When value is larger than the data at the current position
			else if (present.value < value) {
				parent = present;
				directionIsLeft = false;
				present = present.right;
			}
			//When value and current position data match
			else {
				//At least one has no children
				if (present.left == null || present.right == null) {
					return deleteNodeEl(root, present, parent, directionIsLeft);
				}
				//If you have both children
				else {
					BST right = present.right;
					parent = present;
					directionIsLeft = false;

					//Find the minimum value below the right child
					while (right.left != null) {
						parent = right;
						right = right.left;
						directionIsLeft = true;
					}

					//At the time of exiting the previous while, right indicates the node with the minimum value below the right child.
					//Exchange present and right data
					present.value = right.value;
					right.value = value;
					return deleteNodeEl(root, right, parent, directionIsLeft);
				}
			}
		}

		return root;
	}

	//A function that reconstructs a binary search tree after deleting a present when there are one or less children
	//Returns the reconstructed BST
	public static BST deleteNodeEl(BST root, BST present, BST parent, boolean directionIsLeft) {
		//If you have no children
		if (present.left == null && present.right == null) {
			//If the current position is the root
			if (parent == null) {
				return null;
			}
			//If the current position is not the root
			else {
				if (directionIsLeft) {
					parent.left = null;
				}
				else {
					parent.right = null;
				}
				return root;
			}
		}

		//If you have only one child
		else if (present.left == null || present.right == null) {
			//If you have the right child
			if (present.right != null) {
				//If the current position is the root
				if (parent == null) {
					return present.right;
				}
				//If the current position is not the root
				else {
					if (directionIsLeft) {
						parent.left = present.right;
					}
					else {
						parent.right = present.right;
					}
					return root;
				}
			}

			//If you have a child on the left
			else {
				//If the current position is the root
				if (parent == null) {
					return present.left;
				}
				//If the current position is not the root
				else {
					if (directionIsLeft) {
						parent.left = present.left;
					}
					else {
						parent.right = present.left;
					}
					return root;
				}
			}
		}

		return root;
	}

	public static void main(String[] args) {
		BST root = new BST(20);
		root = insertNode(root, 10);
		root = insertNode(root, 26);
		root = insertNode(root, 5);
		root = insertNode(root, 14);
		root = insertNode(root, 23);
		root = insertNode(root, 25);

		//Duplicate insertion is not allowed
		root = insertNode(root, 25);
		inorder(root);
		System.out.println();

		System.out.println("10: " + searchNode(root, 10));
		System.out.println("23: " + searchNode(root, 23));

		//You can't search for what you don't have
		System.out.println("15: " + searchNode(root, 15));

		root = deleteNode(root, 25);
		root = deleteNode(root, 14);

		//You can't delete what you don't have
		root = deleteNode(root, 14);
		inorder(root);
		System.out.println();
	}
}

The execution result is as follows.

5 10 14 20 23 25 26
10: true
23: true
15: false
5 10 20 23 26

Commentary

The following explanations are based on Java programs. The following functions are implemented in the above program.

--void inorder (BST root): A function that displays a binary search tree in the order of passage. --BST insertNode (BST root, int value): A function that inserts a new node with value as data into the binary search tree. --BST deleteNode (BST root, int value): A function that deletes a node that has value as data from the binary search tree. --BST deleteNodeEl (BST root, BST present, BST parent, boolean directionIsLeft): A function that reconstructs a binary search tree when there is one or less children.

The insertNode function first compares the data at the current position with the value. If they are equal, they return without creating a new node. If the data at the current position is greater than the value, move the current position to the child on the left. If value is greater than the data at the current position, move the current position to the right child. Repeat the previous operation until there is no destination. When there is no destination to go to, create a new node with value as data, and the insertion is completed.

The searchNode function behaves similarly to the insertNode function I mentioned earlier. First, compare the current position data with the value, and if the current position data is larger than the value, move the current position to the left child. If value is greater than the data at the current position, move the current position to the right child. Repeat the previous operation until you reach a node with data equal to value. When the target node is found, true is returned, and if the leaf is reached without being found, false is returned and the search is completed.

The deleteNode function is also very similar to the searchNode and insertNode functions at first. If the data at the current position is greater than the value, move the current position to the child on the left. If value is greater than the data at the current position, move the current position to the right child. Repeat the previous operation until you reach a node with data equal to value. When you find the node you want, delete it. However, if you simply erase it, even the child of the node at the current position will be erased. Therefore, it is necessary to recreate the area below the node at the current position. First, find out if the node at the current position has left and right children. If you have only one child, just move that child to its current position and you're done. If you don't have either, simply erase the node at your current location and you're done. If you have both children, find the node with the smallest data below the right child and exchange the data at that node with the data at the current position. After that, recreate the bottom from the exchanged node and you're done.

Finally

That is all for the article about the binary tree that I wanted to memorialize. Thank you for reading this far. I hope this article will help you in your studies.

Recommended Posts

Binary tree memorandum for beginners (Part 5 Binary search tree)
Binary tree memorandum for beginners (Part 2 Search for binary trees)
Binary Tree Memorandum for Beginners (Part 1)
Binary tree memorandum for beginners (Part 4 Binary heap)
Binary tree memorandum for beginners (Part 3 Realization using class)
A memorandum for android application development beginners
CI / CD practice for beginners --Part2 --CI / CD tool construction
CI / CD practice for beginners --Part1 --Environment construction
Binary search method
[For Rails beginners] Implemented multiple search function without Gem
CI / CD practice for beginners --Part3 --Preparation for development project
Scraping for beginners (Ruby)
[Ruby] Searching for elements in an array using binary search
Tutorial to create a blog with Rails for beginners Part 1
Tutorial to create a blog with Rails for beginners Part 0