Declaring BST::insert()
The stub of BST::insert() should look like this:
void BST::insert(const Item& item) {
}
Defining BST::insert()
The BST::insert(item) method needs to distinguish
between the two cases (empty and non-empty):
- If the BST is empty:
- Create a new node containing item
and store that node's address in myRoot.
- Otherwise (there is at least one node):
- Try to "pass the buck" to the root node
by invoking Node::insert(item)
on the node whose address is in myRoot.
- Catch any exception it throws; throw it on to the sender of the insert() message.
- In either case (when no exception was thrown), increment myNumItems.
Designing Node::insert()
Since a Node is recursively defined, we might define
Node::insert(item) as a recursive method.
One way to design a recursive algorithm for this method is as follows:
Basis. There are three trivial cases:
-
If item belongs in my left subtree and my left subtree is empty:
-
Make my left subtree a new node containing item.
-
If item belongs in my right subtree and my right subtree is empty:
-
Make my right subtree a new node containing item.
-
If item does not belong in our left or right subtrees
(i.e., its value is the same as myItem):
- We will treat our BST like a mathematical set
(which has no redundant elements)
and throw an exception to alert the user
that they have inserted the same Item more than once.
Induction Step. Again, there are two cases:
-
If item belongs in my left subtree and my left subtree is not empty:
-
"Pass the buck" to the node in my left subtree
by asking it to insert item.
-
If item belongs in my right subtree and my right subtree is not empty:
-
"Pass the buck" to the node in my right subtree
by asking it to insert item.
Defining Node::insert()
These observations can then be reorganized into
the following algorithm for our Node::insert() method:
- If item is less than myItem:
- If myLeft is nullptr:
- Set myLeft to the address of a new node containing
item.
- Otherwise:
- "Pass the buck" by recursively calling
myLeft->insert(item).
- Otherwise, if item is greater than myItem:
- If myRight is nullptr:
- Set myRight to the address of a new node containing
item.
- Otherwise:
- "Pass the buck" by recursively calling
myRight->insert(item).
- Otherwise (item must be equal to myItem):
- throw an Exception indicating that item is already in the BST.