Binary Max Heap Tree Node Deletion
Here given code implementation process.
/*
C++ program
Binary Max Heap Tree Node Deletion
*/
//Binary max heap node
#include<iostream>
using namespace std;
class Node {
public:
Node *left;
Node *right;
int key;
Node(int value) {
this->key = value;
this->left = NULL;
this->right = NULL;
}
};
class MaxHeap {
public:
//This is use to store information of number of nodes in Max heap
int size;
Node *root;
MaxHeap() {
this->root = NULL;
this->size = 0;
}
//Get height of insert new node
int tree_height() {
int i = 1;
int sum = 0;
while (this->size > sum + (1 << i)) {
sum += (1 << i);
i++;
}
return i;
}
//interchange the two node value
void swap_node(Node *first, Node *second) {
int temp = first->key;
first->key = second->key;
second->key = temp;
}
//Arrange node key
void arrange_node(Node *head) {
if (head->left != NULL &&
head->left->key > head->key) {
this->swap_node(head, head->left);
}
if (head->right != NULL &&
head->right->key > head->key) {
this->swap_node(head, head->right);
}
}
bool add_node(Node *head, int height, int level, int value) {
if (level >= height) {
return false;
}
if (head != NULL) {
if (level - 1 == height &&
head->left == NULL ||
head->right == NULL) {
if (head->left == NULL) {
head->left = new Node(value);
} else {
head->right = new Node(value);
}
this->arrange_node(head);
return true;
}
if (this->add_node(head->left, height, level + 1, value) ||
this->add_node(head->right, height, level + 1, value)) {
//Check effect of new inserted node
this->arrange_node(head);
return true;
}
}
return false;
}
//Handles the request to new inserting node
void insert(int value) {
if (this->root == NULL) {
this->root = new Node(value);
} else
if (this->root->left == NULL) {
this->root->left = new Node(value);
this->arrange_node(this->root);
} else
if (this->root->right == NULL) {
this->root->right = new Node(value);
this->arrange_node(this->root);
} else {
int height = this->tree_height();
this->add_node(this->root, height, 0, value);
}
this->size++;
}
void preorder(Node *head) {
if (head != NULL) {
cout << " " << head->key;
this->preorder(head->left);
this->preorder(head->right);
}
}
Node *node_parent(Node *head, int value) {
if (head != NULL) {
if (head->left != NULL &&
head->left->key == value ||
head->right != NULL &&
head->right->key == value) {
return head;
}
Node *element = this->node_parent(head->left, value);
if (element == NULL) {
element = this->node_parent(head->right, value);
}
return element;
}
return head;
}
//Find last node of tree
Node *tree_last_node(Node *head, int height, int level) {
if (head != NULL) {
if (level == height - 1 &&
(head->left != NULL ||
head->right != NULL)) {
return head;
}
Node *element = this->tree_last_node(head->right, height, level + 1);
if (element == NULL) {
element = this->tree_last_node(head->left, height, level + 1);
}
return element;
}
return head;
}
bool is_max_heap(Node *head) {
if ((head->left != NULL &&
head->left->key > head->key) ||
(head->right != NULL &&
head->right->key > head->key)) {
return false;
}
return true;
}
void updateDeletion(Node *find_node) {
//Find the new changes to make new max heap
//O(long h)
while (find_node != NULL) {
//Check max heap properties
if (this->is_max_heap(find_node) == false) {
//fail max heap
if (find_node->left != NULL &&
find_node->right != NULL) {
//Repace data with maximum value
if (find_node->left->key > find_node->right->key) {
this->swap_node(find_node, find_node->left);
find_node = find_node->left;
} else {
this->swap_node(find_node, find_node->right);
find_node = find_node->right;
}
} else
if (find_node->right != NULL) {
this->swap_node(find_node, find_node->right);
find_node = find_node->right;
} else {
this->swap_node(find_node, find_node->left);
find_node = find_node->left;
}
} else {
break;
}
}
}
void delete_node(int value) {
if (this->root != NULL) {
Node *find_node = NULL;
Node *last_root = NULL;
if (this->root->key == value) {
if (this->root->left == NULL &&
this->root->right == NULL) {
//Delete root node
this->root = NULL;
} else
if (this->root->key == value &&
this->root->right == NULL) {
//Only two node in max heap
find_node = this->root;
this->root = this->root->left;
find_node = NULL;
} else {
//Find the max height by using tree node size
int height = this->tree_height();
if ((1 << height) - 1 == this->size) {
//in case given height is a perfect of all leaf
height--;
}
//Find parent of a last node of tree
last_root = this->tree_last_node(this->root, height, 0);
if (last_root != NULL) {
//updtae key value
if (last_root->right != NULL) {
this->root->key = last_root->right->key;
//remove last node
last_root->right = NULL;
} else {
this->root->key = last_root->left->key;
//remove last node
last_root->left = NULL;
}
this->updateDeletion(this->root);
}
}
cout << "\nDelete Node key : " << value << "\n";
this->preorder(this->root);
//modify tree node size
this->size--;
} else {
//When root node is not a part of delete node
//Find parent of a delete node key
find_node = this->node_parent(this->root, value);
if (find_node == NULL) {
cout << "\nDelete key " << value << " not exist ";
} else {
//Find the max height by using tree node size
int height = this->tree_height();
if ((1 << height) - 1 == this->size) {
//In case given height is a same of all leaf
height--;
}
//Find parent of a last node of tree
last_root = this->tree_last_node(this->root, height, 0);
if (last_root != NULL) {
if (last_root == find_node) {
//When delete last node
if (last_root->right != NULL &&
last_root->right->key == value) {
last_root->right = NULL;
} else
if (last_root->left != NULL &&
last_root->left->key == value) {
if (last_root->right != NULL) {
this->swap_node(last_root->right, last_root->left);
last_root->right = NULL;
} else {
last_root->left = NULL;
}
}
} else {
//Get actual delete node location
if (find_node->right != NULL &&
find_node->right->key == value) {
find_node = find_node->right;
} else {
find_node = find_node->left;
}
//Updtae key value
if (last_root->right != NULL) {
find_node->key = last_root->right->key;
//remove last node
last_root->right = NULL;
} else {
find_node->key = last_root->left->key;
//remove last node
last_root->left = NULL;
}
}
this->updateDeletion(find_node);
cout << "\nDelete Node key : " << value << "\n";
this->preorder(this->root);
//modify tree node size
this->size--;
}
}
}
} else {
cout << "Empty max heap\n";
}
}
};
int main() {
MaxHeap obj = MaxHeap();
//Construct first max heap tree
obj.insert(5);
obj.insert(7);
obj.insert(4);
obj.insert(3);
obj.insert(9);
obj.insert(14);
obj.insert(2);
obj.insert(1);
obj.insert(6);
obj.insert(11);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
//preorder 14 11 6 1 3 7 5 9 4 2
obj.preorder(obj.root);
obj.delete_node(1);
/*
when delete node 1
14
/ \
11 9
/ \ / \
6 7 4 2
/ \
5 3
*/
obj.delete_node(2);
/*
when delete node 2
14
/ \
11 9
/ \ / \
6 7 4 3
/
5
*/
obj.delete_node(4);
/*
when delete node 4
14
/ \
11 9
/ \ / \
6 7 5 3
*/
obj.delete_node(14);
/*
when delete node 14
First make last node as root
3
/ \
11 9
/ \ /
6 7 5
//update node value
11
/ \
7 9
/ \ /
6 3 5
*/
//when node are not exist
obj.delete_node(15);
return 0;
}
Output
14 11 6 1 3 7 5 9 4 2
Delete Node key : 1
14 11 6 5 3 7 9 4 2
Delete Node key : 2
14 11 6 5 7 9 4 3
Delete Node key : 4
14 11 6 7 9 5 3
Delete Node key : 14
11 7 6 3 9 5
Delete key 15 not exist/*
Java program
Binary Max Heap Tree Node Deletion
*/
//Binary max heap node
class Node
{
public Node left;
public Node right;
public int key;
public Node(int value)
{
key = value;
left = null;
right = null;
}
}
public class MaxHeap {
//This is use to store information of number of nodes in Max heap
public int size;
public Node root;
public MaxHeap() {
root = null;
size = 0;
}
//Get height of insert new node
public int tree_height() {
int i = 1;
int sum = 0;
while (this.size > sum + (1 << i)) {
sum += (1 << i);
i++;
}
return i;
}
//interchange the two node value
public void swap_node(Node first, Node second) {
int temp = first.key;
first.key = second.key;
second.key = temp;
}
//Arrange node key
public void arrange_node(Node head) {
if (head.left != null && head.left.key > head.key) {
swap_node(head, head.left);
}
if (head.right != null && head.right.key > head.key) {
swap_node(head, head.right);
}
}
public boolean add_node(Node head, int height, int level, int value) {
if (level >= height) {
return false;
}
if (head != null) {
if (level - 1 == height && head.left == null || head.right == null) {
if (head.left == null) {
head.left = new Node(value);
} else {
head.right = new Node(value);
}
arrange_node(head);
return true;
}
if (add_node(head.left, height, level + 1, value) || add_node(head.right, height, level + 1, value)) {
//Check effect of new inserted node
arrange_node(head);
return true;
}
}
return false;
}
//Handles the request to new inserting node
public void insert(int value) {
if (root == null) {
root = new Node(value);
} else if (root.left == null) {
root.left = new Node(value);
arrange_node(root);
} else if (root.right == null) {
root.right = new Node(value);
arrange_node(root);
} else {
int height = tree_height();
add_node(root, height, 0, value);
}
this.size++;
}
public void preorder(Node head) {
if (head != null) {
System.out.print(" " + head.key);
preorder(head.left);
preorder(head.right);
}
}
public Node node_parent(Node head, int value) {
if (head != null) {
if (head.left != null && head.left.key == value ||
head.right != null && head.right.key == value) {
return head;
}
Node element = node_parent(head.left, value);
if (element == null) {
element = node_parent(head.right, value);
}
return element;
}
return head;
}
//Find last node of tree
public Node tree_last_node(Node head, int height, int level) {
if (head != null) {
if (level == height - 1 && (head.left != null || head.right != null)) {
return head;
}
Node element = tree_last_node(head.right, height, level + 1);
if (element == null) {
element = tree_last_node(head.left, height, level + 1);
}
return element;
}
return head;
}
public boolean is_max_heap(Node head) {
if ((head.left != null && head.left.key > head.key) ||
(head.right != null && head.right.key > head.key)) {
return false;
}
return true;
}
public void updateDeletion(Node find_node) {
//Find the new changes to make new max heap
//O(long h)
while (find_node != null) {
//Check max heap properties
if (is_max_heap(find_node) == false) {
//fail max heap
if (find_node.left != null && find_node.right != null) {
//Repace data with maximum value
if (find_node.left.key > find_node.right.key) {
swap_node(find_node, find_node.left);
find_node = find_node.left;
} else {
swap_node(find_node, find_node.right);
find_node = find_node.right;
}
} else if (find_node.right != null) {
swap_node(find_node, find_node.right);
find_node = find_node.right;
} else {
swap_node(find_node, find_node.left);
find_node = find_node.left;
}
}
else
{
break;
}
}
}
public void delete_node(int value)
{
if (root != null) {
Node find_node = null;
Node last_root = null;
if (root.key == value)
{
if (root.left == null && root.right == null)
{
//Delete root node
root = null;
}
else if (root.key == value && root.right == null)
{
//Only two node in max heap
find_node = root;
root = root.left;
find_node = null;
}
else
{
//Find the max height by using tree node size
int height = tree_height();
if ((1 << height) - 1 == this.size)
{
//in case given height is a perfect of all leaf
height--;
}
//Find parent of a last node of tree
last_root = tree_last_node(root, height, 0);
if (last_root != null)
{
//updtae key value
if (last_root.right != null)
{
root.key = last_root.right.key;
//remove last node
last_root.right = null;
}
else
{
root.key = last_root.left.key;
//remove last node
last_root.left = null;
}
updateDeletion(root);
}
}
System.out.print("\nDelete Node key : " + value + "\n");
preorder(root);
//modify tree node size
this.size--;
}
else
{
//When root node is not a part of delete node
//Find parent of a delete node key
find_node = node_parent(root, value);
if (find_node == null)
{
//In case delete node not exist
System.out.print("\nDelete key " + value + " not exist ");
}
else
{
//Find the max height by using tree node size
int height = tree_height();
if ((1 << height) - 1 == this.size)
{
//In case given height is a same of all leaf
height--;
}
//Find parent of a last node of tree
last_root = tree_last_node(root, height, 0);
if (last_root != null)
{
if (last_root == find_node)
{
//When delete last node
if (last_root.right != null && last_root.right.key == value) {
last_root.right = null;
}
else if (last_root.left != null && last_root.left.key == value) {
if (last_root.right != null)
{
swap_node(last_root.right, last_root.left);
last_root.right = null;
}
else
{
last_root.left = null;
}
}
}
else
{
//Get actual delete node location
if (find_node.right != null && find_node.right.key == value) {
find_node = find_node.right;
}
else
{
find_node = find_node.left;
}
//Updtae key value
if (last_root.right != null)
{
find_node.key = last_root.right.key;
//remove last node
last_root.right = null;
}
else
{
find_node.key = last_root.left.key;
//remove last node
last_root.left = null;
}
}
updateDeletion(find_node);
System.out.print("\nDelete Node key : " + value + "\n");
preorder(root);
//modify tree node size
this.size--;
}
}
}
} else {
System.out.print("Empty max heap\n");
}
}
public static void main(String[] args) {
MaxHeap obj = new MaxHeap();
//Construct first max heap tree
obj.insert(5);
obj.insert(7);
obj.insert(4);
obj.insert(3);
obj.insert(9);
obj.insert(14);
obj.insert(2);
obj.insert(1);
obj.insert(6);
obj.insert(11);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
//preorder 14 11 6 1 3 7 5 9 4 2
obj.preorder(obj.root);
obj.delete_node(1);
/*
when delete node 1
14
/ \
11 9
/ \ / \
6 7 4 2
/ \
5 3
*/
obj.delete_node(2);
/*
when delete node 2
14
/ \
11 9
/ \ / \
6 7 4 3
/
5
*/
obj.delete_node(4);
/*
when delete node 4
14
/ \
11 9
/ \ / \
6 7 5 3
*/
obj.delete_node(14);
/*
when delete node 14
First make last node as root
3
/ \
11 9
/ \ /
6 7 5
//update node value
11
/ \
7 9
/ \ /
6 3 5
*/
//when node are not exist
obj.delete_node(15);
}
}
Output
14 11 6 1 3 7 5 9 4 2
Delete Node key : 1
14 11 6 5 3 7 9 4 2
Delete Node key : 2
14 11 6 5 7 9 4 3
Delete Node key : 4
14 11 6 7 9 5 3
Delete Node key : 14
11 7 6 3 9 5
Delete key 15 not exist/*
C# program
Binary Max Heap Tree Node Deletion
*/
//Binary max heap node
using System;
public class Node {
public Node left;
public Node right;
public int key;
public Node(int value) {
key = value;
left = null;
right = null;
}
}
public class MaxHeap {
//This is use to store information of number of nodes in Max heap
public int size;
public Node root;
public MaxHeap() {
root = null;
size = 0;
}
//Get height of insert new node
public int tree_height() {
int i = 1;
int sum = 0;
while (this.size > sum + (1 << i)) {
sum += (1 << i);
i++;
}
return i;
}
//interchange the two node value
public void swap_node(Node first, Node second) {
int temp = first.key;
first.key = second.key;
second.key = temp;
}
//Arrange node key
public void arrange_node(Node head) {
if (head.left != null &&
head.left.key > head.key) {
swap_node(head, head.left);
}
if (head.right != null &&
head.right.key > head.key) {
swap_node(head, head.right);
}
}
public Boolean add_node(Node head, int height, int level, int value) {
if (level >= height) {
return false;
}
if (head != null) {
if (level - 1 == height &&
head.left == null ||
head.right == null) {
if (head.left == null) {
head.left = new Node(value);
} else {
head.right = new Node(value);
}
arrange_node(head);
return true;
}
if (add_node(head.left, height, level + 1, value) ||
add_node(head.right, height, level + 1, value)) {
arrange_node(head);
return true;
}
}
return false;
}
//Handles the request to new inserting node
public void insert(int value) {
if (root == null) {
root = new Node(value);
} else
if (root.left == null) {
root.left = new Node(value);
arrange_node(root);
} else
if (root.right == null) {
root.right = new Node(value);
arrange_node(root);
} else {
int height = tree_height();
add_node(root, height, 0, value);
}
this.size++;
}
public void preorder(Node head) {
if (head != null) {
Console.Write(" " + head.key);
preorder(head.left);
preorder(head.right);
}
}
public Node node_parent(Node head, int value) {
if (head != null) {
if (head.left != null &&
head.left.key == value ||
head.right != null &&
head.right.key == value) {
return head;
}
Node element = node_parent(head.left, value);
if (element == null) {
element = node_parent(head.right, value);
}
return element;
}
return head;
}
//Find last node of tree
public Node tree_last_node(Node head, int height, int level) {
if (head != null) {
if (level == height - 1 &&
(head.left != null ||
head.right != null)) {
return head;
}
Node element = tree_last_node(head.right, height, level + 1);
if (element == null) {
element = tree_last_node(head.left, height, level + 1);
}
return element;
}
return head;
}
public Boolean is_max_heap(Node head) {
if ((head.left != null &&
head.left.key > head.key) ||
(head.right != null &&
head.right.key > head.key)) {
return false;
}
return true;
}
public void updateDeletion(Node find_node) {
//Find the new changes to make new max heap
//O(long h)
while (find_node != null) {
//Check max heap properties
if (is_max_heap(find_node) == false) {
//fail max heap
if (find_node.left != null &&
find_node.right != null) {
//Repace data with maximum value
if (find_node.left.key > find_node.right.key) {
swap_node(find_node, find_node.left);
find_node = find_node.left;
} else {
swap_node(find_node, find_node.right);
find_node = find_node.right;
}
} else
if (find_node.right != null) {
swap_node(find_node, find_node.right);
find_node = find_node.right;
} else {
swap_node(find_node, find_node.left);
find_node = find_node.left;
}
} else {
break;;
}
}
}
public void delete_node(int value) {
if (root != null) {
Node find_node = null;
Node last_root = null;
if (root.key == value) {
if (root.left == null &&
root.right == null) {
//Delete root node
root = null;
} else
if (root.key == value &&
root.right == null) {
//Only two node in max heap
find_node = root;
root = root.left;
find_node = null;
} else {
//Find the max height by using tree node size
int height = tree_height();
if ((1 << height) - 1 == this.size) {
//in case given height is a perfect of all leaf
height--;
}
//Find parent of a last node of tree
last_root = tree_last_node(root, height, 0);
if (last_root != null) {
//updtae key value
if (last_root.right != null) {
root.key = last_root.right.key;
//remove last node
last_root.right = null;
} else {
root.key = last_root.left.key;
//remove last node
last_root.left = null;
}
updateDeletion(root);
}
}
Console.Write("\nDelete Node key : " + value + "\n");
preorder(root);
//modify tree node size
this.size--;
} else {
//When root node is not a part of delete node
//Find parent of a delete node key
find_node = node_parent(root, value);
if (find_node == null) {
Console.Write("\nDelete key " + value + " not exist ");
} else {
//Find the max height by using tree node size
int height = tree_height();
if ((1 << height) - 1 == this.size) {
//In case given height is a same of all leaf
height--;
}
//Find parent of a last node of tree
last_root = tree_last_node(root, height, 0);
if (last_root != null) {
if (last_root == find_node) {
//When delete last node
if (last_root.right != null &&
last_root.right.key == value) {
last_root.right = null;
} else
if (last_root.left != null &&
last_root.left.key == value) {
if (last_root.right != null) {
swap_node(last_root.right, last_root.left);
last_root.right = null;
} else {
last_root.left = null;
}
}
} else {
//Get actual delete node location
if (find_node.right != null &&
find_node.right.key == value) {
find_node = find_node.right;
} else {
find_node = find_node.left;
}
//Updtae key value
if (last_root.right != null) {
find_node.key = last_root.right.key;
//remove last node
last_root.right = null;
} else {
find_node.key = last_root.left.key;
//remove last node
last_root.left = null;
}
}
updateDeletion(find_node);
Console.Write("\nDelete Node key : " + value + "\n");
preorder(root);
//modify tree node size
this.size--;
}
}
}
} else {
Console.Write("Empty max heap\n");
}
}
public static void Main(String[] args) {
MaxHeap obj = new MaxHeap();
obj.insert(5);
obj.insert(7);
obj.insert(4);
obj.insert(3);
obj.insert(9);
obj.insert(14);
obj.insert(2);
obj.insert(1);
obj.insert(6);
obj.insert(11);
obj.preorder(obj.root);
obj.delete_node(1);
obj.delete_node(2);
obj.delete_node(4);
obj.delete_node(14);
obj.delete_node(15);
}
}
Output
14 11 6 1 3 7 5 9 4 2
Delete Node key : 1
14 11 6 5 3 7 9 4 2
Delete Node key : 2
14 11 6 5 7 9 4 3
Delete Node key : 4
14 11 6 7 9 5 3
Delete Node key : 14
11 7 6 3 9 5
Delete key 15 not exist<?php
/*
Php program
Binary Max Heap Tree Node Deletion
*/
//Binary max heap node
class Node {
public $left;
public $right;
public $key;
function __construct($value) {
$this->key = $value;
$this->left = null;
$this->right = null;
}
}
class MaxHeap {
//This is use to store information of number of nodes in Max heap
public $size;
public $root;
function __construct() {
$this->root = null;
$this->size = 0;
}
//Get height of insert new node
public function tree_height() {
$i = 1;
$sum = 0;
while ($this->size > $sum + (1 << $i)) {
$sum += (1 << $i);
$i++;
}
return $i;
}
//interchange the two node value
public function swap_node($first, $second) {
$temp = $first->key;
$first->key = $second->key;
$second->key = $temp;
}
//Arrange node key
public function arrange_node($head) {
if ($head->left != null &&
$head->left->key > $head->key) {
$this->swap_node($head, $head->left);
}
if ($head->right != null &&
$head->right->key > $head->key) {
$this->swap_node($head, $head->right);
}
}
public function add_node($head, $height, $level, $value) {
if ($level >= $height) {
return false;
}
if ($head != null) {
if ($level - 1 == $height &&
$head->left == null ||
$head->right == null) {
if ($head->left == null) {
$head->left = new Node($value);
} else {
$head->right = new Node($value);
}
$this->arrange_node($head);
return true;
}
if ($this->add_node($head->left, $height, $level + 1, $value) ||
$this->add_node($head->right, $height, $level + 1, $value)) {
//Check effect of new inserted node
$this->arrange_node($head);
return true;
}
}
return false;
}
//Handles the request to new inserting node
public function insert($value) {
if ($this->root == null) {
$this->root = new Node($value);
} else
if ($this->root->left == null) {
$this->root->left = new Node($value);
$this->arrange_node($this->root);
} else
if ($this->root->right == null) {
$this->root->right = new Node($value);
$this->arrange_node($this->root);
} else {
$height = $this->tree_height();
$this->add_node($this->root, $height, 0, $value);
}
$this->size++;
}
public function preorder($head) {
if ($head != null) {
echo(" ". $head->key);
$this->preorder($head->left);
$this->preorder($head->right);
}
}
public function node_parent($head, $value) {
if ($head != null) {
if ($head->left != null &&
$head->left->key == $value ||
$head->right != null &&
$head->right->key == $value) {
return $head;
}
$element = $this->node_parent($head->left, $value);
if ($element == null) {
$element = $this->node_parent($head->right, $value);
}
return $element;
}
return $head;
}
//Find last node of tree
public function tree_last_node($head, $height, $level) {
if ($head != null) {
if ($level == $height - 1 &&
($head->left != null ||
$head->right != null)) {
return $head;
}
$element = $this->tree_last_node($head->right, $height, $level + 1);
if ($element == null) {
$element = $this->tree_last_node($head->left, $height, $level + 1);
}
return $element;
}
return $head;
}
public function is_max_heap($head) {
if (($head->left != null &&
$head->left->key > $head->key) ||
($head->right != null &&
$head->right->key > $head->key)) {
return false;
}
return true;
}
public function updateDeletion($find_node) {
//Find the new changes to make new max heap
//O(long h)
while ($find_node != null) {
//Check max heap properties
if ($this->is_max_heap($find_node) == false) {
//fail max heap
if ($find_node->left != null &&
$find_node->right != null) {
//Repace data with maximum value
if ($find_node->left->key > $find_node->right->key) {
$this->swap_node($find_node, $find_node->left);
$find_node = $find_node->left;
} else {
$this->swap_node($find_node, $find_node->right);
$find_node = $find_node->right;
}
} else
if ($find_node->right != null) {
$this->swap_node($find_node, $find_node->right);
$find_node = $find_node->right;
} else {
$this->swap_node($find_node, $find_node->left);
$find_node = $find_node->left;
}
} else {
break;
}
}
}
public function delete_node($value) {
if ($this->root != null) {
$find_node = null;
$last_root = null;
if ($this->root->key == $value) {
if ($this->root->left == null &&
$this->root->right == null) {
//Delete root node
$this->root = null;
} else
if ($this->root->key == $value &&
$this->root->right == null) {
//Only two node in max heap
$find_node = $this->root;
$this->root = $this->root->left;
$find_node = null;
} else {
//Find the max height by using tree node size
$height = $this->tree_height();
if ((1 << $height) - 1 == $this->size) {
//in case given height is a perfect of all leaf
$height--;
}
//Find parent of a last node of tree
$last_root = $this->tree_last_node($this->root, $height, 0);
if ($last_root != null) {
//updtae key value
if ($last_root->right != null) {
$this->root->key = $last_root->right->key;
//remove last node
$last_root->right = null;
} else {
$this->root->key = $last_root->left->key;
//remove last node
$last_root->left = null;
}
$this->updateDeletion($this->root);
}
}
echo("\nDelete Node key : ". $value ."\n");
$this->preorder($this->root);
//modify tree node size
$this->size--;
} else {
//When root node is not a part of delete node
//Find parent of a delete node key
$find_node = $this->node_parent($this->root, $value);
if ($find_node == null) {
//In case delete node not exist
echo("\nDelete key ". $value ." not exist ");
} else {
//Find the max height by using tree node size
$height = $this->tree_height();
if ((1 << $height) - 1 == $this->size) {
//In case given height is a same of all leaf
$height--;
}
//Find parent of a last node of tree
$last_root = $this->tree_last_node($this->root, $height, 0);
if ($last_root != null) {
if ($last_root == $find_node) {
//When delete last node
if ($last_root->right != null &&
$last_root->right->key == $value) {
$last_root->right = null;
} else
if ($last_root->left != null &&
$last_root->left->key == $value) {
if ($last_root->right != null) {
$this->swap_node($last_root->right, $last_root->left);
$last_root->right = null;
} else {
$last_root->left = null;
}
}
} else {
//Get actual delete node location
if ($find_node->right != null &&
$find_node->right->key == $value) {
$find_node = $find_node->right;
} else {
$find_node = $find_node->left;
}
//Updtae key value
if ($last_root->right != null) {
$find_node->key = $last_root->right->key;
//remove last node
$last_root->right = null;
} else {
$find_node->key = $last_root->left->key;
//remove last node
$last_root->left = null;
}
}
$this->updateDeletion($find_node);
echo("\nDelete Node key : ". $value ."\n");
$this->preorder($this->root);
//modify tree node size
$this->size--;
}
}
}
} else {
echo("Empty max heap\n");
}
}
}
function main() {
$obj = new MaxHeap();
//Construct first max heap tree
$obj->insert(5);
$obj->insert(7);
$obj->insert(4);
$obj->insert(3);
$obj->insert(9);
$obj->insert(14);
$obj->insert(2);
$obj->insert(1);
$obj->insert(6);
$obj->insert(11);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
//preorder 14 11 6 1 3 7 5 9 4 2
$obj->preorder($obj->root);
$obj->delete_node(1);
/*
when delete node 1
14
/ \
11 9
/ \ / \
6 7 4 2
/ \
5 3
*/
$obj->delete_node(2);
/*
when delete node 2
14
/ \
11 9
/ \ / \
6 7 4 3
/
5
*/
$obj->delete_node(4);
/*
when delete node 4
14
/ \
11 9
/ \ / \
6 7 5 3
*/
$obj->delete_node(14);
/*
when delete node 14
First make last node as root
3
/ \
11 9
/ \ /
6 7 5
//update node value
11
/ \
7 9
/ \ /
6 3 5
*/
//when node are not exist
$obj->delete_node(15);
}
main();
Output
14 11 6 1 3 7 5 9 4 2
Delete Node key : 1
14 11 6 5 3 7 9 4 2
Delete Node key : 2
14 11 6 5 7 9 4 3
Delete Node key : 4
14 11 6 7 9 5 3
Delete Node key : 14
11 7 6 3 9 5
Delete key 15 not exist/*
Node Js program
Binary Max Heap Tree Node Deletion
*/
//Binary max heap node
class Node {
constructor(value) {
this.key = value;
this.left = null;
this.right = null;
}
}
class MaxHeap {
//This is use to store information of number of nodes in Max heap
constructor() {
this.root = null;
this.size = 0;
}
//Get height of insert new node
tree_height() {
var i = 1;
var sum = 0;
while (this.size > sum + (1 << i)) {
sum += (1 << i);
i++;
}
return i;
}
//interchange the two node value
swap_node(first, second) {
var temp = first.key;
first.key = second.key;
second.key = temp;
}
//Arrange node key
arrange_node(head) {
if (head.left != null &&
head.left.key > head.key) {
this.swap_node(head, head.left);
}
if (head.right != null &&
head.right.key > head.key) {
this.swap_node(head, head.right);
}
}
add_node(head, height, level, value) {
if (level >= height) {
return false;
}
if (head != null) {
if (level - 1 == height &&
head.left == null ||
head.right == null) {
if (head.left == null) {
head.left = new Node(value);
} else {
head.right = new Node(value);
}
this.arrange_node(head);
return true;
}
if (this.add_node(head.left, height, level + 1, value) ||
this.add_node(head.right, height, level + 1, value)) {
//Check effect of new inserted node
this.arrange_node(head);
return true;
}
}
return false;
}
//Handles the request to new inserting node
insert(value) {
if (this.root == null) {
this.root = new Node(value);
} else
if (this.root.left == null) {
this.root.left = new Node(value);
this.arrange_node(this.root);
} else
if (this.root.right == null) {
this.root.right = new Node(value);
this.arrange_node(this.root);
} else {
var height = this.tree_height();
this.add_node(this.root, height, 0, value);
}
this.size++;
}
preorder(head) {
if (head != null) {
process.stdout.write(" " + head.key);
this.preorder(head.left);
this.preorder(head.right);
}
}
node_parent(head, value) {
if (head != null) {
if (head.left != null &&
head.left.key == value ||
head.right != null &&
head.right.key == value) {
return head;
}
var element = this.node_parent(head.left, value);
if (element == null) {
element = this.node_parent(head.right, value);
}
return element;
}
return head;
}
//Find last node of tree
tree_last_node(head, height, level) {
if (head != null) {
if (level == height - 1 &&
(head.left != null ||
head.right != null)) {
return head;
}
var element = this.tree_last_node(head.right, height, level + 1);
if (element == null) {
element = this.tree_last_node(head.left, height, level + 1);
}
return element;
}
return head;
}
is_max_heap(head) {
if ((head.left != null &&
head.left.key > head.key) ||
(head.right != null &&
head.right.key > head.key)) {
return false;
}
return true;
}
updateDeletion(find_node) {
//Find the new changes to make new max heap
//O(long h)
while (find_node != null) {
//Check max heap properties
if (this.is_max_heap(find_node) == false) {
//fail max heap
if (find_node.left != null &&
find_node.right != null) {
//Repace data with maximum value
if (find_node.left.key > find_node.right.key) {
this.swap_node(find_node, find_node.left);
find_node = find_node.left;
} else {
this.swap_node(find_node, find_node.right);
find_node = find_node.right;
}
} else
if (find_node.right != null) {
this.swap_node(find_node, find_node.right);
find_node = find_node.right;
} else {
this.swap_node(find_node, find_node.left);
find_node = find_node.left;
}
} else {
break;
}
}
}
delete_node(value) {
if (this.root != null) {
var find_node = null;
var last_root = null;
if (this.root.key == value) {
if (this.root.left == null &&
this.root.right == null) {
//Delete root node
this.root = null;
} else
if (this.root.key == value &&
this.root.right == null) {
//Only two node in max heap
find_node = this.root;
this.root = this.root.left;
find_node = null;
} else {
//Find the max height by using tree node size
var height = this.tree_height();
if ((1 << height) - 1 == this.size) {
//in case given height is a perfect of all leaf
height--;
}
//Find parent of a last node of tree
last_root = this.tree_last_node(this.root, height, 0);
if (last_root != null) {
//updtae key value
if (last_root.right != null) {
this.root.key = last_root.right.key;
//remove last node
last_root.right = null;
} else {
this.root.key = last_root.left.key;
//remove last node
last_root.left = null;
}
this.updateDeletion(this.root);
}
}
process.stdout.write("\nDelete Node key : " + value + "\n");
this.preorder(this.root);
//modify tree node size
this.size--;
} else {
//When root node is not a part of delete node
//Find parent of a delete node key
find_node = this.node_parent(this.root, value);
if (find_node == null) {
//In case delete node not exist
process.stdout.write("\nDelete key " + value + " not exist ");
} else {
//Find the max height by using tree node size
var height = this.tree_height();
if ((1 << height) - 1 == this.size) {
//In case given height is a same of all leaf
height--;
}
//Find parent of a last node of tree
last_root = this.tree_last_node(this.root, height, 0);
if (last_root != null) {
if (last_root == find_node) {
//When delete last node
if (last_root.right != null &&
last_root.right.key == value) {
last_root.right = null;
} else
if (last_root.left != null &&
last_root.left.key == value) {
if (last_root.right != null) {
this.swap_node(last_root.right, last_root.left);
last_root.right = null;
} else {
last_root.left = null;
}
}
} else {
//Get actual delete node location
if (find_node.right != null &&
find_node.right.key == value) {
find_node = find_node.right;
} else {
find_node = find_node.left;
}
//Updtae key value
if (last_root.right != null) {
find_node.key = last_root.right.key;
//remove last node
last_root.right = null;
} else {
find_node.key = last_root.left.key;
//remove last node
last_root.left = null;
}
}
this.updateDeletion(find_node);
process.stdout.write("\nDelete Node key : " + value + "\n");
this.preorder(this.root);
//modify tree node size
this.size--;
}
}
}
} else {
process.stdout.write("Empty max heap\n");
}
}
}
function main(args) {
var obj = new MaxHeap();
//Construct first max heap tree
obj.insert(5);
obj.insert(7);
obj.insert(4);
obj.insert(3);
obj.insert(9);
obj.insert(14);
obj.insert(2);
obj.insert(1);
obj.insert(6);
obj.insert(11);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
//preorder 14 11 6 1 3 7 5 9 4 2
obj.preorder(obj.root);
obj.delete_node(1);
/*
when delete node 1
14
/ \
11 9
/ \ / \
6 7 4 2
/ \
5 3
*/
obj.delete_node(2);
/*
when delete node 2
14
/ \
11 9
/ \ / \
6 7 4 3
/
5
*/
obj.delete_node(4);
/*
when delete node 4
14
/ \
11 9
/ \ / \
6 7 5 3
*/
obj.delete_node(14);
/*
when delete node 14
First make last node as root
3
/ \
11 9
/ \ /
6 7 5
//update node value
11
/ \
7 9
/ \ /
6 3 5
*/
//when node are not exist
obj.delete_node(15);
}
main();
Output
14 11 6 1 3 7 5 9 4 2
Delete Node key : 1
14 11 6 5 3 7 9 4 2
Delete Node key : 2
14 11 6 5 7 9 4 3
Delete Node key : 4
14 11 6 7 9 5 3
Delete Node key : 14
11 7 6 3 9 5
Delete key 15 not exist# Python 3 program
# Binary Max Heap Tree Node Deletion
# Binary max heap node
class Node :
def __init__(self, value) :
self.key = value
self.left = None
self.right = None
class MaxHeap :
# This is use to store information of number of nodes in Max heap
def __init__(self) :
self.root = None
self.size = 0
# Get height of insert new node
def tree_height(self) :
i = 1
sum = 0
while (self.size > sum + (1 << i)) :
sum += (1 << i)
i += 1
return i
# interchange the two node value
def swap_node(self, first, second) :
temp = first.key
first.key = second.key
second.key = temp
# Arrange node key
def arrange_node(self, head) :
if (head.left != None and head.left.key > head.key) :
self.swap_node(head, head.left)
if (head.right != None and head.right.key > head.key) :
self.swap_node(head, head.right)
def add_node(self, head, height, level, value) :
if (level >= height) :
return False
if (head != None) :
if (level - 1 == height and head.left == None or head.right == None) :
if (head.left == None) :
head.left = Node(value)
else :
head.right = Node(value)
self.arrange_node(head)
return True
if (self.add_node(head.left, height, level + 1, value) or
self.add_node(head.right, height, level + 1, value)) :
# Check effect of new inserted node
self.arrange_node(head)
return True
return False
# Handles the request to new inserting node
def insert(self, value) :
if (self.root == None) :
self.root = Node(value)
elif (self.root.left == None) :
self.root.left = Node(value)
self.arrange_node(self.root)
elif (self.root.right == None) :
self.root.right = Node(value)
self.arrange_node(self.root)
else :
height = self.tree_height()
self.add_node(self.root, height, 0, value)
self.size += 1
def preorder(self, head) :
if (head != None) :
print(" ", head.key, end = "")
self.preorder(head.left)
self.preorder(head.right)
def node_parent(self, head, value) :
if (head != None) :
if (head.left != None and head.left.key == value
or head.right != None and head.right.key == value) :
return head
element = self.node_parent(head.left, value)
if (element == None) :
element = self.node_parent(head.right, value)
return element
return head
# Find last node of tree
def tree_last_node(self, head, height, level) :
if (head != None) :
if (level == height - 1 and(head.left != None or head.right != None)) :
return head
element = self.tree_last_node(head.right, height, level + 1)
if (element == None) :
element = self.tree_last_node(head.left, height, level + 1)
return element
return head
def is_max_heap(self, head) :
if ((head.left != None and head.left.key > head.key) or(head.right != None and head.right.key > head.key)) :
return False
return True
def updateDeletion(self, find_node) :
# Find the new changes to make new max heap
# O(long h)
while (find_node != None) :
# Check max heap properties
if (self.is_max_heap(find_node) == False) :
# fail max heap
if (find_node.left != None and find_node.right != None) :
# Repace data with maximum value
if (find_node.left.key > find_node.right.key) :
self.swap_node(find_node, find_node.left)
find_node = find_node.left
else :
self.swap_node(find_node, find_node.right)
find_node = find_node.right
elif (find_node.right != None) :
self.swap_node(find_node, find_node.right)
find_node = find_node.right
else :
self.swap_node(find_node, find_node.left)
find_node = find_node.left
else :
break
def delete_node(self, value) :
if (self.root != None) :
find_node = None
last_root = None
if (self.root.key == value) :
if (self.root.left == None and self.root.right == None) :
# Delete root node
self.root = None
elif (self.root.key == value and self.root.right == None) :
# Only two node in max heap
find_node = self.root
self.root = self.root.left
find_node = None
else :
# Find the max height by using tree node size
height = self.tree_height()
if ((1 << height) - 1 == self.size) :
# in case given height is a perfect of all leaf
height -= 1
# Find parent of a last node of tree
last_root = self.tree_last_node(self.root, height, 0)
if (last_root != None) :
# updtae key value
if (last_root.right != None) :
self.root.key = last_root.right.key
# remove last node
last_root.right = None
else :
self.root.key = last_root.left.key
# remove last node
last_root.left = None
self.updateDeletion(self.root)
print("\nDelete Node key : ", value ,"\n", end = "")
self.preorder(self.root)
# modify tree node size
self.size -= 1
else :
# When root node is not a part of delete node
# Find parent of a delete node key
find_node = self.node_parent(self.root, value)
if (find_node == None) :
# In case delete node not exist
print("\nDelete key ", value ," not exist ", end = "")
else :
# Find the max height by using tree node size
height = self.tree_height()
if ((1 << height) - 1 == self.size) :
# In case given height is a same of all leaf
height -= 1
# Find parent of a last node of tree
last_root = self.tree_last_node(self.root, height, 0)
if (last_root != None) :
if (last_root == find_node) :
# When delete last node
if (last_root.right != None and last_root.right.key == value) :
last_root.right = None
elif (last_root.left != None and last_root.left.key == value) :
if (last_root.right != None) :
self.swap_node(last_root.right, last_root.left)
last_root.right = None
else :
last_root.left = None
else :
# Get actual delete node location
if (find_node.right != None and find_node.right.key == value) :
find_node = find_node.right
else :
find_node = find_node.left
# Updtae key value
if (last_root.right != None) :
find_node.key = last_root.right.key
# remove last node
last_root.right = None
else :
find_node.key = last_root.left.key
# remove last node
last_root.left = None
self.updateDeletion(find_node)
print("\nDelete Node key : ", value ,"\n", end = "")
self.preorder(self.root)
# modify tree node size
self.size -= 1
else :
print("Empty max heap\n", end = "")
def main() :
obj = MaxHeap()
# Construct first max heap tree
obj.insert(5)
obj.insert(7)
obj.insert(4)
obj.insert(3)
obj.insert(9)
obj.insert(14)
obj.insert(2)
obj.insert(1)
obj.insert(6)
obj.insert(11)
# preorder 14 11 6 1 3 7 5 9 4 2
#
# 14
# / \
# 11 9
# / \ / \
# 6 7 4 2
# / \ /
# 1 3 5
#
# After insert element
obj.preorder(obj.root)
obj.delete_node(1)
#
# when delete node 1
# 14
# / \
# 11 9
# / \ / \
# 6 7 4 2
# / \
# 5 3
#
obj.delete_node(2)
#
# when delete node 2
# 14
# / \
# 11 9
# / \ / \
# 6 7 4 3
# /
# 5
#
obj.delete_node(4)
#
# when delete node 4
# 14
# / \
# 11 9
# / \ / \
# 6 7 5 3
#
#
#
obj.delete_node(14)
# when node are not exist
#
# when delete node 14
# First make last node as root
# 3
# / \
# 11 9
# / \ /
# 6 7 5
#
# //update node value
#
# 11
# / \
# 7 9
# / \ /
# 6 3 5
#
#
#
obj.delete_node(15)
if __name__ == "__main__":
main()
Output
14 11 6 1 3 7 5 9 4 2
Delete Node key : 1
14 11 6 5 3 7 9 4 2
Delete Node key : 2
14 11 6 5 7 9 4 3
Delete Node key : 4
14 11 6 7 9 5 3
Delete Node key : 14
11 7 6 3 9 5
Delete key 15 not exist# Ruby program
# Binary Max Heap Tree Node Deletion
# Binary max heap node
class Node
# Define the accessor and reader of class Node
attr_reader :left, :right, :key
attr_accessor :left, :right, :key
def initialize(value)
@key = value
@left = nil
@right = nil
end
end
class MaxHeap
# Define the accessor and reader of class MaxHeap
attr_reader :size, :root
attr_accessor :size, :root
# This is use to store information of number of nodes in Max heap
def initialize()
@root = nil
@size = 0
end
# Get height of insert new node
def tree_height()
i = 1
sum = 0
while (self.size > sum + (1 << i))
sum += (1 << i)
i += 1
end
return i
end
# interchange the two node value
def swap_node(first, second)
temp = first.key
first.key = second.key
second.key = temp
end
# Arrange node key
def arrange_node(head)
if (head.left != nil &&
head.left.key > head.key)
self.swap_node(head, head.left)
end
if (head.right != nil &&
head.right.key > head.key)
self.swap_node(head, head.right)
end
end
def add_node(head, height, level, value)
if (level >= height)
return false
end
if (head != nil)
if (level - 1 == height &&
head.left == nil ||
head.right == nil)
if (head.left == nil)
head.left = Node.new(value)
else
head.right = Node.new(value)
end
self.arrange_node(head)
return true
end
if (self.add_node(head.left, height, level + 1, value) ||
self.add_node(head.right, height, level + 1, value))
# Check effect of new inserted node
self.arrange_node(head)
return true
end
end
return false
end
# Handles the request to new inserting node
def insert(value)
if (@root == nil)
@root = Node.new(value)
elsif (@root.left == nil)
@root.left = Node.new(value)
self.arrange_node(@root)
elsif (@root.right == nil)
@root.right = Node.new(value)
self.arrange_node(@root)
else
height = self.tree_height()
self.add_node(@root, height, 0, value)
end
self.size += 1
end
def preorder(head)
if (head != nil)
print(" ", head.key)
self.preorder(head.left)
self.preorder(head.right)
end
end
def node_parent(head, value)
if (head != nil)
if (head.left != nil &&
head.left.key == value ||
head.right != nil &&
head.right.key == value)
return head
end
element = self.node_parent(head.left, value)
if (element == nil)
element = self.node_parent(head.right, value)
end
return element
end
return head
end
# Find last node of tree
def tree_last_node(head, height, level)
if (head != nil)
if (level == height - 1 &&
(head.left != nil ||
head.right != nil))
return head
end
element = self.tree_last_node(head.right, height, level + 1)
if (element == nil)
element = self.tree_last_node(head.left, height, level + 1)
end
return element
end
return head
end
def is_max_heap(head)
if ((head.left != nil &&
head.left.key > head.key) ||
(head.right != nil &&
head.right.key > head.key))
return false
end
return true
end
def updateDeletion(find_node)
# Find the new changes to make new max heap
# O(long h)
while (find_node != nil)
# Check max heap properties
if (self.is_max_heap(find_node) == false)
# fail max heap
if (find_node.left != nil &&
find_node.right != nil)
# Repace data with maximum value
if (find_node.left.key > find_node.right.key)
self.swap_node(find_node, find_node.left)
find_node = find_node.left
else
self.swap_node(find_node, find_node.right)
find_node = find_node.right
end
elsif (find_node.right != nil)
self.swap_node(find_node, find_node.right)
find_node = find_node.right
else
self.swap_node(find_node, find_node.left)
find_node = find_node.left
end
else
break
end
end
end
def delete_node(value)
if (@root != nil)
find_node = nil
last_root = nil
if (@root.key == value)
if (@root.left == nil &&
@root.right == nil)
# Delete root node
@root = nil
elsif (@root.key == value &&
@root.right == nil)
# Only two node in max heap
find_node = @root
@root = @root.left
find_node = nil
else
# Find the max height by using tree node size
height = self.tree_height()
if ((1 << height) - 1 == self.size)
# in case given height is a perfect of all leaf
height -= 1
end
# Find parent of a last node of tree
last_root = self.tree_last_node(@root, height, 0)
if (last_root != nil)
# updtae key value
if (last_root.right != nil)
@root.key = last_root.right.key
# remove last node
last_root.right = nil
else
@root.key = last_root.left.key
# remove last node
last_root.left = nil
end
self.updateDeletion(@root)
end
end
print("\nDelete Node key :", value ,"\n")
self.preorder(@root)
# modify tree node size
self.size -= 1
else
# When root node is not a part of delete node
# Find parent of a delete node key
find_node = self.node_parent(@root, value)
if (find_node == nil)
# In case delete node not exist
print("\nDelete key ", value ," not exist ")
else
# Find the max height by using tree node size
height = self.tree_height()
if ((1 << height) - 1 == self.size)
# In case given height is a same of all leaf
height -= 1
end
# Find parent of a last node of tree
last_root = self.tree_last_node(@root, height, 0)
if (last_root != nil)
if (last_root == find_node)
# When delete last node
if (last_root.right != nil &&
last_root.right.key == value)
last_root.right = nil
elsif (last_root.left != nil &&
last_root.left.key == value)
if (last_root.right != nil)
self.swap_node(last_root.right, last_root.left)
last_root.right = nil
else
last_root.left = nil
end
end
else
# Get actual delete node location
if (find_node.right != nil &&
find_node.right.key == value)
find_node = find_node.right
else
find_node = find_node.left
end
# Updtae key value
if (last_root.right != nil)
find_node.key = last_root.right.key
# remove last node
last_root.right = nil
else
find_node.key = last_root.left.key
# remove last node
last_root.left = nil
end
end
self.updateDeletion(find_node)
print("\nDelete Node key : ", value ,"\n")
self.preorder(@root)
# modify tree node size
self.size -= 1
end
end
end
else
print("Empty max heap\n")
end
end
end
def main()
obj = MaxHeap.new()
# Construct first max heap tree
obj.insert(5)
obj.insert(7)
obj.insert(4)
obj.insert(3)
obj.insert(9)
obj.insert(14)
obj.insert(2)
obj.insert(1)
obj.insert(6)
obj.insert(11)
# preorder 14 11 6 1 3 7 5 9 4 2
#
# 14
# / \
# 11 9
# / \ / \
# 6 7 4 2
# / \ /
# 1 3 5
#
# After insert element
obj.preorder(obj.root)
obj.delete_node(1)
#
# when delete node 1
# 14
# / \
# 11 9
# / \ / \
# 6 7 4 2
# / \
# 5 3
#
obj.delete_node(2)
#
# when delete node 2
# 14
# / \
# 11 9
# / \ / \
# 6 7 4 3
# /
# 5
#
obj.delete_node(4)
#
# when delete node 4
# 14
# / \
# 11 9
# / \ / \
# 6 7 5 3
#
#
#
obj.delete_node(14)
# when node are not exist
#
# when delete node 14
# First make last node as root
# 3
# / \
# 11 9
# / \ /
# 6 7 5
#
# //update node value
#
# 11
# / \
# 7 9
# / \ /
# 6 3 5
#
#
#
obj.delete_node(15)
end
main()
Output
14 11 6 1 3 7 5 9 4 2
Delete Node key : 1
14 11 6 5 3 7 9 4 2
Delete Node key : 2
14 11 6 5 7 9 4 3
Delete Node key : 4
14 11 6 7 9 5 3
Delete Node key :14
11 7 6 3 9 5
Delete key 15 not exist /*
Scala program
Binary Max Heap Tree Node Deletion
*/
//Binary max heap node
class Node(var left: Node,
var right: Node,
var key: Int) {
def this(value: Int) {
this(null,null,value);
}
}
class MaxHeap(var size: Int,
var root: Node) {
//size is use to store information of number of nodes in Max heap
def this() {
this(0,null);
}
//Get height of insert new node
def tree_height(): Int = {
var i: Int = 1;
var sum: Int = 0;
while (this.size > sum + (1 << i)) {
sum += (1 << i);
i += 1;
}
return i;
}
//interchange the two node value
def swap_node(first: Node, second: Node): Unit = {
var temp: Int = first.key;
first.key = second.key;
second.key = temp;
}
//Arrange node key
def arrange_node(head: Node): Unit = {
if (head.left != null &&
head.left.key > head.key) {
swap_node(head, head.left);
}
if (head.right != null &&
head.right.key > head.key) {
swap_node(head, head.right);
}
}
def add_node(head: Node, height: Int, level: Int, value: Int): Boolean = {
if (level >= height) {
return false;
}
if (head != null) {
if (level - 1 == height &&
head.left == null ||
head.right == null) {
if (head.left == null) {
head.left = new Node(value);
} else {
head.right = new Node(value);
}
arrange_node(head);
return true;
}
if (add_node(head.left, height, level + 1, value) ||
add_node(head.right, height, level + 1, value)) {
//Check effect of new inserted node
arrange_node(head);
return true;
}
}
return false;
}
//Handles the request to new inserting node
def insert(value: Int): Unit = {
if (root == null) {
root = new Node(value);
} else
if (root.left == null) {
root.left = new Node(value);
arrange_node(root);
} else
if (root.right == null) {
root.right = new Node(value);
arrange_node(root);
} else {
var height: Int = tree_height();
add_node(root, height, 0, value);
}
this.size += 1;
}
def preorder(head: Node): Unit = {
if (head != null) {
print(" " + head.key);
preorder(head.left);
preorder(head.right);
}
}
def node_parent(head: Node, value: Int): Node = {
if (head != null) {
if (head.left != null &&
head.left.key == value ||
head.right != null &&
head.right.key == value) {
return head;
}
var element: Node = node_parent(head.left, value);
if (element == null) {
element = node_parent(head.right, value);
}
return element;
}
return head;
}
//Find last node of tree
def tree_last_node(head: Node, height: Int, level: Int): Node = {
if (head != null) {
if (level == height - 1 &&
(head.left != null ||
head.right != null)) {
return head;
}
var element: Node = tree_last_node(head.right, height, level + 1);
if (element == null) {
element = tree_last_node(head.left, height, level + 1);
}
return element;
}
return head;
}
def is_max_heap(head: Node): Boolean = {
if ((head.left != null &&
head.left.key > head.key) ||
(head.right != null &&
head.right.key > head.key)) {
return false;
}
return true;
}
def updateDeletion(element: Node): Unit = {
//Find the new changes to make new max heap
//O(long h)
var find_node: Node = element;
while (find_node != null) {
//Check max heap properties
if (is_max_heap(find_node) == false) {
//fail max heap
if (find_node.left != null &&
find_node.right != null) {
//Repace data with maximum value
if (find_node.left.key > find_node.right.key) {
swap_node(find_node, find_node.left);
find_node = find_node.left;
} else {
swap_node(find_node, find_node.right);
find_node = find_node.right;
}
} else
if (find_node.right != null) {
swap_node(find_node, find_node.right);
find_node = find_node.right;
} else {
swap_node(find_node, find_node.left);
find_node = find_node.left;
}
} else {
return;
}
}
}
def delete_node(value: Int): Unit = {
if (root != null) {
var find_node: Node = null;
var last_root: Node = null;
var height: Int = 0;
if (root.key == value) {
if (root.left == null &&
root.right == null) {
//Delete root node
root = null;
} else
if (root.key == value &&
root.right == null) {
//Only two node in max heap
find_node = root;
root = root.left;
find_node = null;
} else {
//Find the max height by using tree node size
height = tree_height();
if ((1 << height) - 1 == this.size) {
//in case given height is a perfect of all leaf
height -= 1;
}
//Find parent of a last node of tree
last_root = tree_last_node(root, height, 0);
if (last_root != null) {
//updtae key value
if (last_root.right != null) {
root.key = last_root.right.key;
//remove last node
last_root.right = null;
} else {
root.key = last_root.left.key;
//remove last node
last_root.left = null;
}
updateDeletion(root);
}
}
print("\nDelete Node key : " + value + "\n");
preorder(root);
//modify tree node size
this.size -= 1;
} else {
//When root node is not a part of delete node
//Find parent of a delete node key
find_node = node_parent(root, value);
if (find_node == null) {
//In case delete node not exist
print("\nDelete key " + value + " not exist ");
} else {
//Find the max height by using tree node size
height = this.tree_height();
if ((1 << height) - 1 == this.size) {
//In case given height is a same of all leaf
height -= 1;
}
//Find parent of a last node of tree
last_root = tree_last_node(root, height, 0);
if (last_root != null) {
if (last_root == find_node) {
//When delete last node
if (last_root.right != null &&
last_root.right.key == value) {
last_root.right = null;
} else
if (last_root.left != null &&
last_root.left.key == value) {
if (last_root.right != null) {
swap_node(last_root.right, last_root.left);
last_root.right = null;
} else {
last_root.left = null;
}
}
} else {
//Get actual delete node location
if (find_node.right != null &&
find_node.right.key == value) {
find_node = find_node.right;
} else {
find_node = find_node.left;
}
//Updtae key value
if (last_root.right != null) {
find_node.key = last_root.right.key;
//remove last node
last_root.right = null;
} else {
find_node.key = last_root.left.key;
//remove last node
last_root.left = null;
}
}
updateDeletion(find_node);
print("\nDelete Node key : " + value + "\n");
preorder(root);
//modify tree node size
this.size -= 1;
}
}
}
} else {
print("Empty max heap\n");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var obj: MaxHeap = new MaxHeap();
//Construct first max heap tree
obj.insert(5);
obj.insert(7);
obj.insert(4);
obj.insert(3);
obj.insert(9);
obj.insert(14);
obj.insert(2);
obj.insert(1);
obj.insert(6);
obj.insert(11);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
//preorder 14 11 6 1 3 7 5 9 4 2
obj.preorder(obj.root);
obj.delete_node(1);
/*
when delete node 1
14
/ \
11 9
/ \ / \
6 7 4 2
/ \
5 3
*/
obj.delete_node(2);
/*
when delete node 2
14
/ \
11 9
/ \ / \
6 7 4 3
/
5
*/
obj.delete_node(4);
/*
when delete node 4
14
/ \
11 9
/ \ / \
6 7 5 3
*/
obj.delete_node(14);
/*
when delete node 14
First make last node as root
3
/ \
11 9
/ \ /
6 7 5
//update node value
11
/ \
7 9
/ \ /
6 3 5
*/
//when node are not exist
obj.delete_node(15);
}
}
Output
14 11 6 1 3 7 5 9 4 2
Delete Node key : 1
14 11 6 5 3 7 9 4 2
Delete Node key : 2
14 11 6 5 7 9 4 3
Delete Node key : 4
14 11 6 7 9 5 3
Delete Node key : 14
11 7 6 3 9 5
Delete key 15 not exist/*
Swift program
Binary Max Heap Tree Node Deletion
*/
//Binary max heap node
class Node {
var left: Node? ;
var right: Node? ;
var key: Int;
init(_ value: Int) {
self.key = value;
self.left = nil;
self.right = nil;
}
}
class MaxHeap {
//This is use to store information of number of nodes in Max heap
var size: Int;
var root: Node? ;
init() {
self.root = nil;
self.size = 0;
}
//Get height of insert new node
func tree_height() -> Int {
var i: Int = 1;
var sum: Int = 0;
while (self.size > sum + (1 << i)) {
sum += (1 << i);
i += 1;
}
return i;
}
//interchange the two node value
func swap_node(_ first: Node? , _ second : Node? ) {
let temp: Int = first!.key;
first!.key = second!.key;
second!.key = temp;
}
//Arrange node key
func arrange_node(_ head: Node? ) {
if (head!.left != nil &&
head!.left!.key > head!.key) {
self.swap_node(head, head!.left);
}
if (head!.right != nil &&
head!.right!.key > head!.key) {
self.swap_node(head, head!.right);
}
}
func add_node(_ head: Node? , _ height : Int, _ level: Int, _ value: Int) -> Bool {
if (level >= height) {
return false;
}
if (head != nil) {
if (level - 1 == height &&
head!.left == nil ||
head!.right == nil) {
if (head!.left == nil) {
head!.left = Node(value);
} else {
head!.right = Node(value);
}
self.arrange_node(head);
return true;
}
if (self.add_node(head!.left, height, level + 1, value) ||
self.add_node(head!.right, height, level + 1, value)) {
//Check effect of new inserted node
self.arrange_node(head);
return true;
}
}
return false;
}
//Handles the request to new inserting node
func insert(_ value: Int) {
if (self.root == nil) {
self.root = Node(value);
} else
if (self.root!.left == nil) {
self.root!.left = Node(value);
self.arrange_node(self.root);
} else
if (self.root!.right == nil) {
self.root!.right = Node(value);
self.arrange_node(self.root);
} else {
let height: Int = self.tree_height();
let _ = self.add_node(self.root, height, 0, value);
}
self.size += 1;
}
func preorder(_ head: Node? ) {
if (head != nil) {
print(" ", head!.key, terminator: "");
self.preorder(head!.left);
self.preorder(head!.right);
}
}
func node_parent(_ head: Node? , _ value : Int) -> Node? {
if (head != nil) {
if (head!.left != nil &&
head!.left!.key == value ||
head!.right != nil &&
head!.right!.key == value) {
return head;
}
var element: Node? = self.node_parent(head!.left, value);
if (element == nil) {
element = self.node_parent(head!.right, value);
}
return element;
}
return head;
}
//Find last node of tree
func tree_last_node(_ head: Node? , _ height : Int, _ level: Int) -> Node? {
if (head != nil) {
if (level == height - 1 &&
(head!.left != nil ||
head!.right != nil)) {
return head;
}
var element: Node? = self.tree_last_node(head!.right, height, level + 1);
if (element == nil) {
element = self.tree_last_node(head!.left, height, level + 1);
}
return element;
}
return head;
}
func is_max_heap(_ head: Node? ) -> Bool {
if ((head!.left != nil &&
head!.left!.key > head!.key) ||
(head!.right != nil &&
head!.right!.key > head!.key)) {
return false;
}
return true;
}
func updateDeletion(_ element: Node? ) {
var find_node : Node? = element;
//Find the new changes to make new max heap
//O(long h)
while (find_node != nil) {
//Check max heap properties
if (self.is_max_heap(find_node) == false) {
//fail max heap
if (find_node!.left != nil &&
find_node!.right != nil) {
//Repace data with maximum value
if (find_node!.left!.key > find_node!.right!.key) {
self.swap_node(find_node, find_node!.left);
find_node = find_node!.left;
} else {
self.swap_node(find_node, find_node!.right);
find_node = find_node!.right;
}
} else
if (find_node!.right != nil) {
self.swap_node(find_node, find_node!.right);
find_node = find_node!.right;
} else {
self.swap_node(find_node, find_node!.left);
find_node = find_node!.left;
}
} else {
break;
}
}
}
func delete_node(_ value: Int) {
if (self.root != nil) {
var height: Int = 0;
var find_node: Node? = nil;
var last_root: Node? = nil;
if (self.root!.key == value) {
if (self.root!.left == nil &&
self.root!.right == nil) {
//Delete root node
self.root = nil;
} else
if (self.root!.key == value &&
self.root!.right == nil) {
//Only two node in max heap
find_node = self.root;
self.root = self.root!.left;
find_node = nil;
} else {
//Find the max height by using tree node size
height = self.tree_height();
if ((1 << height) - 1 == self.size) {
//in case given height is a perfect of all leaf
height -= 1;
}
//Find parent of a last node of tree
last_root = self.tree_last_node(self.root, height, 0);
if (last_root != nil) {
//updtae key value
if (last_root!.right != nil) {
self.root!.key = last_root!.right!.key;
//remove last node
last_root!.right = nil;
} else {
self.root!.key = last_root!.left!.key;
//remove last node
last_root!.left = nil;
}
self.updateDeletion(self.root);
}
}
print("\nDelete Node key : ", value ,"\n", terminator: "");
self.preorder(self.root);
//modify tree node size
self.size -= 1;
} else {
//When root node is not a part of delete node
//Find parent of a delete node key
find_node = self.node_parent(self.root, value);
if (find_node == nil) {
//In case delete node not exist
print("\nDelete key ", value ," not exist ", terminator: "");
} else {
//Find the max height by using tree node size
height = self.tree_height();
if ((1 << height) - 1 == self.size) {
//In case given height is a same of all leaf
height -= 1;
}
//Find parent of a last node of tree
last_root = self.tree_last_node(self.root, height, 0);
if (last_root != nil) {
if (last_root === find_node) {
//When delete last node
if (last_root!.right != nil &&
last_root!.right!.key == value) {
last_root!.right = nil;
} else
if (last_root!.left != nil &&
last_root!.left!.key == value) {
if (last_root!.right != nil) {
self.swap_node(last_root!.right, last_root!.left);
last_root!.right = nil;
} else {
last_root!.left = nil;
}
}
} else {
//Get actual delete node location
if (find_node!.right != nil &&
find_node!.right!.key == value) {
find_node = find_node!.right;
} else {
find_node = find_node!.left;
}
//Updtae key value
if (last_root!.right != nil) {
find_node!.key = last_root!.right!.key;
//remove last node
last_root!.right = nil;
} else {
find_node!.key = last_root!.left!.key;
//remove last node
last_root!.left = nil;
}
}
self.updateDeletion(find_node);
print("\nDelete Node key : ", value ,"\n", terminator: "");
self.preorder(self.root);
//modify tree node size
self.size -= 1;
}
}
}
} else {
print("Empty max heap\n", terminator: "");
}
}
}
func main() {
let obj: MaxHeap = MaxHeap();
//Construct first max heap tree
obj.insert(5);
obj.insert(7);
obj.insert(4);
obj.insert(3);
obj.insert(9);
obj.insert(14);
obj.insert(2);
obj.insert(1);
obj.insert(6);
obj.insert(11);
/*After insert element*/
/*
14
/ \
11 9
/ \ / \
6 7 4 2
/ \ /
1 3 5
*/
//preorder 14 11 6 1 3 7 5 9 4 2
obj.preorder(obj.root);
obj.delete_node(1);
/*
when delete node 1
14
/ \
11 9
/ \ / \
6 7 4 2
/ \
5 3
*/
obj.delete_node(2);
/*
when delete node 2
14
/ \
11 9
/ \ / \
6 7 4 3
/
5
*/
obj.delete_node(4);
/*
when delete node 4
14
/ \
11 9
/ \ / \
6 7 5 3
*/
obj.delete_node(14);
/*
when delete node 14
First make last node as root
3
/ \
11 9
/ \ /
6 7 5
//update node value
11
/ \
7 9
/ \ /
6 3 5
*/
//when node are not exist
obj.delete_node(15);
}
main();
Output
14 11 6 1 3 7 5 9 4 2
Delete Node key : 1
14 11 6 5 3 7 9 4 2
Delete Node key : 2
14 11 6 5 7 9 4 3
Delete Node key : 4
14 11 6 7 9 5 3
Delete Node key : 14
11 7 6 3 9 5
Delete key 15 not exist
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment