C++ - Binary Search Tree - Insertion
There are two function Insert and Insert2 are given on this page for inserting a node into a binary tree. Insert function will not do any balancing and in worst case if you keep adding the elements either in ascending or descending order, then the depth of the binary tree would be huge. The insert2 function does one level of optimization and not the complete optimizatioon.
All the nodes to left are less than the current node value and all nodes to the right are greater than the current node value. It would be true for each and every node in the binary search tree. Click here for validating binary search tree.
typedef struct _BSTNode
{
struct _BSTNode *left;
struct _BSTNode *right;
int data;
} BSTNode;
static BSTNode *root = NULL;
BSTNode* Insert(BSTNode* node, int data)
{
if(node == NULL)
return NewNode(data);
if(data <= node->data)
{
if(node->left == NULL)
node->left = NewNode(data);
else
node->left = Insert(node->left, data);
}
else
{
if(node->right == NULL)
node->right = NewNode(data);
else
node->right = Insert(node->right, data);
}
return node;
}
BSTNode* Insert2(BSTNode* node, int data)
{
if(node == NULL)
return NewNode(data);
if(data <= node->data)
{
if(node->left == NULL)
{
node->left = NewNode(data);
}
else
if(node->right == NULL)
{
// Rearrange
int temp = node->data;
node->data = node->left->data;
node->right = node->left; // reuse valid left pointer
node->right->data = temp;
node->left = NewNode(data);
}
else
{
node->left = Insert2(node->left, data);
}
}
else
{
if(node->left == NULL) // left must be filled in first
{
// swap the values
int temp = node->data;
node->data = data;
data = temp;
// insert now
node->left = NewNode(data);
}
else
{
if(node->right == NULL)
node->right = NewNode(data);
else
node->right = Insert2(node->right, data);
}
}
return node;
}
|
|