Binary Search Trees in C++ – 3 : insert function

The insert function works much like the search function. It takes a data entry and inserts that into the BST whose root is passed as an argument to the insert function.

The key is to find the correct insertion position. This is done exactly the same way as in the search function.

We will look at a nonrecursive version of the insert function.

———-

bool insert ( Node *root, const Item& entry)

{

//firstly, create a new node.

Node *new_ptr = new Node;

if ( ! new_ptr) //memory allocation error

return false;

new_ptr->data = entry;

new_ptr->left = new_ptr->right = 0;

 

//special case where the tree is currently empty.

if ( ! root)

{

root = new_ptr;

return true;

}

//other cases.

Node *temp = root;

while (true)

{

if (entry <= temp->data)

{

if (temp->left == (Node*) 0)

{

//insert here

temp->left = new_ptr;

return true;

}

temp = temp->left;

}

else

{

if (temp -> right == (Node*) 0)

{

//insert here.

temp->right = new_ptr;

return true;

}

temp = temp->right;

}

}

}

————–

The worst case running time for insertion is O(n) while the average case is O(log n).

————–

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: