Node deletion in K dimensional tree
Here given code implementation process.
// C program for
// Node deletion in K dimensional tree
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
// Define tree node
struct TreeNode
{
int *keys;
struct TreeNode *left;
struct TreeNode *right;
};
struct KTree
{
int k;
struct TreeNode *root;
};
// Returns the new K Dimensional Tree
struct KTree *createTree(int k)
{
struct KTree *tree = (struct KTree *) malloc(sizeof(struct KTree));
if (tree != NULL)
{
tree->k = k;
tree->root = NULL;
}
else
{
printf("\n Memory Overflow when create new Tree");
}
}
// Creating and returning new node of tree
struct TreeNode *createNode(int data[], int k)
{
struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
// Create memory of node key
node->keys = (int *) malloc((sizeof(int)) *(2));
node->left = NULL;
node->right = NULL;
for (int i = 0; i < k; i++)
{
node->keys[i] = data[i];
}
}
else
{
printf("\n Memory Overflow when create new node Tree");
}
return node;
}
// Handles the request to add new node in Tree
void insert(struct KTree *tree, int data[])
{
if (tree->root == NULL)
{
// When add first node of tree
tree->root = createNode(data, tree->k);
}
else
{
struct TreeNode *auxiliary = tree->root;
int depth = 0;
int axis = 0;
// Add new node in tree
while (auxiliary != NULL)
{
axis = depth % tree->k;
if (auxiliary->keys[axis] > data[axis])
{
if (auxiliary->left == NULL)
{
// Add new node
auxiliary->left = createNode(data, tree->k);
// break the loop
auxiliary = NULL;
}
else
{
// visit left subtree
auxiliary = auxiliary->left;
}
}
else
{
if (auxiliary->right == NULL)
{
// Add new node
auxiliary->right = createNode(data, tree->k);
// break the loop
auxiliary = NULL;
}
else
{
// visit right subtree
auxiliary = auxiliary->right;
}
}
depth++;
}
}
}
// Print the all key of a given node
void printData(int data[], int k)
{
printf(" (");
for (int i = 0; i < k; ++i)
{
if (i > 0)
{
printf(" , %d", data[i]);
}
else
{
printf(" %d", data[i]);
}
}
printf(")\n");
}
// Display tree node
void printTree(struct TreeNode *node, int k)
{
if (node != NULL)
{
printTree(node->left, k);
printData(node->keys, k);
printTree(node->right, k);
}
}
// Compare node and given point
int isEquals(int node[], int point[], int k)
{
for (int i = 0; i < k; ++i)
{
if (node[i] != point[i])
{
return 0;
}
}
// When both are same
return 1;
}
// return the minimum node by using of given dimension
struct TreeNode * minPoint( struct TreeNode *node1,
struct TreeNode *node2,
int dim)
{
if(node1==NULL)
{
// When node 1 empty
return node2;
}
if(node2 == NULL)
{
// When node 2 empty
return node1;
}
if(node1->keys[dim] < node2->keys[dim])
{
// Node 1 is smaller
return node1;
}
// Node 2 is smaller
return node2;
}
// Recursively finding the minimum of given dimension
struct TreeNode * findMinimum(struct TreeNode *node, int dim, int k, int depth)
{
if (node == NULL)
{
// When get a null Node
return NULL;
}
// Get dimension position
int position = depth % k;
if (position == dim)
{
// When position are equal to given a dimension
if (node->left == NULL)
{
// Returns the current dimension
return node;
}
return minPoint(node,
findMinimum(node->left, dim, k, depth + 1),dim);
}
// When position are equal to given a dimension
// Then resultant node can be exists in left or right subtree
return minPoint(node,
minPoint(findMinimum(node->left, dim, k, depth + 1),
findMinimum(node->right, dim, k, depth + 1),dim),dim);
}
// Handles the request of find minimum point using given dimensions
void minimum(struct KTree *tree, int dim)
{
if (tree->root == NULL)
{
printf("\n Empty Tree");
}
else if (dim < 0 || dim + 1 > tree->k)
{
printf("\n Given dimensions are not valid ");
}
else
{
struct TreeNode*n = findMinimum(tree->root, dim, tree->k, 0);
printf("\n Given Dimension : %d", dim);
if(n != NULL)
{
printf("\n Minimum is : %d", n->keys[dim]);
}
}
}
// Copy node 2 value into node1
void copyData(int node1[], int node2[], int k)
{
for (int i=0; i < k; i++)
{
node1[i] = node2[i];
}
}
// Handles the request of remove given point node in tree
struct TreeNode *removeNode(
struct TreeNode *node,
int k,
int point[],
int depth)
{
if (node == NULL)
{
return NULL;
}
int dim = depth % k;
if (isEquals(node->keys, point,k))
{
// When current node is same as deleted point
// Here are three possibility
if (node->right != NULL)
{
// Case 1 : When right subtree not NULL
// Then find minimum node point and replace by current node
struct TreeNode *min = findMinimum(node->right, dim, k, 0);
// minimum point replace by current node
copyData(node->keys, min->keys, k);
// Recursively find new minimum deleted point
node->right = removeNode(node->right,k, min->keys, depth+1);
}
else if (node->left != NULL)
{
// Case 2 : When current node left subtree not Empty
// Then find minimum node point in left subtree and
// replace by current node
struct TreeNode *min = findMinimum(node->left, dim,k, 0);
// minimum point replace by current node
copyData(node->keys, min->keys, k);
// Recursively find new minimum deleted point
node->right = removeNode(node->left,k, min->keys, depth+1);
}
else
{
// Case 3 : When current node is leaf node
// Then remove it
free(node);
return NULL;
}
return node;
}
// Choose the left and right subtree by using given point
if ( node->keys[dim] > point[dim] )
{
node->left = removeNode(node->left,k, point, depth+1);
}
else
{
node->right = removeNode(node->right,k, point, depth+1);
}
return node;
}
// Handles the request to delete given point in tree
void deleteNode(struct KTree *tree, int point[])
{
if (tree->root == NULL)
{
printf("\n Empty Tree");
return;
}
printf("\n Remove point \n");
printData(point,tree->k);
// Assuming that the given point length is equal to the tree node keys
tree->root = removeNode(tree->root, tree->k, point, 0);
}
int main(int argc, char
const *argv[])
{
// Number of Dimensions
int k = 2;
struct KTree *tree = createTree(k);
// 2d points
int data[][2] = {
{
8 , 9
},
{
7 , 6
},
{
3 , 9
},
{
11 , 12
},
{
2 , 8
},
{
9 , 4
},
{
10 , 13
},
{
14 , 8
}
};
// Remove node points
int point1[] = {7,6};
int point2[] = {8,9};
// Get the number of elements
int n = sizeof(data) / sizeof(data[0]);
// Insert all given nodes
for (int i = 0; i < n; ++i)
{
insert(tree, data[i]);
}
printf("\n Before Delete Tree Nodes\n");
/*
(8, 9)
/ \
(7,6) (11,12)
\ / \
(3,9)(9,4) (10,13)
/ \
(2,8) (14,8)
-----------------
Developed tree
*/
// Print tree elements in inorder form
printTree(tree->root, tree->k);
// Case 1
deleteNode(tree,point1);
/*
(8, 9)
/ \
(2,8) (11,12)
\ / \
(3,9)(9,4) (10,13)
\
(14,8)
-----------------
After Remove (7,6)
*/
printf("\n After Delete Tree Nodes\n");
// Print tree elements in inorder form
printTree(tree->root, tree->k);
// Case 2
deleteNode(tree,point2);
/*
(9, 4)
/ \
(2,8) (11,12)
\ / \
(3,9)(14,8) (10,13)
-----------------
After Remove (8, 9)
*/
printf("\n After Delete Tree Nodes\n");
// Print tree elements in inorder form
printTree(tree->root, tree->k);
return 0;
}
Output
Before Delete Tree Nodes
( 7 , 6)
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 7 , 6)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 8 , 9)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
// Java Program
// Node deletion in K dimensional tree
// Define tree node
class TreeNode
{
public int []keys;
public TreeNode left;
public TreeNode right;
public TreeNode(int[] data,int k)
{
this.keys = new int[k];
this.left = null;
this.right = null;
for (int i = 0; i < k; ++i)
{
this.keys[i] = data[i];
}
}
}
public class KTree
{
public int k;
public TreeNode root;
public KTree(int k)
{
this.k = k;
this.root = null;
}
// Handles the request to add new node in Tree
public void insert(int[] data)
{
if (this.root == null)
{
// When add first node of tree
this.root = new TreeNode(data, this.k);
}
else
{
TreeNode auxiliary = this.root;
int depth = 0;
int axis = 0;
// Add new node in tree
while (auxiliary != null)
{
axis = depth % this.k;
if (auxiliary.keys[axis] > data[axis])
{
if (auxiliary.left == null)
{
// Add new node
auxiliary.left = new TreeNode(data, this.k);
// break the loop
auxiliary = null;
}
else
{
// visit left subtree
auxiliary = auxiliary.left;
}
}
else
{
if (auxiliary.right == null)
{
// Add new node
auxiliary.right = new TreeNode(data, this.k);
// break the loop
auxiliary = null;
}
else
{
// visit right subtree
auxiliary = auxiliary.right;
}
}
depth++;
}
}
}
// Print the all key of a given node
public void printData(int[] data)
{
System.out.print(" (");
for (int i = 0; i < this.k; ++i)
{
if (i > 0)
{
System.out.print(" , " + data[i] );
}
else
{
System.out.print(" " + data[i] );
}
}
System.out.print(")\n");
}
// Display tree node
public void printTree(TreeNode node)
{
if (node != null)
{
printTree(node.left);
printData(node.keys);
printTree(node.right);
}
}
// Compare node and given point
public boolean isEquals(int[] node, int[] point)
{
for (int i = 0; i < this.k; ++i)
{
if (node[i] != point[i])
{
return false;
}
}
// When both are same
return true;
}
// return the minimum node by using of given dimension
public TreeNode minPoint(TreeNode node1, TreeNode node2, int dim)
{
if (node1 == null)
{
// When node 1 empty
return node2;
}
if (node2 == null)
{
// When node 2 empty
return node1;
}
if (node1.keys[dim] < node2.keys[dim])
{
// Node 1 is smaller
return node1;
}
// Node 2 is smaller
return node2;
}
// Recursively finding the minimum of given dimension
public TreeNode findMinimum(TreeNode node, int dim, int depth)
{
if (node == null)
{
// When get a null Node
return null;
}
// Get dimension position
int position = depth % k;
if (position == dim)
{
// When position are equal to given a dimension
if (node.left == null)
{
// Returns the current dimension
return node;
}
return minPoint(node,
findMinimum(node.left, dim, depth + 1), dim);
}
// When position are equal to given a dimension
// Then resultant node can be exists in left or right subtree
return minPoint(node, minPoint(
findMinimum(node.left, dim, depth + 1),
findMinimum(node.right, dim, depth + 1), dim), dim);
}
// Handles the request of find minimum point using given dimensions
public void minimum(int dim)
{
if (this.root == null)
{
System.out.print("\n Empty Tree");
}
else if (dim < 0 || dim + 1 > this.k)
{
System.out.print("\n Given dimensions are not valid ");
}
else
{
TreeNode n = findMinimum(this.root, dim, 0);
System.out.print("\n Given Dimension : " + dim );
if (n != null)
{
System.out.print("\n Minimum is : " + n.keys[dim] );
}
}
}
// Copy node 2 value into node1
public void copyData(int[] node1, int[] node2)
{
for (int i = 0; i < this.k; i++)
{
node1[i] = node2[i];
}
}
// Handles the request of remove given point node in tree
public TreeNode removeNode(TreeNode node, int[] point, int depth)
{
if (node == null)
{
System.out.println("Point not exist");
return null;
}
int dim = depth % this.k;
if (isEquals(node.keys, point))
{
// When current node is same as deleted point
// Here are three possibility
if (node.right != null)
{
// Case 1 : When right subtree not NULL
// Then find minimum node point and replace by current node
TreeNode min = findMinimum(node.right, dim, 0);
// minimum point replace by current node
copyData(node.keys, min.keys);
// Recursively find new minimum deleted point
node.right = removeNode(node.right, min.keys, depth + 1);
}
else if (node.left != null)
{
// Case 2 : When current node left subtree not Empty
// Then find minimum node point in left subtree and
// replace by current node
TreeNode min = findMinimum(node.left, dim, 0);
// minimum point replace by current node
copyData(node.keys, min.keys);
// Recursively find new minimum deleted point
node.right = removeNode(node.left, min.keys, depth + 1);
}
else
{
// Case 3 : When current node is leaf node
// Then remove it
node = null;
return null;
}
return node;
}
// Choose the left and right subtree by using given point
if (node.keys[dim] > point[dim])
{
node.left = removeNode(node.left, point, depth + 1);
}
else
{
node.right = removeNode(node.right, point, depth + 1);
}
return node;
}
// Handles the request to delete given point in tree
public void deleteNode( int[] point)
{
if (this.root == null)
{
System.out.print("\n Empty Tree");
return;
}
System.out.print("\n Remove point \n");
printData(point);
// Assuming that the given point length is equal to the tree node keys
this.root = removeNode(this.root, point, 0);
}
public static void main(String[] args)
{
int k = 2;
KTree tree = new KTree(k);
// 2d points
int[][] data = {
{
8 , 9
},
{
7 , 6
},
{
3 , 9
},
{
11 , 12
},
{
2 , 8
},
{
9 , 4
},
{
10 , 13
},
{
14 , 8
}
};
// Remove node points
int[] point1 = {
7 , 6
};
int[] point2 = {
8 , 9
};
// Get the number of elements
int n = data.length;
// Insert all given nodes
for (int i = 0; i < n; ++i)
{
tree.insert(data[i]);
}
System.out.print("\n Tree Nodes\n");
/*
(8, 9)
/ \
(7,6) (11,12)
\ / \
(3,9)(9,4) (10,13)
/ \
(2,8) (14,8)
-----------------
Developed tree
*/
// Print tree elements in inorder form
tree.printTree(tree.root);
// Case 1
tree.deleteNode( point1);
/*
(8, 9)
/ \
(2,8) (11,12)
\ / \
(3,9)(9,4) (10,13)
\
(14,8)
-----------------
After Remove (7,6)
*/
System.out.print("\n After Delete Tree Nodes\n");
// Print tree elements in inorder form
tree.printTree(tree.root);
// Case 2
tree.deleteNode(point2);
/*
(9, 4)
/ \
(2,8) (11,12)
\ / \
(3,9)(14,8) (10,13)
-----------------
After Remove (8, 9)
*/
System.out.print("\n After Delete Tree Nodes\n");
// Print tree elements in inorder form
tree.printTree(tree.root);
}
}
Output
Tree Nodes
( 7 , 6)
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 7 , 6)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 8 , 9)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Node deletion in K dimensional tree
// Define tree node
class TreeNode
{
public:
int *keys;
TreeNode *left;
TreeNode *right;
TreeNode(int data[], int k)
{
this->keys = new int[k];
this->left = NULL;
this->right = NULL;
for (int i = 0; i < k; ++i)
{
this->keys[i] = data[i];
}
}
};
class KTree
{
public: int k;
TreeNode *root;
KTree(int k)
{
this->k = k;
this->root = NULL;
}
// Handles the request to add new node in Tree
void insert(int data[])
{
if (this->root == NULL)
{
// When add first node of tree
this->root = new TreeNode(data, this->k);
}
else
{
TreeNode *auxiliary = this->root;
int depth = 0;
int axis = 0;
// Add new node in tree
while (auxiliary != NULL)
{
axis = depth % this->k;
if (auxiliary->keys[axis] > data[axis])
{
if (auxiliary->left == NULL)
{
// Add new node
auxiliary->left = new TreeNode(data, this->k);
// break the loop
auxiliary = NULL;
}
else
{
// visit left subtree
auxiliary = auxiliary->left;
}
}
else
{
if (auxiliary->right == NULL)
{
// Add new node
auxiliary->right = new TreeNode(data, this->k);
// break the loop
auxiliary = NULL;
}
else
{
// visit right subtree
auxiliary = auxiliary->right;
}
}
depth++;
}
}
}
// Print the all key of a given node
void printData(int data[])
{
cout << " (";
for (int i = 0; i < this->k; ++i)
{
if (i > 0)
{
cout << " , " << data[i];
}
else
{
cout << " " << data[i];
}
}
cout << ")\n";
}
// Display tree node
void printTree(TreeNode *node)
{
if (node != NULL)
{
this->printTree(node->left);
this->printData(node->keys);
this->printTree(node->right);
}
}
// Compare node and given point
bool isEquals(int node[], int point[])
{
// When both are same
for (int i = 0; i < this->k; ++i)
{
if (node[i] != point[i])
{
return false;
}
}
return true;
}
// return the minimum node by using of given dimension
TreeNode *minPoint(TreeNode *node1, TreeNode *node2, int dim)
{
// Node 2 is smaller
if (node1 == NULL)
{
// When node 1 empty
return node2;
}
if (node2 == NULL)
{
// When node 2 empty
return node1;
}
if (node1->keys[dim] < node2->keys[dim])
{
// Node 1 is smaller
return node1;
}
return node2;
}
// Recursively finding the minimum of given dimension
TreeNode *findMinimum(TreeNode *node, int dim, int depth)
{
if (node == NULL)
{
// When get a null Node
return NULL;
}
// Get dimension position
int position = depth % this->k;
if (position == dim)
{
// When position are equal to given a dimension
if (node->left == NULL)
{
// Returns the current dimension
return node;
}
return this->minPoint(node,
this->findMinimum(node->left, dim, depth + 1), dim);
}
// When position are equal to given a dimension
// Then resultant node can be exists in left or right subtree
return this->minPoint(node,
this->minPoint(this->findMinimum(node->left, dim, depth + 1),
this->findMinimum(node->right, dim, depth + 1), dim), dim);
}
// Handles the request of find minimum point using given dimensions
void minimum(int dim)
{
if (this->root == NULL)
{
cout << "\n Empty Tree";
}
else if (dim < 0 || dim + 1 > this->k)
{
cout << "\n Given dimensions are not valid ";
}
else
{
TreeNode *n = this->findMinimum(this->root, dim, 0);
cout << "\n Given Dimension : " << dim;
if (n != NULL)
{
cout << "\n Minimum is : " << n->keys[dim];
}
}
}
// Copy node 2 value into node1
void copyData(int node1[], int node2[])
{
for (int i = 0; i < this->k; i++)
{
node1[i] = node2[i];
}
}
// Handles the request of remove given point node in tree
TreeNode *removeNode(TreeNode *node, int point[], int depth)
{
if (node == NULL)
{
cout << "Point not exist";
return NULL;
}
int dim = depth % this->k;
if (this->isEquals(node->keys, point))
{
// When current node is same as deleted point
// Here are three possibility
if (node->right != NULL)
{
// Case 1 : When right subtree not NULL
// Then find minimum node point and replace by current node
TreeNode *min = this->findMinimum(node->right, dim, 0);
// minimum point replace by current node
this->copyData(node->keys, min->keys);
// Recursively find new minimum deleted point
node->right = this->removeNode(node->right, min->keys, depth + 1);
}
else if (node->left != NULL)
{
// Case 2 : When current node left subtree not Empty
// Then find minimum node point in left subtree and
// replace by current node
TreeNode *min = this->findMinimum(node->left, dim, 0);
// minimum point replace by current node
this->copyData(node->keys, min->keys);
// Recursively find new minimum deleted point
node->right = this->removeNode(node->left, min->keys, depth + 1);
}
else
{
// Case 3 : When current node is leaf node
// Then remove it
delete node;
node = NULL;
}
return node;
}
// Choose the left and right subtree by using given point
if (node->keys[dim] > point[dim])
{
node->left = this->removeNode(node->left, point, depth + 1);
}
else
{
node->right = this->removeNode(node->right, point, depth + 1);
}
return node;
}
// Handles the request to delete given point in tree
void deleteNode(int point[])
{
if (this->root == NULL)
{
cout << "\n Empty Tree";
return;
}
cout << "\n Remove point \n";
this->printData(point);
// Assuming that the given point length is equal to the tree node keys
this->root = this->removeNode(this->root, point, 0);
}
};
int main()
{
int k = 2;
KTree tree = KTree(k);
// 2d points
int data[][2] = {
{
8 , 9
} , {
7 , 6
} , {
3 , 9
} , {
11 , 12
} , {
2 , 8
} , {
9 , 4
} , {
10 , 13
} , {
14 , 8
}
};
// Remove node points
int point1[] = {
7 , 6
};
int point2[] = {
8 , 9
};
// Get the number of elements
int n = sizeof(data) / sizeof(data[0]);
// Insert all given nodes
for (int i = 0; i < n; ++i)
{
tree.insert(data[i]);
}
cout << "\n Tree Nodes\n";
/*
(8, 9)
/ \
(7,6) (11,12)
\ / \
(3,9)(9,4) (10,13)
/ \
(2,8) (14,8)
-----------------
Developed tree
*/
// Print tree elements in inorder form
tree.printTree(tree.root);
// Case 1
tree.deleteNode(point1);
/*
(8, 9)
/ \
(2,8) (11,12)
\ / \
(3,9)(9,4) (10,13)
\
(14,8)
-----------------
After Remove (7,6)
*/
cout << "\n After Delete Tree Nodes\n";
// Print tree elements in inorder form
tree.printTree(tree.root);
// Case 2
tree.deleteNode(point2);
/*
(9, 4)
/ \
(2,8) (11,12)
\ / \
(3,9)(14,8) (10,13)
-----------------
After Remove (8, 9)
*/
cout << "\n After Delete Tree Nodes\n";
// Print tree elements in inorder form
tree.printTree(tree.root);
return 0;
}
Output
Tree Nodes
( 7 , 6)
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 7 , 6)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 8 , 9)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
// Include namespace system
using System;
using System.Collections;
using System.Linq;
// C# Program
// Node deletion in K dimensional tree
// Define tree node
public class TreeNode
{
public int[] keys;
public TreeNode left;
public TreeNode right;
public TreeNode(int[] data, int k)
{
this.keys = new int[k];
this.left = null;
this.right = null;
for (int i = 0; i < k; ++i)
{
this.keys[i] = data[i];
}
}
}
public class KTree
{
public int k;
public TreeNode root;
public KTree(int k)
{
this.k = k;
this.root = null;
}
// Handles the request to add new node in Tree
public void insert(int[] data)
{
if (this.root == null)
{
// When add first node of tree
this.root = new TreeNode(data, this.k);
}
else
{
TreeNode auxiliary = this.root;
int depth = 0;
int axis = 0;
// Add new node in tree
while (auxiliary != null)
{
axis = depth % this.k;
if (auxiliary.keys[axis] > data[axis])
{
if (auxiliary.left == null)
{
// Add new node
auxiliary.left = new TreeNode(data, this.k);
// break the loop
auxiliary = null;
}
else
{
// visit left subtree
auxiliary = auxiliary.left;
}
}
else
{
if (auxiliary.right == null)
{
// Add new node
auxiliary.right = new TreeNode(data, this.k);
// break the loop
auxiliary = null;
}
else
{
// visit right subtree
auxiliary = auxiliary.right;
}
}
depth++;
}
}
}
// Print the all key of a given node
public void printData(int[] data)
{
Console.Write(" (");
for (int i = 0; i < this.k; ++i)
{
if (i > 0)
{
Console.Write(" , " + data[i]);
}
else
{
Console.Write(" " + data[i]);
}
}
Console.Write(")\n");
}
// Display tree node
public void printTree(TreeNode node)
{
if (node != null)
{
printTree(node.left);
printData(node.keys);
printTree(node.right);
}
}
// Compare node and given point
public Boolean isEquals(int[] node, int[] point)
{
// When both are same
for (int i = 0; i < this.k; ++i)
{
if (node[i] != point[i])
{
return false;
}
}
return true;
}
// return the minimum node by using of given dimension
public TreeNode minPoint(TreeNode node1, TreeNode node2, int dim)
{
// Node 2 is smaller
if (node1 == null)
{
// When node 1 empty
return node2;
}
if (node2 == null)
{
// When node 2 empty
return node1;
}
if (node1.keys[dim] < node2.keys[dim])
{
// Node 1 is smaller
return node1;
}
return node2;
}
// Recursively finding the minimum of given dimension
public TreeNode findMinimum(TreeNode node, int dim, int depth)
{
if (node == null)
{
// When get a null Node
return null;
}
// Get dimension position
int position = depth % k;
if (position == dim)
{
// When position are equal to given a dimension
if (node.left == null)
{
// Returns the current dimension
return node;
}
return minPoint(node, findMinimum(node.left, dim, depth + 1), dim);
}
// When position are equal to given a dimension
// Then resultant node can be exists in left or right subtree
return minPoint(node, minPoint(findMinimum(node.left, dim, depth + 1), findMinimum(node.right, dim, depth + 1), dim), dim);
}
// Handles the request of find minimum point using given dimensions
public void minimum(int dim)
{
if (this.root == null)
{
Console.Write("\n Empty Tree");
}
else if (dim < 0 || dim + 1 > this.k)
{
Console.Write("\n Given dimensions are not valid ");
}
else
{
TreeNode n = findMinimum(this.root, dim, 0);
Console.Write("\n Given Dimension : " + dim);
if (n != null)
{
Console.Write("\n Minimum is : " + n.keys[dim]);
}
}
}
// Copy node 2 value into node1
public void copyData(int[] node1, int[] node2)
{
for (int i = 0; i < this.k; i++)
{
node1[i] = node2[i];
}
}
// Handles the request of remove given point node in tree
public TreeNode removeNode(TreeNode node, int[] point, int depth)
{
if (node == null)
{
Console.WriteLine("Point not exist");
return null;
}
int dim = depth % this.k;
if (isEquals(node.keys, point))
{
// When current node is same as deleted point
// Here are three possibility
if (node.right != null)
{
// Case 1 : When right subtree not NULL
// Then find minimum node point and replace by current node
TreeNode min = findMinimum(node.right, dim, 0);
// minimum point replace by current node
copyData(node.keys, min.keys);
// Recursively find new minimum deleted point
node.right = removeNode(node.right, min.keys, depth + 1);
}
else if (node.left != null)
{
// Case 2 : When current node left subtree not Empty
// Then find minimum node point in left subtree and
// replace by current node
TreeNode min = findMinimum(node.left, dim, 0);
// minimum point replace by current node
copyData(node.keys, min.keys);
// Recursively find new minimum deleted point
node.right = removeNode(node.left, min.keys, depth + 1);
}
else
{
// Case 3 : When current node is leaf node
// Then remove it
node = null;
}
return node;
}
// Choose the left and right subtree by using given point
if (node.keys[dim] > point[dim])
{
node.left = removeNode(node.left, point, depth + 1);
}
else
{
node.right = removeNode(node.right, point, depth + 1);
}
return node;
}
// Handles the request to delete given point in tree
public void deleteNode(int[] point)
{
if (this.root == null)
{
Console.Write("\n Empty Tree");
return;
}
Console.Write("\n Remove point \n");
printData(point);
// Assuming that the given point length is equal to the tree node keys
this.root = removeNode(this.root, point, 0);
}
public static void Main(String[] args)
{
int k = 2;
KTree tree = new KTree(k);
// 2d points
int[,] data = {
{
8 , 9
} ,
{
7 , 6
} ,
{
3 , 9
} ,
{
11 , 12
} ,
{
2 , 8
} ,
{
9 , 4
} ,
{
10 , 13
} ,
{
14 , 8
}
};
// Remove node points
int[] point1 = {
7 , 6
};
int[] point2 = {
8 , 9
};
// Get the number of elements
int n = data.GetLength(0);
// Insert all given nodes
for (int i = 0; i < n; ++i)
{
tree.insert(Enumerable.Range(0, data.GetLength(1))
.Select(x => data[i, x])
.ToArray());
}
Console.Write("\n Tree Nodes\n");
/*
(8, 9)
/ \
(7,6) (11,12)
\ / \
(3,9)(9,4) (10,13)
/ \
(2,8) (14,8)
-----------------
Developed tree
*/
// Print tree elements in inorder form
tree.printTree(tree.root);
// Case 1
tree.deleteNode(point1);
/*
(8, 9)
/ \
(2,8) (11,12)
\ / \
(3,9)(9,4) (10,13)
\
(14,8)
-----------------
After Remove (7,6)
*/
Console.Write("\n After Delete Tree Nodes\n");
// Print tree elements in inorder form
tree.printTree(tree.root);
// Case 2
tree.deleteNode(point2);
/*
(9, 4)
/ \
(2,8) (11,12)
\ / \
(3,9)(14,8) (10,13)
-----------------
After Remove (8, 9)
*/
Console.Write("\n After Delete Tree Nodes\n");
// Print tree elements in inorder form
tree.printTree(tree.root);
}
}
Output
Tree Nodes
( 7 , 6)
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 7 , 6)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 8 , 9)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
<?php
// Php Program
// Node deletion in K dimensional tree
// Define tree node
class TreeNode
{
public $keys;
public $left;
public $right;
function __construct( & $data, $k)
{
$this->keys = array_fill(0, $k, 0);
$this->left = null;
$this->right = null;
for ($i = 0; $i < $k; ++$i)
{
$this->keys[$i] = $data[$i];
}
}
}
class KTree
{
public $k;
public $root;
function __construct($k)
{
$this->k = $k;
$this->root = null;
}
// Handles the request to add new node in Tree
public function insert( & $data)
{
if ($this->root == null)
{
// When add first node of tree
$this->root = new TreeNode($data, $this->k);
}
else
{
$auxiliary = $this->root;
$depth = 0;
$axis = 0;
// Add new node in tree
while ($auxiliary != null)
{
$axis = $depth % $this->k;
if ($auxiliary->keys[$axis] > $data[$axis])
{
if ($auxiliary->left == null)
{
// Add new node
$auxiliary->left = new TreeNode($data, $this->k);
// break the loop
$auxiliary = null;
}
else
{
// visit left subtree
$auxiliary = $auxiliary->left;
}
}
else
{
if ($auxiliary->right == null)
{
// Add new node
$auxiliary->right = new TreeNode($data, $this->k);
// break the loop
$auxiliary = null;
}
else
{
// visit right subtree
$auxiliary = $auxiliary->right;
}
}
$depth++;
}
}
}
// Print the all key of a given node
public function printData( & $data)
{
echo " (";
for ($i = 0; $i < $this->k; ++$i)
{
if ($i > 0)
{
echo " , ". $data[$i];
}
else
{
echo " ". $data[$i];
}
}
echo ")\n";
}
// Display tree node
public function printTree($node)
{
if ($node != null)
{
$this->printTree($node->left);
$this->printData($node->keys);
$this->printTree($node->right);
}
}
// Compare node and given point
public function isEquals( & $node, & $point)
{
// When both are same
for ($i = 0; $i < $this->k; ++$i)
{
if ($node[$i] != $point[$i])
{
return false;
}
}
return true;
}
// return the minimum node by using of given dimension
public function minPoint($node1, $node2, $dim)
{
// Node 2 is smaller
if ($node1 == null)
{
// When node 1 empty
return $node2;
}
if ($node2 == null)
{
// When node 2 empty
return $node1;
}
if ($node1->keys[$dim] < $node2->keys[$dim])
{
// Node 1 is smaller
return $node1;
}
return $node2;
}
// Recursively finding the minimum of given dimension
public function findMinimum($node, $dim, $depth)
{
if ($node == null)
{
// When get a null Node
return null;
}
// Get dimension position
$position = $depth % $this->k;
if ($position == $dim)
{
// When position are equal to given a dimension
if ($node->left == null)
{
// Returns the current dimension
return $node;
}
return $this->minPoint($node, $this->findMinimum($node->left, $dim, $depth + 1), $dim);
}
// When position are equal to given a dimension
// Then resultant node can be exists in left or right subtree
return $this->minPoint($node, $this->minPoint($this->findMinimum($node->left, $dim, $depth + 1), $this->findMinimum($node->right, $dim, $depth + 1), $dim), $dim);
}
// Handles the request of find minimum point using given dimensions
public function minimum($dim)
{
if ($this->root == null)
{
echo "\n Empty Tree";
}
else if ($dim < 0 || $dim + 1 > $this->k)
{
echo "\n Given dimensions are not valid ";
}
else
{
$n = $this->findMinimum($this->root, $dim, 0);
echo "\n Given Dimension : ". $dim;
if ($n != null)
{
echo "\n Minimum is : ". $n->keys[$dim];
}
}
}
// Copy node 2 value into node1
public function copyData( & $node1, & $node2)
{
for ($i = 0; $i < $this->k; $i++)
{
$node1[$i] = $node2[$i];
}
}
// Handles the request of remove given point node in tree
public function removeNode($node, & $point, $depth)
{
if ($node == null)
{
echo "Point not exist";
return null;
}
$dim = $depth % $this->k;
if ($this->isEquals($node->keys, $point))
{
// When current node is same as deleted point
// Here are three possibility
if ($node->right != null)
{
// Case 1 : When right subtree not NULL
// Then find minimum node point and replace by current node
$min = $this->findMinimum($node->right, $dim, 0);
// minimum point replace by current node
$this->copyData($node->keys, $min->keys);
// Recursively find new minimum deleted point
$node->right = $this->removeNode($node->right, $min->keys, $depth + 1);
}
else if ($node->left != null)
{
// Case 2 : When current node left subtree not Empty
// Then find minimum node point in left subtree and
// replace by current node
$min = $this->findMinimum($node->left, $dim, 0);
// minimum point replace by current node
$this->copyData($node->keys, $min->keys);
// Recursively find new minimum deleted point
$node->right = $this->removeNode($node->left, $min->keys, $depth + 1);
}
else
{
// Case 3 : When current node is leaf node
// Then remove it
$node = null;
}
return $node;
}
// Choose the left and right subtree by using given point
if ($node->keys[$dim] > $point[$dim])
{
$node->left = $this->removeNode($node->left, $point, $depth + 1);
}
else
{
$node->right = $this->removeNode($node->right, $point, $depth + 1);
}
return $node;
}
// Handles the request to delete given point in tree
public function deleteNode( & $point)
{
if ($this->root == null)
{
echo "\n Empty Tree";
return;
}
echo "\n Remove point \n";
$this->printData($point);
// Assuming that the given point length is equal to the tree node keys
$this->root = $this->removeNode($this->root, $point, 0);
}
}
function main()
{
$k = 2;
$tree = new KTree($k);
// 2d points
$data = array(array(8, 9), array(7, 6), array(3, 9), array(11, 12), array(2, 8), array(9, 4), array(10, 13), array(14, 8));
// Remove node points
$point1 = array(7, 6);
$point2 = array(8, 9);
// Get the number of elements
$n = count($data);
// Insert all given nodes
for ($i = 0; $i < $n; ++$i)
{
$tree->insert($data[$i]);
}
echo "\n Tree Nodes\n";
$tree->printTree($tree->root);
$tree->deleteNode($point1);
/*
(8, 9)
/ \
(2,8) (11,12)
\ / \
(3,9)(9,4) (10,13)
\
(14,8)
-----------------
After Remove (7,6)
*/
echo "\n After Delete Tree Nodes\n";
$tree->printTree($tree->root);
$tree->deleteNode($point2);
/*
(9, 4)
/ \
(2,8) (11,12)
\ / \
(3,9)(14,8) (10,13)
-----------------
After Remove (8, 9)
*/
echo "\n After Delete Tree Nodes\n";
$tree->printTree($tree->root);
}
main();
Output
Tree Nodes
( 7 , 6)
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 7 , 6)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 8 , 9)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
// Node Js Program
// Node deletion in K dimensional tree
// Define tree node
class TreeNode
{
constructor(data, k)
{
this.keys = Array(k).fill(0);
this.left = null;
this.right = null;
for (var i = 0; i < k; ++i)
{
this.keys[i] = data[i];
}
}
}
class KTree
{
constructor(k)
{
this.k = k;
this.root = null;
}
// Handles the request to add new node in Tree
insert(data)
{
if (this.root == null)
{
// When add first node of tree
this.root = new TreeNode(data, this.k);
}
else
{
var auxiliary = this.root;
var depth = 0;
var axis = 0;
// Add new node in tree
while (auxiliary != null)
{
axis = depth % this.k;
if (auxiliary.keys[axis] > data[axis])
{
if (auxiliary.left == null)
{
// Add new node
auxiliary.left = new TreeNode(data, this.k);
// break the loop
auxiliary = null;
}
else
{
// visit left subtree
auxiliary = auxiliary.left;
}
}
else
{
if (auxiliary.right == null)
{
// Add new node
auxiliary.right = new TreeNode(data, this.k);
// break the loop
auxiliary = null;
}
else
{
// visit right subtree
auxiliary = auxiliary.right;
}
}
depth++;
}
}
}
// Print the all key of a given node
printData(data)
{
process.stdout.write(" (");
for (var i = 0; i < this.k; ++i)
{
if (i > 0)
{
process.stdout.write(" , " + data[i]);
}
else
{
process.stdout.write(" " + data[i]);
}
}
process.stdout.write(")\n");
}
// Display tree node
printTree(node)
{
if (node != null)
{
this.printTree(node.left);
this.printData(node.keys);
this.printTree(node.right);
}
}
// Compare node and given point
isEquals(node, point)
{
// When both are same
for (var i = 0; i < this.k; ++i)
{
if (node[i] != point[i])
{
return false;
}
}
return true;
}
// return the minimum node by using of given dimension
minPoint(node1, node2, dim)
{
// Node 2 is smaller
if (node1 == null)
{
// When node 1 empty
return node2;
}
if (node2 == null)
{
// When node 2 empty
return node1;
}
if (node1.keys[dim] < node2.keys[dim])
{
// Node 1 is smaller
return node1;
}
return node2;
}
// Recursively finding the minimum of given dimension
findMinimum(node, dim, depth)
{
if (node == null)
{
// When get a null Node
return null;
}
// Get dimension position
var position = depth % this.k;
if (position == dim)
{
// When position are equal to given a dimension
if (node.left == null)
{
// Returns the current dimension
return node;
}
return this.minPoint(node, this.findMinimum(node.left, dim, depth + 1), dim);
}
// When position are equal to given a dimension
// Then resultant node can be exists in left or right subtree
return this.minPoint(node, this.minPoint(this.findMinimum(node.left, dim, depth + 1), this.findMinimum(node.right, dim, depth + 1), dim), dim);
}
// Handles the request of find minimum point using given dimensions
minimum(dim)
{
if (this.root == null)
{
process.stdout.write("\n Empty Tree");
}
else if (dim < 0 || dim + 1 > this.k)
{
process.stdout.write("\n Given dimensions are not valid ");
}
else
{
var n = this.findMinimum(this.root, dim, 0);
process.stdout.write("\n Given Dimension : " + dim);
if (n != null)
{
process.stdout.write("\n Minimum is : " + n.keys[dim]);
}
}
}
// Copy node 2 value into node1
copyData(node1, node2)
{
for (var i = 0; i < this.k; i++)
{
node1[i] = node2[i];
}
}
// Handles the request of remove given point node in tree
removeNode(node, point, depth)
{
if (node == null)
{
process.stdout.write("Point not exist");
return null;
}
var dim = depth % this.k;
if (this.isEquals(node.keys, point))
{
// When current node is same as deleted point
// Here are three possibility
if (node.right != null)
{
// Case 1 : When right subtree not NULL
// Then find minimum node point and replace by current node
var min = this.findMinimum(node.right, dim, 0);
// minimum point replace by current node
this.copyData(node.keys, min.keys);
// Recursively find new minimum deleted point
node.right = this.removeNode(node.right, min.keys, depth + 1);
}
else if (node.left != null)
{
// Case 2 : When current node left subtree not Empty
// Then find minimum node point in left subtree and
// replace by current node
var min = this.findMinimum(node.left, dim, 0);
// minimum point replace by current node
this.copyData(node.keys, min.keys);
// Recursively find new minimum deleted point
node.right = this.removeNode(node.left, min.keys, depth + 1);
}
else
{
// Case 3 : When current node is leaf node
// Then remove it
node = null;
}
return node;
}
// Choose the left and right subtree by using given point
if (node.keys[dim] > point[dim])
{
node.left = this.removeNode(node.left, point, depth + 1);
}
else
{
node.right = this.removeNode(node.right, point, depth + 1);
}
return node;
}
// Handles the request to delete given point in tree
deleteNode(point)
{
if (this.root == null)
{
process.stdout.write("\n Empty Tree");
return;
}
process.stdout.write("\n Remove point \n");
this.printData(point);
// Assuming that the given point length is equal to the tree node keys
this.root = this.removeNode(this.root, point, 0);
}
}
function main()
{
var k = 2;
var tree = new KTree(k);
// 2d points
var data = [
[8, 9] , [7, 6] , [3, 9] , [11, 12] , [2, 8] , [9, 4] , [10, 13] , [14, 8]
];
// Remove node points
var point1 = [7, 6];
var point2 = [8, 9];
// Get the number of elements
var n = data.length;
// Insert all given nodes
for (var i = 0; i < n; ++i)
{
tree.insert(data[i]);
}
process.stdout.write("\n Tree Nodes\n");
/*
(8, 9)
/ \
(7,6) (11,12)
\ / \
(3,9)(9,4) (10,13)
/ \
(2,8) (14,8)
-----------------
Developed tree
*/
// Print tree elements in inorder form
tree.printTree(tree.root);
// Case 1
tree.deleteNode(point1);
/*
(8, 9)
/ \
(2,8) (11,12)
\ / \
(3,9)(9,4) (10,13)
\
(14,8)
-----------------
After Remove (7,6)
*/
process.stdout.write("\n After Delete Tree Nodes\n");
// Print tree elements in inorder form
tree.printTree(tree.root);
// Case 2
tree.deleteNode(point2);
/*
(9, 4)
/ \
(2,8) (11,12)
\ / \
(3,9)(14,8) (10,13)
-----------------
After Remove (8, 9)
*/
process.stdout.write("\n After Delete Tree Nodes\n");
// Print tree elements in inorder form
tree.printTree(tree.root);
}
main();
Output
Tree Nodes
( 7 , 6)
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 7 , 6)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 8 , 9)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
# Python 3 Program
# Node deletion in K dimensional tree
# Define tree node
class TreeNode :
def __init__(self, data, k) :
self.keys = [0] * (k)
self.left = None
self.right = None
i = 0
while (i < k) :
self.keys[i] = data[i]
i += 1
class KTree :
def __init__(self, k) :
self.k = k
self.root = None
# Handles the request to add new node in Tree
def insert(self, data) :
if (self.root == None) :
# When add first node of tree
self.root = TreeNode(data, self.k)
else :
auxiliary = self.root
depth = 0
axis = 0
# Add new node in tree
while (auxiliary != None) :
axis = depth % self.k
if (auxiliary.keys[axis] > data[axis]) :
if (auxiliary.left == None) :
# Add new node
auxiliary.left = TreeNode(data, self.k)
# break the loop
auxiliary = None
else :
# visit left subtree
auxiliary = auxiliary.left
else :
if (auxiliary.right == None) :
# Add new node
auxiliary.right = TreeNode(data, self.k)
# break the loop
auxiliary = None
else :
# visit right subtree
auxiliary = auxiliary.right
depth += 1
# Print the all key of a given node
def printData(self, data) :
print(" (", end = "")
i = 0
while (i < self.k) :
if (i > 0) :
print(" , ", data[i], end = "")
else :
print(" ", data[i], end = "")
i += 1
print(")")
# Display tree node
def printTree(self, node) :
if (node != None) :
self.printTree(node.left)
self.printData(node.keys)
self.printTree(node.right)
# Compare node and given point
def isEquals(self, node, point) :
# When both are same
i = 0
while (i < self.k) :
if (node[i] != point[i]) :
return False
i += 1
return True
# return the minimum node by using of given dimension
def minPoint(self, node1, node2, dim) :
# Node 2 is smaller
if (node1 == None) :
# When node 1 empty
return node2
if (node2 == None) :
# When node 2 empty
return node1
if (node1.keys[dim] < node2.keys[dim]) :
# Node 1 is smaller
return node1
return node2
# Recursively finding the minimum of given dimension
def findMinimum(self, node, dim, depth) :
if (node == None) :
# When get a null Node
return None
# Get dimension position
position = depth % self.k
if (position == dim) :
# When position are equal to given a dimension
if (node.left == None) :
# Returns the current dimension
return node
return self.minPoint(node,
self.findMinimum(node.left, dim, depth + 1), dim)
# When position are equal to given a dimension
# Then resultant node can be exists in left or right subtree
return self.minPoint(node,
self.minPoint(self.findMinimum(node.left, dim, depth + 1),
self.findMinimum(node.right, dim, depth + 1), dim), dim)
# Handles the request of find minimum point using given dimensions
def minimum(self, dim) :
if (self.root == None) :
print("\n Empty Tree", end = "")
elif(dim < 0 or dim + 1 > self.k) :
print("\n Given dimensions are not valid ", end = "")
else :
n = self.findMinimum(self.root, dim, 0)
print("\n Given Dimension : ", dim, end = "")
if (n != None) :
print("\n Minimum is : ", n.keys[dim], end = "")
# Copy node 2 value into node1
def copyData(self, node1, node2) :
i = 0
while (i < self.k) :
node1[i] = node2[i]
i += 1
# Handles the request of remove given point node in tree
def removeNode(self, node, point, depth) :
if (node == None) :
print("Point not exist", end = "")
return None
dim = depth % self.k
if (self.isEquals(node.keys, point)) :
# When current node is same as deleted point
# Here are three possibility
if (node.right != None) :
# Case 1 : When right subtree not NULL
# Then find minimum node point and replace by current node
min = self.findMinimum(node.right, dim, 0)
# minimum point replace by current node
self.copyData(node.keys, min.keys)
# Recursively find new minimum deleted point
node.right = self.removeNode(node.right, min.keys, depth + 1)
elif(node.left != None) :
# Case 2 : When current node left subtree not Empty
# Then find minimum node point in left subtree and
# replace by current node
min = self.findMinimum(node.left, dim, 0)
# minimum point replace by current node
self.copyData(node.keys, min.keys)
# Recursively find new minimum deleted point
node.right = self.removeNode(node.left, min.keys, depth + 1)
else :
# Case 3 : When current node is leaf node
# Then remove it
node = None
return node
# Choose the left and right subtree by using given point
if (node.keys[dim] > point[dim]) :
node.left = self.removeNode(node.left, point, depth + 1)
else :
node.right = self.removeNode(node.right, point, depth + 1)
return node
# Handles the request to delete given point in tree
def deleteNode(self, point) :
if (self.root == None) :
print("\n Empty Tree", end = "")
return
print("\n Remove point ")
self.printData(point)
# Assuming that the given point length is equal to the tree node keys
self.root = self.removeNode(self.root, point, 0)
def main() :
k = 2
tree = KTree(k)
# 2d points
data = [
[8, 9] , [7, 6] , [3, 9] , [11, 12] ,
[2, 8] , [9, 4] , [10, 13] , [14, 8]
]
# Remove node points
point1 = [7, 6]
point2 = [8, 9]
# Get the number of elements
n = len(data)
# Insert all given nodes
i = 0
while (i < n) :
tree.insert(data[i])
i += 1
print("\n Tree Nodes")
#
# (8, 9)
# / \
# (7,6) (11,12)
# \ / \
# (3,9)(9,4) (10,13)
# / \
# (2,8) (14,8)
# -----------------
# Developed tree
#
# Print tree elements in inorder form
tree.printTree(tree.root)
# Case 1
tree.deleteNode(point1)
#
# (8, 9)
# / \
# (2,8) (11,12)
# \ / \
# (3,9)(9,4) (10,13)
# \
# (14,8)
# -----------------
# After Remove (7,6)
#
print("\n After Delete Tree Nodes")
# Print tree elements in inorder form
tree.printTree(tree.root)
# Case 2
tree.deleteNode(point2)
#
# (9, 4)
# / \
# (2,8) (11,12)
# \ / \
# (3,9)(14,8) (10,13)
#
# -----------------
# After Remove (8, 9)
#
print("\n After Delete Tree Nodes")
# Print tree elements in inorder form
tree.printTree(tree.root)
if __name__ == "__main__": main()
Output
Tree Nodes
( 7 , 6)
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 7 , 6)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 8 , 9)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
# Ruby Program
# Node deletion in K dimensional tree
# Define tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :keys, :left, :right
attr_accessor :keys, :left, :right
def initialize(data, k)
self.keys = Array.new(k) {0}
self.left = nil
self.right = nil
i = 0
while (i < k)
self.keys[i] = data[i]
i += 1
end
end
end
class KTree
# Define the accessor and reader of class KTree
attr_reader :k, :root
attr_accessor :k, :root
def initialize(k)
self.k = k
self.root = nil
end
# Handles the request to add new node in Tree
def insert(data)
if (self.root == nil)
# When add first node of tree
self.root = TreeNode.new(data, self.k)
else
auxiliary = self.root
depth = 0
axis = 0
# Add new node in tree
while (auxiliary != nil)
axis = depth % self.k
if (auxiliary.keys[axis] > data[axis])
if (auxiliary.left == nil)
# Add new node
auxiliary.left = TreeNode.new(data, self.k)
# break the loop
auxiliary = nil
else
# visit left subtree
auxiliary = auxiliary.left
end
else
if (auxiliary.right == nil)
# Add new node
auxiliary.right = TreeNode.new(data, self.k)
# break the loop
auxiliary = nil
else
# visit right subtree
auxiliary = auxiliary.right
end
end
depth += 1
end
end
end
# Print the all key of a given node
def printData(data)
print(" (")
i = 0
while (i < self.k)
if (i > 0)
print(" , ", data[i])
else
print(" ", data[i])
end
i += 1
end
print(")\n")
end
# Display tree node
def printTree(node)
if (node != nil)
self.printTree(node.left)
self.printData(node.keys)
self.printTree(node.right)
end
end
# Compare node and given point
def isEquals(node, point)
# When both are same
i = 0
while (i < self.k)
if (node[i] != point[i])
return false
end
i += 1
end
return true
end
# return the minimum node by using of given dimension
def minPoint(node1, node2, dim)
# Node 2 is smaller
if (node1 == nil)
# When node 1 empty
return node2
end
if (node2 == nil)
# When node 2 empty
return node1
end
if (node1.keys[dim] < node2.keys[dim])
# Node 1 is smaller
return node1
end
return node2
end
# Recursively finding the minimum of given dimension
def findMinimum(node, dim, depth)
if (node == nil)
# When get a null Node
return nil
end
# Get dimension position
position = depth % k
if (position == dim)
# When position are equal to given a dimension
if (node.left == nil)
# Returns the current dimension
return node
end
return self.minPoint(node,
self.findMinimum(node.left, dim, depth + 1), dim)
end
# When position are equal to given a dimension
# Then resultant node can be exists in left or right subtree
return self.minPoint(node,
self.minPoint(self.findMinimum(node.left, dim, depth + 1),
self.findMinimum(node.right, dim, depth + 1), dim), dim)
end
# Handles the request of find minimum point using given dimensions
def minimum(dim)
if (self.root == nil)
print("\n Empty Tree")
elsif(dim < 0 || dim + 1 > self.k)
print("\n Given dimensions are not valid ")
else
n = self.findMinimum(self.root, dim, 0)
print("\n Given Dimension : ", dim)
if (n != nil)
print("\n Minimum is : ", n.keys[dim])
end
end
end
# Copy node 2 value into node1
def copyData(node1, node2)
i = 0
while (i < self.k)
node1[i] = node2[i]
i += 1
end
end
# Handles the request of remove given point node in tree
def removeNode(node, point, depth)
if (node == nil)
print("Point not exist")
return nil
end
dim = depth % self.k
if (self.isEquals(node.keys, point))
# When current node is same as deleted point
# Here are three possibility
if (node.right != nil)
# Case 1 : When right subtree not NULL
# Then find minimum node point and replace by current node
min = self.findMinimum(node.right, dim, 0)
# minimum point replace by current node
self.copyData(node.keys, min.keys)
# Recursively find new minimum deleted point
node.right = self.removeNode(node.right, min.keys, depth + 1)
elsif(node.left != nil)
# Case 2 : When current node left subtree not Empty
# Then find minimum node point in left subtree and
# replace by current node
min = self.findMinimum(node.left, dim, 0)
# minimum point replace by current node
self.copyData(node.keys, min.keys)
# Recursively find new minimum deleted point
node.right = self.removeNode(node.left, min.keys, depth + 1)
else
# Case 3 : When current node is leaf node
# Then remove it
node = nil
end
return node
end
# Choose the left and right subtree by using given point
if (node.keys[dim] > point[dim])
node.left = self.removeNode(node.left, point, depth + 1)
else
node.right = self.removeNode(node.right, point, depth + 1)
end
return node
end
# Handles the request to delete given point in tree
def deleteNode(point)
if (self.root == nil)
print("\n Empty Tree")
return
end
print("\n Remove point \n")
self.printData(point)
# Assuming that the given point length is equal to the tree node keys
self.root = self.removeNode(self.root, point, 0)
end
end
def main()
k = 2
tree = KTree.new(k)
# 2d points
data = [
[8, 9] , [7, 6] , [3, 9] , [11, 12] ,
[2, 8] , [9, 4] , [10, 13] , [14, 8]
]
# Remove node points
point1 = [7, 6]
point2 = [8, 9]
# Get the number of elements
n = data.length
# Insert all given nodes
i = 0
while (i < n)
tree.insert(data[i])
i += 1
end
print("\n Tree Nodes\n")
#
# (8, 9)
# / \
# (7,6) (11,12)
# \ / \
# (3,9)(9,4) (10,13)
# / \
# (2,8) (14,8)
# -----------------
# Developed tree
# Print tree elements in inorder form
tree.printTree(tree.root)
# Case 1
tree.deleteNode(point1)
#
# (8, 9)
# / \
# (2,8) (11,12)
# \ / \
# (3,9)(9,4) (10,13)
# \
# (14,8)
# -----------------
# After Remove (7,6)
print("\n After Delete Tree Nodes\n")
# Print tree elements in inorder form
tree.printTree(tree.root)
# Case 2
tree.deleteNode(point2)
#
# (9, 4)
# / \
# (2,8) (11,12)
# \ / \
# (3,9)(14,8) (10,13)
#
# -----------------
# After Remove (8, 9)
print("\n After Delete Tree Nodes\n")
# Print tree elements in inorder form
tree.printTree(tree.root)
end
main()
Output
Tree Nodes
( 7 , 6)
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 7 , 6)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 8 , 9)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
// Scala Program
// Node deletion in K dimensional tree
// Define tree node
class TreeNode(var keys: Array[Int] ,
var left: TreeNode ,
var right: TreeNode)
{
def this(data: Array[Int], k: Int)
{
this(Array.fill[Int](k)(0), null, null);
var i: Int = 0
while (i < k)
{
this.keys(i) = data(i);
i += 1
}
}
}
class KTree(var k: Int ,
var root: TreeNode)
{
def this(k: Int)
{
this(k, null);
}
// Handles the request to add new node in Tree
def insert(data: Array[Int]): Unit = {
if (this.root == null)
{
// When add first node of tree
this.root = new TreeNode(data, this.k);
}
else
{
var auxiliary: TreeNode = this.root;
var depth: Int = 0;
var axis: Int = 0;
// Add new node in tree
while (auxiliary != null)
{
axis = depth % this.k;
if (auxiliary.keys(axis) > data(axis))
{
if (auxiliary.left == null)
{
// Add new node
auxiliary.left = new TreeNode(data, this.k);
// break the loop
auxiliary = null;
}
else
{
// visit left subtree
auxiliary = auxiliary.left;
}
}
else
{
if (auxiliary.right == null)
{
// Add new node
auxiliary.right = new TreeNode(data, this.k);
// break the loop
auxiliary = null;
}
else
{
// visit right subtree
auxiliary = auxiliary.right;
}
}
depth += 1;
}
}
}
// Print the all key of a given node
def printData(data: Array[Int]): Unit = {
print(" (");
var i: Int = 0;
while (i < this.k)
{
if (i > 0)
{
print(" , " + data(i));
}
else
{
print(" " + data(i));
}
i += 1;
}
print(")\n");
}
// Display tree node
def printTree(node: TreeNode): Unit = {
if (node != null)
{
this.printTree(node.left);
this.printData(node.keys);
this.printTree(node.right);
}
}
// Compare node and given point
def isEquals(node: Array[Int], point: Array[Int]): Boolean = {
// When both are same
var i: Int = 0;
while (i < this.k)
{
if (node(i) != point(i))
{
return false;
}
i += 1;
}
return true;
}
// return the minimum node by using of given dimension
def minPoint(node1: TreeNode, node2: TreeNode, dim: Int): TreeNode = {
// Node 2 is smaller
if (node1 == null)
{
// When node 1 empty
return node2;
}
if (node2 == null)
{
// When node 2 empty
return node1;
}
if (node1.keys(dim) < node2.keys(dim))
{
// Node 1 is smaller
return node1;
}
return node2;
}
// Recursively finding the minimum of given dimension
def findMinimum(node: TreeNode, dim: Int, depth: Int): TreeNode = {
if (node == null)
{
// When get a null Node
return null;
}
// Get dimension position
var position: Int = depth % k;
if (position == dim)
{
// When position are equal to given a dimension
if (node.left == null)
{
// Returns the current dimension
return node;
}
return this.minPoint(node, this.findMinimum(node.left, dim, depth + 1), dim);
}
// When position are equal to given a dimension
// Then resultant node can be exists in left or right subtree
return this.minPoint(node, this.minPoint(this.findMinimum(node.left, dim, depth + 1), this.findMinimum(node.right, dim, depth + 1), dim), dim);
}
// Handles the request of find minimum point using given dimensions
def minimum(dim: Int): Unit = {
if (this.root == null)
{
print("\n Empty Tree");
}
else if (dim < 0 || dim + 1 > this.k)
{
print("\n Given dimensions are not valid ");
}
else
{
var n: TreeNode = this.findMinimum(this.root, dim, 0);
print("\n Given Dimension : " + dim);
if (n != null)
{
print("\n Minimum is : " + n.keys(dim));
}
}
}
// Copy node 2 value into node1
def copyData(node1: Array[Int], node2: Array[Int]): Unit = {
var i: Int = 0;
while (i < this.k)
{
node1(i) = node2(i);
i += 1;
}
}
// Handles the request of remove given point node in tree
def removeNode(node: TreeNode, point: Array[Int], depth: Int): TreeNode = {
if (node == null)
{
print("Point not exist");
return null;
}
var dim: Int = depth % this.k;
if (this.isEquals(node.keys, point))
{
// When current node is same as deleted point
// Here are three possibility
if (node.right != null)
{
// Case 1 : When right subtree not NULL
// Then find minimum node point and replace by current node
var min: TreeNode = this.findMinimum(node.right, dim, 0);
// minimum point replace by current node
this.copyData(node.keys, min.keys);
// Recursively find new minimum deleted point
node.right = this.removeNode(node.right, min.keys, depth + 1);
}
else if (node.left != null)
{
// Case 2 : When current node left subtree not Empty
// Then find minimum node point in left subtree and
// replace by current node
var min = this.findMinimum(node.left, dim, 0);
// minimum point replace by current node
this.copyData(node.keys, min.keys);
// Recursively find new minimum deleted point
node.right = this.removeNode(node.left, min.keys, depth + 1);
}
else
{
// Case 3 : When current node is leaf node
// Then remove it
return null;
}
return node;
}
// Choose the left and right subtree by using given point
if (node.keys(dim) > point(dim))
{
node.left = this.removeNode(node.left, point, depth + 1);
}
else
{
node.right = this.removeNode(node.right, point, depth + 1);
}
return node;
}
// Handles the request to delete given point in tree
def deleteNode(point: Array[Int]): Unit = {
if (this.root == null)
{
print("\n Empty Tree");
return;
}
print("\n Remove point \n");
this.printData(point);
// Assuming that the given point length is equal to the tree node keys
this.root = this.removeNode(this.root, point, 0);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var k: Int = 2;
var tree: KTree = new KTree(k);
// 2d points
var data: Array[Array[Int]] = Array(
Array(8, 9), Array(7, 6), Array(3, 9),
Array(11, 12), Array(2, 8), Array(9, 4),
Array(10, 13), Array(14, 8));
// Remove node points
var point1: Array[Int] = Array(7, 6);
var point2: Array[Int] = Array(8, 9);
// Get the number of elements
var n: Int = data.length;
// Insert all given nodes
var i: Int = 0;
while (i < n)
{
tree.insert(data(i));
i += 1;
}
print("\n Tree Nodes\n");
/*
(8, 9)
/ \
(7,6) (11,12)
\ / \
(3,9)(9,4) (10,13)
/ \
(2,8) (14,8)
-----------------
Developed tree
*/
// Print tree elements in inorder form
tree.printTree(tree.root);
// Case 1
tree.deleteNode(point1);
/*
(8, 9)
/ \
(2,8) (11,12)
\ / \
(3,9)(9,4) (10,13)
\
(14,8)
-----------------
After Remove (7,6)
*/
print("\n After Delete Tree Nodes\n");
// Print tree elements in inorder form
tree.printTree(tree.root);
// Case 2
tree.deleteNode(point2);
/*
(9, 4)
/ \
(2,8) (11,12)
\ / \
(3,9)(14,8) (10,13)
-----------------
After Remove (8, 9)
*/
print("\n After Delete Tree Nodes\n");
// Print tree elements in inorder form
tree.printTree(tree.root);
}
}
Output
Tree Nodes
( 7 , 6)
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 7 , 6)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 8 , 9)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
// Swift 4 Program
// Node deletion in K dimensional tree
// Define tree node
class TreeNode
{
var keys: [Int];
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: [Int], _ k: Int)
{
self.keys = Array(repeating: 0, count: k);
self.left = nil;
self.right = nil;
var i: Int = 0;
while (i < k)
{
self.keys[i] = data[i];
i += 1;
}
}
}
class KTree
{
var k: Int;
var root: TreeNode? ;
init(_ k: Int)
{
self.k = k;
self.root = nil;
}
// Handles the request to add new node in Tree
func insert(_ data: [Int])
{
if (self.root == nil)
{
// When add first node of tree
self.root = TreeNode(data, self.k);
}
else
{
var auxiliary: TreeNode? = self.root;
var depth: Int = 0;
var axis: Int = 0;
// Add new node in tree
while (auxiliary != nil)
{
axis = depth % self.k;
if (auxiliary!.keys[axis] > data[axis])
{
if (auxiliary!.left == nil)
{
// Add new node
auxiliary!.left = TreeNode(data, self.k);
// break the loop
auxiliary = nil;
}
else
{
// visit left subtree
auxiliary = auxiliary!.left;
}
}
else
{
if (auxiliary!.right == nil)
{
// Add new node
auxiliary!.right = TreeNode(data, self.k);
// break the loop
auxiliary = nil;
}
else
{
// visit right subtree
auxiliary = auxiliary!.right;
}
}
depth += 1;
}
}
}
// Print the all key of a given node
func printData(_ data: [Int])
{
print(" (", terminator: "");
var i: Int = 0;
while (i < self.k)
{
if (i > 0)
{
print(" , ", data[i], terminator: "");
}
else
{
print(" ", data[i], terminator: "");
}
i += 1;
}
print(")");
}
// Display tree node
func printTree(_ node: TreeNode? )
{
if (node != nil)
{
self.printTree(node!.left);
self.printData(node!.keys);
self.printTree(node!.right);
}
}
// Compare node and given point
func isEquals(_ node: [Int], _ point: [Int])->Bool
{
// When both are same
var i: Int = 0;
while (i < self.k)
{
if (node[i] != point[i])
{
return false;
}
i += 1;
}
return true;
}
// return the minimum node by using of given dimension
func minPoint(_ node1: TreeNode? , _ node2 : TreeNode? , _ dim : Int)->TreeNode?
{
// Node 2 is smaller
if (node1 == nil)
{
// When node 1 empty
return node2;
}
if (node2 == nil)
{
// When node 2 empty
return node1;
}
if (node1!.keys[dim] < node2!.keys[dim])
{
// Node 1 is smaller
return node1;
}
return node2;
}
// Recursively finding the minimum of given dimension
func findMinimum(_ node: TreeNode? , _ dim : Int, _ depth: Int)->TreeNode?
{
if (node == nil)
{
// When get a null Node
return nil;
}
// Get dimension position
let position: Int = depth % self.k;
if (position == dim)
{
// When position are equal to given a dimension
if (node!.left == nil)
{
// Returns the current dimension
return node;
}
return self.minPoint(node,
self.findMinimum(node!.left, dim, depth + 1), dim);
}
// When position are equal to given a dimension
// Then resultant node can be exists in left or right subtree
return self.minPoint(node,
self.minPoint(self.findMinimum(node!.left, dim, depth + 1),
self.findMinimum(node!.right, dim, depth + 1), dim), dim);
}
// Handles the request of find minimum point using given dimensions
func minimum(_ dim: Int)
{
if (self.root == nil)
{
print("\n Empty Tree", terminator: "");
}
else if (dim < 0 || dim + 1 > self.k)
{
print("\n Given dimensions are not valid ", terminator: "");
}
else
{
let n: TreeNode? = self.findMinimum(self.root, dim, 0);
print("\n Given Dimension : ", dim, terminator: "");
if (n != nil)
{
print("\n Minimum is : ", n!.keys[dim], terminator: "");
}
}
}
// Copy node 2 value into node1
func copyData(_ node1: inout[Int], _ node2: [Int])
{
var i: Int = 0;
while (i < self.k)
{
node1[i] = node2[i];
i += 1;
}
}
// Handles the request of remove given point node in tree
func removeNode(_ node: TreeNode? , _ point : [Int], _ depth: Int)->TreeNode?
{
if (node == nil)
{
print("Point not exist", terminator: "");
return nil;
}
let dim: Int = depth % self.k;
if (self.isEquals(node!.keys, point))
{
// When current node is same as deleted point
// Here are three possibility
if (node!.right != nil)
{
// Case 1 : When right subtree not NULL
// Then find minimum node point and replace by current node
let min: TreeNode? = self.findMinimum(node!.right, dim, 0);
// minimum point replace by current node
self.copyData(&node!.keys, min!.keys);
// Recursively find new minimum deleted point
node!.right = self.removeNode(node!.right, min!.keys, depth + 1);
}
else if (node!.left != nil)
{
// Case 2 : When current node left subtree not Empty
// Then find minimum node point in left subtree and
// replace by current node
let min = self.findMinimum(node!.left, dim, 0);
// minimum point replace by current node
self.copyData(&node!.keys, min!.keys);
// Recursively find new minimum deleted point
node!.right = self.removeNode(node!.left, min!.keys, depth + 1);
}
else
{
// Case 3 : When current node is leaf node
// Then remove it
return nil;
}
return node;
}
// Choose the left and right subtree by using given point
if (node!.keys[dim] > point[dim])
{
node!.left = self.removeNode(node!.left, point, depth + 1);
}
else
{
node!.right = self.removeNode(node!.right, point, depth + 1);
}
return node;
}
// Handles the request to delete given point in tree
func deleteNode(_ point: [Int])
{
if (self.root == nil)
{
print("\n Empty Tree", terminator: "");
return;
}
print("\n Remove point ");
self.printData(point);
// Assuming that the given point length is equal to the tree node keys
self.root = self.removeNode(self.root, point, 0);
}
}
func main()
{
let k: Int = 2;
let tree: KTree = KTree(k);
// 2d points
let data: [
[Int]
] = [
[8, 9] , [7, 6] , [3, 9] , [11, 12] , [2, 8] , [9, 4] , [10, 13] , [14, 8]
];
// Remove node points
let point1: [Int] = [7, 6];
let point2: [Int] = [8, 9];
// Get the number of elements
let n: Int = data.count;
// Insert all given nodes
var i: Int = 0;
while (i < n)
{
tree.insert(data[i]);
i += 1;
}
print("\n Tree Nodes");
/*
(8, 9)
/ \
(7,6) (11,12)
\ / \
(3,9)(9,4) (10,13)
/ \
(2,8) (14,8)
-----------------
Developed tree
*/
// Print tree elements in inorder form
tree.printTree(tree.root);
// Case 1
tree.deleteNode(point1);
/*
(8, 9)
/ \
(2,8) (11,12)
\ / \
(3,9)(9,4) (10,13)
\
(14,8)
-----------------
After Remove (7,6)
*/
print("\n After Delete Tree Nodes");
// Print tree elements in inorder form
tree.printTree(tree.root);
// Case 2
tree.deleteNode(point2);
/*
(9, 4)
/ \
(2,8) (11,12)
\ / \
(3,9)(14,8) (10,13)
-----------------
After Remove (8, 9)
*/
print("\n After Delete Tree Nodes");
// Print tree elements in inorder form
tree.printTree(tree.root);
}
main();
Output
Tree Nodes
( 7 , 6)
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 7 , 6)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 8 , 9)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
// Kotlin Program
// Node deletion in K dimensional tree
// Define tree node
class TreeNode
{
var keys: Array < Int > ;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Array < Int > , k: Int)
{
this.keys = Array(k)
{
0
};
this.left = null;
this.right = null;
var i: Int = 0;
while (i < k)
{
this.keys[i] = data[i];
i += 1;
}
}
}
class KTree
{
var k: Int;
var root: TreeNode ? ;
constructor(k: Int)
{
this.k = k;
this.root = null;
}
// Handles the request to add new node in Tree
fun insert(data: Array < Int > ): Unit
{
if (this.root == null)
{
// When add first node of tree
this.root = TreeNode(data, this.k);
}
else
{
var auxiliary: TreeNode ? = this.root;
var depth: Int = 0;
var axis: Int;
// Add new node in tree
while (auxiliary != null)
{
axis = depth % this.k;
if (auxiliary.keys[axis] > data[axis])
{
if (auxiliary.left == null)
{
// Add new node
auxiliary.left = TreeNode(data, this.k);
// break the loop
auxiliary = null;
}
else
{
// visit left subtree
auxiliary = auxiliary.left;
}
}
else
{
if (auxiliary.right == null)
{
// Add new node
auxiliary.right = TreeNode(data, this.k);
// break the loop
auxiliary = null;
}
else
{
// visit right subtree
auxiliary = auxiliary.right;
}
}
depth += 1;
}
}
}
// Print the all key of a given node
fun printData(data: Array < Int > ): Unit
{
print(" (");
var i: Int = 0;
while (i < this.k)
{
if (i > 0)
{
print(" , " + data[i]);
}
else
{
print(" " + data[i]);
}
i += 1;
}
print(")\n");
}
// Display tree node
fun printTree(node: TreeNode ? ): Unit
{
if (node != null)
{
this.printTree(node.left);
this.printData(node.keys);
this.printTree(node.right);
}
}
// Compare node and given point
fun isEquals(node: Array < Int > , point: Array < Int > ): Boolean
{
// When both are same
var i: Int = 0;
while (i < this.k)
{
if (node[i] != point[i])
{
return false;
}
i += 1;
}
return true;
}
// return the minimum node by using of given dimension
fun minPoint(node1: TreeNode ? , node2 : TreeNode ? , dim : Int): TreeNode ?
{
// Node 2 is smaller
if (node1 == null)
{
// When node 1 empty
return node2;
}
if (node2 == null)
{
// When node 2 empty
return node1;
}
if (node1.keys[dim] < node2.keys[dim])
{
// Node 1 is smaller
return node1;
}
return node2;
}
// Recursively finding the minimum of given dimension
fun findMinimum(node: TreeNode ? , dim : Int, depth: Int): TreeNode ?
{
if (node == null)
{
// When get a null Node
return null;
}
// Get dimension position
var position: Int = depth % k;
if (position == dim)
{
// When position are equal to given a dimension
if (node.left == null)
{
// Returns the current dimension
return node;
}
return this.minPoint(node,
this.findMinimum(node.left, dim, depth + 1), dim);
}
// When position are equal to given a dimension
// Then resultant node can be exists in left or right subtree
return this.minPoint(node,
this.minPoint(
this.findMinimum(node.left, dim, depth + 1),
this.findMinimum(node.right, dim, depth + 1), dim), dim);
}
// Handles the request of find minimum point using given dimensions
fun minimum(dim: Int): Unit
{
if (this.root == null)
{
print("\n Empty Tree");
}
else if (dim < 0 || dim + 1 > this.k)
{
print("\n Given dimensions are not valid ");
}
else
{
var n: TreeNode? = this.findMinimum(this.root, dim, 0);
print("\n Given Dimension : " + dim);
if (n != null)
{
print("\n Minimum is : " + n.keys[dim]);
}
}
}
// Copy node 2 value into node1
fun copyData(node1: Array < Int > , node2: Array < Int > ): Unit
{
var i: Int = 0;
while (i < this.k)
{
node1[i] = node2[i];
i += 1;
}
}
// Handles the request of remove given point node in tree
fun removeNode(node: TreeNode ? , point : Array <Int> , depth: Int): TreeNode ?
{
if (node == null)
{
print("Point not exist");
return null;
}
var dim: Int = depth % this.k;
if (this.isEquals(node.keys, point))
{
// When current node is same as deleted point
// Here are three possibility
if (node.right != null)
{
// Case 1 : When right subtree not NULL
// Then find minimum node point and replace by current node
var min: TreeNode? = this.findMinimum(node.right, dim, 0);
// minimum point replace by current node
this.copyData(node.keys, min!!.keys);
// Recursively find new minimum deleted point
node.right = this.removeNode(node.right, min.keys, depth + 1);
}
else if (node.left != null)
{
// Case 2 : When current node left subtree not Empty
// Then find minimum node point in left subtree and
// replace by current node
var min: TreeNode? = this.findMinimum(node.left, dim, 0);
// minimum point replace by current node
this.copyData(node.keys, min!!.keys);
// Recursively find new minimum deleted point
node.right = this.removeNode(node.left, min.keys, depth + 1);
}
else
{
// Case 3 : When current node is leaf node
// Then remove it
return null;
}
return node;
}
// Choose the left and right subtree by using given point
if (node.keys[dim] > point[dim])
{
node.left = this.removeNode(node.left, point, depth + 1);
}
else
{
node.right = this.removeNode(node.right, point, depth + 1);
}
return node;
}
// Handles the request to delete given point in tree
fun deleteNode(point: Array < Int > ): Unit
{
if (this.root == null)
{
print("\n Empty Tree");
return;
}
print("\n Remove point \n");
this.printData(point);
// Assuming that the given point length is equal to the tree node keys
this.root = this.removeNode(this.root, point, 0);
}
}
fun main(args: Array < String > ): Unit
{
var k: Int = 2;
var tree: KTree = KTree(k);
// 2d points
var data: Array < Array < Int >> = arrayOf(
arrayOf(8, 9),
arrayOf(7, 6),
arrayOf(3, 9),
arrayOf(11, 12),
arrayOf(2, 8),
arrayOf(9, 4),
arrayOf(10, 13),
arrayOf(14, 8));
// Remove node points
var point1: Array < Int > = arrayOf(7, 6);
var point2: Array < Int > = arrayOf(8, 9);
// Get the number of elements
var n: Int = data.count();
// Insert all given nodes
var i: Int = 0;
while (i < n)
{
tree.insert(data[i]);
i += 1;
}
print("\n Tree Nodes\n");
/*
(8, 9)
/ \
(7,6) (11,12)
\ / \
(3,9)(9,4) (10,13)
/ \
(2,8) (14,8)
-----------------
Developed tree
*/
// Print tree elements in inorder form
tree.printTree(tree.root);
// Case 1
tree.deleteNode(point1);
/*
(8, 9)
/ \
(2,8) (11,12)
\ / \
(3,9)(9,4) (10,13)
\
(14,8)
-----------------
After Remove (7,6)
*/
print("\n After Delete Tree Nodes\n");
// Print tree elements in inorder form
tree.printTree(tree.root);
// Case 2
tree.deleteNode(point2);
/*
(9, 4)
/ \
(2,8) (11,12)
\ / \
(3,9)(14,8) (10,13)
-----------------
After Remove (8, 9)
*/
print("\n After Delete Tree Nodes\n");
// Print tree elements in inorder form
tree.printTree(tree.root);
}
Output
Tree Nodes
( 7 , 6)
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 7 , 6)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 8 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)
Remove point
( 8 , 9)
After Delete Tree Nodes
( 2 , 8)
( 3 , 9)
( 9 , 4)
( 14 , 8)
( 11 , 12)
( 10 , 13)

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