A binary search tree is just a binary tree in which the values are added so that values greater than or equal to the root are placed in the right tree and smaller are placed in the left tree. This makes it easier to find and add nodes to the tree. The more balanced a tree is the faster is can work.
class BSTNode
{
public:
BSTNode() : baseRoot(NULL) {}
static size(BSTNode* root); //same as before
static depth(BSTNode* root); //same as before
static void add(BSTNode* root, int num); //adds num to tree, calls addR()
static void remove(BSTNode* root, int num); //removes num from tree
static void removeAll(BSTNode* root); //delete all nodes under and including root
private:
int data;
BSTNode* left;
BSTNode* right;
void addR(BSTNode* root, int num) //recursive fuction that actual adds root
static void delRoot(BSTNode* root); //removes root, needed for remove
BSTNode* findParent(BSTNode* root, int num); //finds parent of int from root
};
The functions here are tricky so they will be guided through. First is add(). The add() function just calls the add recursive function. The addR() function adds the number to the tree with the given node as the root. Since add() will give the real root node addR() can trace through the other trees. Now what will addR() do. Basicially it will check num against the data. If it is less than then addR() to the left. If it is greather than or equal, then addR() to the right. This will zoom the calls down the tree until a NULL is reach. So when the value is NULL a need BSTNode is attached to the tree. Remeber though that NULL must be check first before anything is done.
Removal from the binary tree is probably the most complete function so far. It is divided into three parts. First is the delete the root function, then is the find the parent of function, and finally the remove function which calls them. The delRoot() function returns the tree in which the root have been removed and there are three cases for it.
The first is when the left side is NULL and the right side isn't. (These implementations can refer to the left or right since the function calls are recursive and end up on a node at some point. I will use left because that is what was in my notes.) In that case just return the right node.
The second case is when the right link of the root's left child is NULL. In that case just set the root's left child's right link to the root's right node, and return the left child. A binary search tree will still exist since the root's right subtree is still greater than the root's left node.
If neither case exists then the middle number is made the root. The middle number will either be the right most node on the root's left subtree or the left most node on the root's right sub tree. In this case find the right most on the left (RML). Then make RML's parent link to RML's left subtree. Finally make the left and right subtrees of the root RML's right and left subtree, and return it. All the while do not forget to delete the root node as needed.
Here is a table with graphical representation. Green is the return value, red are the edit marks, and dots mean that the tree can possible continue in the direction.
| Case | Solution | Model |
|---|---|---|
| Left subtree is NULL | Return Right subtree |
|
| Right subtree of Left subtree is NULL | Link the Left subtree to the Right and return it |
|
| Everything else | Find the right most node of the Left subtree. Link its parent to its left subtree, link it to the left and right subtree |
|
Finding the parent is a simple traversal through the trees. However since the parent is what is being searched the checks are offset by one child. This creates a special precondition in that the root is neither the target nor NULL. If the target is not found then NULL is returned otherwise the parent is. This brings up an importnant point in dealing with recursion and functions in that ALWAYS KNOW THE PRE AND POST CONDITIONS!
Finally to remove a node with the two helper functions. First check for NULL as usual. Next check the obvious that the root itself is to be removed. If not then the number to be removed is somewhere in the tree. Use findParent() to get a pointer to that node, then use delRoot() to remove it all the while checking for special cases.
This is in place of the destructor normally in a class. Since the binary search tree is very dynamic this function will be called to free up memeory. It is a simple travserval, but is must be postfix. Since any other one will delete the roots before thier subtree can be deleted, and memory leaks will ensue.
Like the plain binary tree the binary search tree's performance are based on how balanced the tree is. All the functions use simple operations with recursive calls. If the tree has alls its nodes to the left or right, functions are linear. If the tree is "bushy" it has logarithmic performances.
Prev -- Back to Portal -- Next