It's just binary tree with some logic! Here our tree has some properties like, our root will be greater than everything of it's left and will be less than it's right subtree and so on... So why? What's the point?
Well, here's the thing, it'll let us find either an elelment exist in our tree or not in O(log_2 n) time complexity. Pretty kool, right?
7.4 Find
Before inserting values, let's actually try to find a value exists in our tree or not. We will iterate through our tree to find the location and previous location of whatever we search for. So if our location is NULL we can just go ahead and use that information while inserting.
Here we are passing pointer as a reference! Pretty kool, right? We will be using these values later!
7.5 Insert
In insertion we will simply use the data of above method. And as always if it's NULL we will try to add that node.
void insert(Node *&root, int item) {
Node *location, *previous;
find(root, location, previous, item);
if (location != NULL) return;
if (previous == NULL)
root = new Node(item);
else if (item < previous -> data)
previous -> left = new Node(item);
else
previous -> right = new Node(item);
}
Suppose we have the location of a node and the location of it's parent node and we are gonna delete that node.
7.6 Delete with one child
We will be deleting nodes if any node of our tree has only one child. So we can just go ahead and check either it has a left child or right child and act accordingly.
void delete_with_one_child(Node *&root, Node *&location, Node *&parent) {
Node *child;
if (location -> left != NULL)
child = location -> left;
else if (location -> right != NULL)
child = location -> right;
else
child = NULL;
if (parent != NULL) {
if (location == parent -> left)
parent -> left = child;
else
parent -> right = child;
} else {
root = child;
}
}
But what if we have two child?
7.7 Delete with two child
In this case, things are bit tricky, cause we have to consider which of the successor will take the place of the node that we delete. And actually if we iterate through the right node's left element and so on, we will eventually meet with that guy. Next we can use the above trick to get rid of that alongside joining our new node with parent.
void delete_with_two_children(Node *&root, Node *&location, Node *&parent) {
Node *successor, *parent_successor;
parent_successor = location;
successor = location -> right;
while (successor -> left != NULL) {
parent_successor = successor;
successor = successor -> left;
}
delete_with_one_child(root, successor, parent_successor);
if (parent != NULL) {
if (location == parent -> left)
parent -> left = successor;
else
parent -> right = successor;
} else {
root = successor;
}
successor -> left = location -> left;
successor -> right = location -> right;
}
7.8 Deleting an element
As we have seen in the 7.6 and 7.7, we will be needing address of the node that we want to delete. And here in this step we will work around this. We will use 7.4 to find the address of our node and parent and will try to determine either it has one child or two child!
void delete_node(Node *&root, int item) {
Node *location, *parent;
find(root, location, parent, item);
if (location == NULL) return;
if (location -> left != NULL && location -> right != NULL)
delete_with_two_children(root, location, parent);
else
delete_with_one_child(root, location, parent);
delete location;
}
Wrapping up!
After combining all of the above algorithms here's a full executable code,
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int data) {
this->data = data;
left = NULL;
right = NULL;
}
};
void find(Node *&root, Node *&location, Node *&previous, int item) {
location = root;
previous = NULL;
if (location == NULL) {
return;
}
while (location != NULL) {
if (item == location -> data) {
return;
}
if (item < location -> data) {
previous = location;
location = location -> left;
}
else {
previous = location;
location = location -> right;
}
}
}
void insert(Node *&root, int item) {
Node *location, *previous;
find(root, location, previous, item);
if (location != NULL) return;
if (previous == NULL)
root = new Node(item);
else if (item < previous -> data)
previous -> left = new Node(item);
else
previous -> right = new Node(item);
}
void delete_with_one_child(Node *&root, Node *&location, Node *&parent) {
Node *child;
if (location -> left != NULL)
child = location -> left;
else if (location -> right != NULL)
child = location -> right;
else
child = NULL;
if (parent != NULL) {
if (location == parent -> left)
parent -> left = child;
else
parent -> right = child;
} else {
root = child;
}
}
void delete_with_two_children(Node *&root, Node *&location, Node *&parent) {
Node *successor, *parent_successor;
parent_successor = location;
successor = location -> right;
while (successor -> left != NULL) {
parent_successor = successor;
successor = successor -> left;
}
delete_with_one_child(root, successor, parent_successor);
if (parent != NULL) {
if (location == parent -> left)
parent -> left = successor;
else
parent -> right = successor;
} else {
root = successor;
}
successor -> left = location -> left;
successor -> right = location -> right;
}
void delete_node(Node *&root, int item) {
Node *location, *parent;
find(root, location, parent, item);
if (location == NULL) return;
if (location -> left != NULL && location -> right != NULL)
delete_with_two_children(root, location, parent);
else
delete_with_one_child(root, location, parent);
delete location;
}
void preorder(Node *root) {
if (root == NULL) return;
cout << root -> data << " ";
preorder(root -> left);
preorder(root -> right);
}
void inorder(Node *root) {
if (root == NULL) return;
inorder(root -> left);
cout << root -> data << " ";
inorder(root -> right);
}
void level_order(Node *root) {
if (root == NULL) return;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node *current = q.front();
q.pop();
cout << current -> data << " ";
if (current -> left != NULL) q.push(current -> left);
if (current -> right != NULL) q.push(current -> right);
}
}
int main() {
Node* tree = NULL;
insert(tree, 60);
insert(tree, 25);
insert(tree, 75);
insert(tree, 15);
insert(tree, 50);
insert(tree, 66);
insert(tree, 33);
insert(tree, 44);
cout << "Before Deletion -> \n";
cout << "Preorder -> \n";
preorder(tree);
cout << "\nInorder -> \n";
inorder(tree);
cout << "\nLevel Order -> \n";
delete_node(tree, 25);
cout << "After Deletion -> \n";
cout << "Preorder -> \n";
preorder(tree);
cout << "\nInorder -> \n";
inorder(tree);
cout << "\nLevel Order -> \n";
level_order(tree);
}
