K dimensional tree insertion
Here given code implementation process.
// C program for
// K dimensional tree insertion
#include <stdio.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;
}
// Check if given point exists in tree or not
void search(struct KTree *tree, int point[])
{
if (tree->root != NULL)
{
struct TreeNode *auxiliary = tree->root;
int depth = 0;
int axis = 0;
int result = 0;
// Find node point
while (auxiliary != NULL && result == 0)
{
axis = depth % tree->k;
if (isEquals(auxiliary->keys, point, tree->k) == 1)
{
// When get resultant node
result = 1;
auxiliary = NULL;
}
else if (auxiliary->keys[axis] > point[axis])
{
// visit left subtree
auxiliary = auxiliary->left;
}
else
{
// visit right subtree
auxiliary = auxiliary->right;
}
depth++;
}
printf("\n Given point : ");
printData(point, tree->k);
if (result == 1)
{
printf(" Found \n");
}
else
{
printf(" Not Found \n");
}
}
else
{
printf("\n Empty Tree");
}
}
int main(int argc, char const *argv[])
{
// Number of Dimensions
int k = 2;
struct KTree *tree = createTree(k);
// 2d points
int data[][2] = {
{
8 , 2
},
{
7 , 4
},
{
3 , 5
},
{
11, 2
},
{
5 , 8
},
{
9 , 4
},
{
2 , 3
}
};
// 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 Tree Nodes\n");
/*
(8,2)
/ \
(7,4) (11,2)
/ \ \
(2,3) (3,5) (9,4)
\
(5,8)
-----------------
Developed tree
*/
// Print tree elements in inorder form
printTree(tree->root, tree->k);
// Search nodes
int point1[] = {
8 , 1
};
int point2[] = {
5 , 8
};
int point3[] = {
5 , 4
};
// Test case for find nodes
search(tree, point1);
search(tree, point2);
search(tree, point3);
return 0;
}
Output
Tree Nodes
( 2 , 3)
( 7 , 4)
( 3 , 5)
( 5 , 8)
( 8 , 2)
( 11 , 2)
( 9 , 4)
Given point : ( 8 , 1)
Not Found
Given point : ( 5 , 8)
Found
Given point : ( 5 , 4)
Not Found
// Java Program
// K dimensional tree insertion
// 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;
}
// Check if given point exists in tree or not
public void search(int[] point)
{
if (this.root != null)
{
TreeNode auxiliary = this.root;
int depth = 0;
int axis = 0;
boolean result = false;
// Find node point
while (auxiliary != null && result == false)
{
axis = depth % this.k;
if (isEquals(auxiliary.keys, point) == true)
{
// When get resultant node
result = true;
auxiliary = null;
}
else if (auxiliary.keys[axis] > point[axis])
{
// visit left subtree
auxiliary = auxiliary.left;
}
else
{
// visit right subtree
auxiliary = auxiliary.right;
}
depth++;
}
System.out.print("\n Given point : ");
printData(point);
if (result == true)
{
System.out.print(" Found \n");
}
else
{
System.out.print(" Not Found \n");
}
}
else
{
System.out.print("\n Empty Tree");
}
}
public static void main(String[] args)
{
int k = 2;
KTree tree = new KTree(2);
// 2d points
int[][] data = {
{
8 , 2
} ,
{
7 , 4
} ,
{
3 , 5
} ,
{
11 , 2
} ,
{
5 , 8
} ,
{
9 , 4
} ,
{
2 , 3
}
};
// 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,2)
/ \
(7,4) (11,2)
/ \ \
(2,3) (3,5) (9,4)
\
(5,8)
-----------------
Developed tree
*/
// Print tree elements in inorder form
tree.printTree(tree.root);
// Search nodes
int[] point1 = {
8 , 1
};
int[] point2 = {
5 , 8
};
int[] point3 = {
5 , 4
};
// Test case for find nodes
tree.search(point1);
tree.search(point2);
tree.search(point3);
}
}
Output
Tree Nodes
( 2 , 3)
( 7 , 4)
( 3 , 5)
( 5 , 8)
( 8 , 2)
( 11 , 2)
( 9 , 4)
Given point : ( 8 , 1)
Not Found
Given point : ( 5 , 8)
Found
Given point : ( 5 , 4)
Not Found
// Include header file
#include <iostream>
using namespace std;
// C++ Program
// K dimensional tree insertion
// 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;
}
// Check if given point exists in tree or not
void search(int point[])
{
if (this->root != NULL)
{
TreeNode *auxiliary = this->root;
int depth = 0;
int axis = 0;
bool result = false;
// Find node point
while (auxiliary != NULL && result == false)
{
axis = depth % this->k;
if (this->isEquals(auxiliary->keys, point) == true)
{
// When get resultant node
result = true;
auxiliary = NULL;
}
else if (auxiliary->keys[axis] > point[axis])
{
// visit left subtree
auxiliary = auxiliary->left;
}
else
{
// visit right subtree
auxiliary = auxiliary->right;
}
depth++;
}
cout << "\n Given point : ";
this->printData(point);
if (result == true)
{
cout << " Found \n";
}
else
{
cout << " Not Found \n";
}
}
else
{
cout << "\n Empty Tree";
}
}
};
int main()
{
int k = 2;
KTree tree = KTree(2);
// 2d points
int data[][2] = {
{
8 , 2
} ,
{
7 , 4
} ,
{
3 , 5
} ,
{
11 , 2
} ,
{
5 , 8
} ,
{
9 , 4
} ,
{
2 , 3
}
};
// 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,2)
/ \
(7,4) (11,2)
/ \ \
(2,3) (3,5) (9,4)
\
(5,8)
-----------------
Developed tree
*/
// Print tree elements in inorder form
tree.printTree(tree.root);
// Search nodes
int point1[] = {
8 , 1
};
int point2[] = {
5 , 8
};
int point3[] = {
5 , 4
};
// Test case for find nodes
tree.search(point1);
tree.search(point2);
tree.search(point3);
return 0;
}
Output
Tree Nodes
( 2 , 3)
( 7 , 4)
( 3 , 5)
( 5 , 8)
( 8 , 2)
( 11 , 2)
( 9 , 4)
Given point : ( 8 , 1)
Not Found
Given point : ( 5 , 8)
Found
Given point : ( 5 , 4)
Not Found
<?php
// Php Program
// K dimensional tree insertion
// 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;
}
// Check if given point exists in tree or not
public function search( $point)
{
if ($this->root != null)
{
$auxiliary = $this->root;
$depth = 0;
$axis = 0;
$result = false;
// Find node point
while ($auxiliary != null && $result == false)
{
$axis = $depth % $this->k;
if ($this->isEquals($auxiliary->keys, $point) == true)
{
// When get resultant node
$result = true;
$auxiliary = null;
}
else if ($auxiliary->keys[$axis] > $point[$axis])
{
// visit left subtree
$auxiliary = $auxiliary->left;
}
else
{
// visit right subtree
$auxiliary = $auxiliary->right;
}
$depth++;
}
echo "\n Given point : ";
$this->printData($point);
if ($result == true)
{
echo " Found \n";
}
else
{
echo " Not Found \n";
}
}
else
{
echo "\n Empty Tree";
}
}
}
function main()
{
$k = 2;
$tree = new KTree($k);
// 2d points
$data = array(
array(8, 2),
array(7, 4),
array(3, 5),
array(11, 2),
array(5, 8),
array(9, 4),
array(2, 3)
);
// 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);
// Search nodes
$point1 = array(8, 1);
$point2 = array(5, 8);
$point3 = array(5, 4);
$tree->search($point1);
$tree->search($point2);
$tree->search($point3);
}
main();
Output
Tree Nodes
( 2 , 3)
( 7 , 4)
( 3 , 5)
( 5 , 8)
( 8 , 2)
( 11 , 2)
( 9 , 4)
Given point : ( 8 , 1)
Not Found
Given point : ( 5 , 8)
Found
Given point : ( 5 , 4)
Not Found
// Node Js Program
// K dimensional tree insertion
// 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;
}
// Check if given point exists in tree or not
search(point)
{
if (this.root != null)
{
var auxiliary = this.root;
var depth = 0;
var axis = 0;
var result = false;
// Find node point
while (auxiliary != null && result == false)
{
axis = depth % this.k;
if (this.isEquals(auxiliary.keys, point) == true)
{
// When get resultant node
result = true;
auxiliary = null;
}
else if (auxiliary.keys[axis] > point[axis])
{
// visit left subtree
auxiliary = auxiliary.left;
}
else
{
// visit right subtree
auxiliary = auxiliary.right;
}
depth++;
}
process.stdout.write("\n Given point : ");
this.printData(point);
if (result == true)
{
process.stdout.write(" Found \n");
}
else
{
process.stdout.write(" Not Found \n");
}
}
else
{
process.stdout.write("\n Empty Tree");
}
}
}
function main()
{
var k = 2;
var tree = new KTree(k);
// 2d points
var data = [
[8, 2] , [7, 4] , [3, 5] ,
[11, 2] ,
[5, 8] , [9, 4] , [2, 3]
];
// 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,2)
/ \
(7,4) (11,2)
/ \ \
(2,3) (3,5) (9,4)
\
(5,8)
-----------------
Developed tree
*/
// Print tree elements in inorder form
tree.printTree(tree.root);
// Search nodes
var point1 = [8, 1];
var point2 = [5, 8];
var point3 = [5, 4];
// Test case for find nodes
tree.search(point1);
tree.search(point2);
tree.search(point3);
}
main();
Output
Tree Nodes
( 2 , 3)
( 7 , 4)
( 3 , 5)
( 5 , 8)
( 8 , 2)
( 11 , 2)
( 9 , 4)
Given point : ( 8 , 1)
Not Found
Given point : ( 5 , 8)
Found
Given point : ( 5 , 4)
Not Found
# Python 3 Program
# K dimensional tree insertion
# 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
# Check if given point exists in tree or not
def search(self, point) :
if (self.root != None) :
auxiliary = self.root
depth = 0
axis = 0
result = False
# Find node point
while (auxiliary != None and result == False) :
axis = depth % self.k
if (self.isEquals(auxiliary.keys, point) == True) :
# When get resultant node
result = True
auxiliary = None
elif(auxiliary.keys[axis] > point[axis]) :
# visit left subtree
auxiliary = auxiliary.left
else :
# visit right subtree
auxiliary = auxiliary.right
depth += 1
print("\n Given point : ", end = "")
self.printData(point)
if (result == True) :
print(" Found ")
else :
print(" Not Found ")
else :
print("\n Empty Tree", end = "")
def main() :
k = 2
tree = KTree(k)
# 2d points
data = [
[8, 2] , [7, 4] , [3, 5] , [11, 2] ,
[5, 8] , [9, 4] , [2, 3]
]
# 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,2)
# / \
# (7,4) (11,2)
# / \ \
# (2,3) (3,5) (9,4)
# \
# (5,8)
# -----------------
# Developed tree
# Print tree elements in inorder form
tree.printTree(tree.root)
# Search nodes
point1 = [8, 1]
point2 = [5, 8]
point3 = [5, 4]
# Test case for find nodes
tree.search(point1)
tree.search(point2)
tree.search(point3)
if __name__ == "__main__": main()
Output
Tree Nodes
( 2 , 3)
( 7 , 4)
( 3 , 5)
( 5 , 8)
( 8 , 2)
( 11 , 2)
( 9 , 4)
Given point : ( 8 , 1)
Not Found
Given point : ( 5 , 8)
Found
Given point : ( 5 , 4)
Not Found
# Ruby Program
# K dimensional tree insertion
# 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
# Check if given point exists in tree or not
def search(point)
if (self.root != nil)
auxiliary = self.root
depth = 0
axis = 0
result = false
# Find node point
while (auxiliary != nil && result == false)
axis = depth % self.k
if (self.isEquals(auxiliary.keys, point) == true)
# When get resultant node
result = true
auxiliary = nil
elsif(auxiliary.keys[axis] > point[axis])
# visit left subtree
auxiliary = auxiliary.left
else
# visit right subtree
auxiliary = auxiliary.right
end
depth += 1
end
print("\n Given point : ")
self.printData(point)
if (result == true)
print(" Found \n")
else
print(" Not Found \n")
end
else
print("\n Empty Tree")
end
end
end
def main()
k = 2
tree = KTree.new(k)
# 2d points
data = [
[8, 2] , [7, 4] , [3, 5] , [11, 2] , [5, 8] , [9, 4] , [2, 3]
]
# 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,2)
# / \
# (7,4) (11,2)
# / \ \
# (2,3) (3,5) (9,4)
# \
# (5,8)
# -----------------
# Developed tree
# Print tree elements in inorder form
tree.printTree(tree.root)
# Search nodes
point1 = [8, 1]
point2 = [5, 8]
point3 = [5, 4]
# Test case for find nodes
tree.search(point1)
tree.search(point2)
tree.search(point3)
end
main()
Output
Tree Nodes
( 2 , 3)
( 7 , 4)
( 3 , 5)
( 5 , 8)
( 8 , 2)
( 11 , 2)
( 9 , 4)
Given point : ( 8 , 1)
Not Found
Given point : ( 5 , 8)
Found
Given point : ( 5 , 4)
Not Found
// Scala Program
// K dimensional tree insertion
// 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);
this.setValue(data,k);
}
def setValue(data: Array[Int], k : Int): Unit =
{
var i = 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;
}
// Check if given point exists in tree or not
def search(point: Array[Int]): Unit = {
if (this.root != null)
{
var auxiliary: TreeNode = this.root;
var depth: Int = 0;
var axis: Int = 0;
var result: Boolean = false;
// Find node point
while (auxiliary != null && result == false)
{
axis = depth % this.k;
if (this.isEquals(auxiliary.keys, point) == true)
{
// When get resultant node
result = true;
auxiliary = null;
}
else if (auxiliary.keys(axis) > point(axis))
{
// visit left subtree
auxiliary = auxiliary.left;
}
else
{
// visit right subtree
auxiliary = auxiliary.right;
}
depth += 1;
}
print("\n Given point : ");
this.printData(point);
if (result == true)
{
print(" Found \n");
}
else
{
print(" Not Found \n");
}
}
else
{
print("\n Empty Tree");
}
}
}
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, 2), Array(7, 4), Array(3, 5),
Array(11, 2), Array(5, 8), Array(9, 4),
Array(2, 3)
);
// 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,2)
/ \
(7,4) (11,2)
/ \ \
(2,3) (3,5) (9,4)
\
(5,8)
-----------------
Developed tree
*/
// Print tree elements in inorder form
tree.printTree(tree.root);
// Search nodes
var point1: Array[Int] = Array(8, 1);
var point2: Array[Int] = Array(5, 8);
var point3: Array[Int] = Array(5, 4);
// Test case for find nodes
tree.search(point1);
tree.search(point2);
tree.search(point3);
}
}
Output
Tree Nodes
( 2 , 3)
( 7 , 4)
( 3 , 5)
( 5 , 8)
( 8 , 2)
( 11 , 2)
( 9 , 4)
Given point : ( 8 , 1)
Not Found
Given point : ( 5 , 8)
Found
Given point : ( 5 , 4)
Not Found
// Swift 4 Program
// K dimensional tree insertion
// 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;
}
// Check if given point exists in tree or not
func search(_ point: [Int])
{
if (self.root != nil)
{
var auxiliary: TreeNode? = self.root;
var depth: Int = 0;
var axis: Int = 0;
var result: Bool = false;
// Find node point
while (auxiliary != nil && result == false)
{
axis = depth % self.k;
if (self.isEquals(auxiliary!.keys, point) == true)
{
// When get resultant node
result = true;
auxiliary = nil;
}
else if (auxiliary!.keys[axis] > point[axis])
{
// visit left subtree
auxiliary = auxiliary!.left;
}
else
{
// visit right subtree
auxiliary = auxiliary!.right;
}
depth += 1;
}
print("\n Given point : ", terminator: "");
self.printData(point);
if (result == true)
{
print(" Found ");
}
else
{
print(" Not Found ");
}
}
else
{
print("\n Empty Tree", terminator: "");
}
}
}
func main()
{
let k: Int = 2;
let tree: KTree = KTree(k);
// 2d points
let data: [[Int]] =
[
[8, 2] , [7, 4] , [3, 5] ,
[11, 2] , [5, 8] , [9, 4] , [2, 3]
];
// 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,2)
/ \
(7,4) (11,2)
/ \ \
(2,3) (3,5) (9,4)
\
(5,8)
-----------------
Developed tree
*/
// Print tree elements in inorder form
tree.printTree(tree.root);
// Search nodes
let point1: [Int] = [8, 1];
let point2: [Int] = [5, 8];
let point3: [Int] = [5, 4];
// Test case for find nodes
tree.search(point1);
tree.search(point2);
tree.search(point3);
}
main();
Output
Tree Nodes
( 2 , 3)
( 7 , 4)
( 3 , 5)
( 5 , 8)
( 8 , 2)
( 11 , 2)
( 9 , 4)
Given point : ( 8 , 1)
Not Found
Given point : ( 5 , 8)
Found
Given point : ( 5 , 4)
Not Found
// Kotlin Program
// K dimensional tree insertion
// 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;
}
// Check if given point exists in tree or not
fun search(point: Array < Int > ): Unit
{
if (this.root != null)
{
var auxiliary: TreeNode ? = this.root;
var depth: Int = 0;
var axis: Int ;
var result: Boolean = false;
// Find node point
while (auxiliary != null && result == false)
{
axis = depth % this.k;
if (this.isEquals(auxiliary.keys, point) == true)
{
// When get resultant node
result = true;
auxiliary = null;
}
else if (auxiliary.keys[axis] > point[axis])
{
// visit left subtree
auxiliary = auxiliary.left;
}
else
{
// visit right subtree
auxiliary = auxiliary.right;
}
depth += 1;
}
print("\n Given point : ");
this.printData(point);
if (result == true)
{
print(" Found \n");
}
else
{
print(" Not Found \n");
}
}
else
{
print("\n Empty Tree");
}
}
}
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, 2), arrayOf(7, 4), arrayOf(3, 5), arrayOf(11, 2), arrayOf(5, 8), arrayOf(9, 4), arrayOf(2, 3));
// 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,2)
/ \
(7,4) (11,2)
/ \ \
(2,3) (3,5) (9,4)
\
(5,8)
-----------------
Developed tree
*/
// Print tree elements in inorder form
tree.printTree(tree.root);
// Search nodes
var point1: Array < Int > = arrayOf(8, 1);
var point2: Array < Int > = arrayOf(5, 8);
var point3: Array < Int > = arrayOf(5, 4);
// Test case for find nodes
tree.search(point1);
tree.search(point2);
tree.search(point3);
}
Output
Tree Nodes
( 2 , 3)
( 7 , 4)
( 3 , 5)
( 5 , 8)
( 8 , 2)
( 11 , 2)
( 9 , 4)
Given point : ( 8 , 1)
Not Found
Given point : ( 5 , 8)
Found
Given point : ( 5 , 4)
Not Found

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