CP164 Midterm: BST Insertion
BST Insertion: Call Trace
A Call Trace is simply a visual representation of a series of recursive function calls. Each call is
indented to show the ownership of the call and to show the differences between the base and
general cases. Return values, if any, are also shown. The following is a call trace of the insertion
of 13 into the sample tree. Node values are enclosed in{}.
insert(13)
_insert_aux({11}, 13)
_insert_aux({15}, 13)
_insert_aux({12}, 13)
_insert_aux(None, 13)
# Base case - new node inserted.
_BSTNode(13)
return {13}
{13}._update_height()
return {13}, True
{12}._update_height()
return {12}, True
{15}._update_height()
return {15}, True
{11}._update_height()
return {11}, True
return True
Visually, the increasing indentation in the call trace shows the search being done down through
the tree. The decreasing indentation shows the recursive calls finishing and working their way
back up through the tree. When the recursive calls return to the root node, all of the subtrees that
could possibly be affected by the value insertion have had their heights updated.
Binary Search Tree Deletion
Inserting nodes into a BST is fairly straightforward. Deleting a node from a BST is not.
Deleting a node may cause major shifts in the positions of the rest of the elements in the
tree. We will look at deleting nodes from various positions in the tree and how that affects
the structure of the tree. Starting with the BST:
Sample BST
If we wish to delete the node containing the value 18, it is fairly straightforward. First, we
have to find the node to delete, keeping track of its parent in much the same way that we
kept track of the previous node when removing a value from a singly-linked list. Note,
however, we have to keep track of whether we are removing the parent node's left or right
child.
There are three types of BST node deletion:
Document Summary
A call trace is simply a visual representation of a series of recursive function calls. Each call is indented to show the ownership of the call and to show the differences between the base and general cases. The following is a call trace of the insertion of 13 into the sample tree. Visually, the increasing indentation in the call trace shows the search being done down through the tree. The decreasing indentation shows the recursive calls finishing and working their way back up through the tree. When the recursive calls return to the root node, all of the subtrees that could possibly be affected by the value insertion have had their heights updated. Inserting nodes into a bst is fairly straightforward. Deleting a node from a bst is not. Deleting a node may cause major shifts in the positions of the rest of the elements in the tree.
