CP164 Final: Binary Search Tree Insertion
Binary Search Tree Insertion
Inserting Into a BST
To insert into a BST we perform some of the same steps that we do when searching for a
key in the tree. However, nodes are always inserted as leaves, i.e. at the bottom of the tree
below an existing node, never in the middle of the tree. The important thing to understand,
then, is how to find the correct position of the new value within the existing tree: following
the search rules will always get us to the proper location within the tree. Once we arrive
there we create a new node that becomes the root of a new subtree within the BST.
In the following example we wish to insert the value 13 into the BST. The value 13 ends up
in a node that is the right child of the node containing the value 12:
Inserting the Value 10 Into the BST
It should be clear that the shape of a BST is determined by the insertion order of the values
in the tree. A nicely balanced tree requires that some thought be put into the order in which
items are inserted into the tree. We will examine this in lab.
The last consideration to take into account is what to do with duplicate values? At first we
will work with trees that do not allow duplicates. Duplicate values are simply ignored. We
still have to search the tree to determine if there is a duplicate, but if we find one in the tree
we can stop searching and exit the insertion method. There are a number of approaches to
working with trees that allow duplicates, and we will examine some of them later.
Why Recursion?
At first glance, it seems that an iterative algorithm would perform a node insertion quite
nicely. It would look a great deal like the retrieve algorithm, except that it would fail if a
duplicate value were found, and add a node to the bottom of the tree if no duplicate existed.
However, note that the heights of the nodes containing 12 and 15 are incremented by one to
take into account the fact that their maximum subtree heights have increased by one with
the addition of the new node. These heights cannot be updated from the top down, since
the lower nodes must have their heights updated before their parent nodes. The iterative
insertion algorithm, which works from the top down, does not lend itself to an easy
solution for this.
A recursive solution allows us to update a tree both from the top down and the bottom up.
We can find the location of the new node on the way down the tree, and update the node
heights on the way back up the tree. The insertion code involves the following three
methods:
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
To insert into a bst we perform some of the same steps that we do when searching for a key in the tree. However, nodes are always inserted as leaves, i. e. at the bottom of the tree below an existing node, never in the middle of the tree. The important thing to understand, then, is how to find the correct position of the new value within the existing tree: following the search rules will always get us to the proper location within the tree. Once we arrive there we create a new node that becomes the root of a new subtree within the bst. In the following example we wish to insert the value 13 into the bst. The value 13 ends up in a node that is the right child of the node containing the value 12: It should be clear that the shape of a bst is determined by the insertion order of the values in the tree.
