Part 4 is here
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
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.
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