Binary Search Tree
I’m doing the rest of part one of the assignment today, the binary search tree.
In my recent post I explained my linked list and what a binary search tree is. I’ll just link the wikipedia link to a binary search tree here if you want to read about them before I explain how I made mine.Binary Search Tree
It is a template class with T as the template type meaning basically that T is any type that has been defined by the user, such as an int or a float.
I will try to make my blogs easier to overlook so I am now listing my functions and explain them, but first a link to the code! CODE. the comments are strange in paste bin’s text formatting.
- void insert()
- Node* search()
- void erase()
- void removeLeaf()
- void RemoveWithOneChild()
- void RemoveWithTwoChildren()
- int size()
- void Traversal_pre_order()
- void Traversal_post_order()
- void Traversal_in_order()
- void delete_post_order()
void insert(T data)
This function first looks to see if the root node is empty and allocates a new node and set root to point to it. If not it looks whether the new node’s data is larger or lesser than the root’s data. If it is larger it checks if the node the right link points exists, and if the data is lesser than the root it checks the left link. The same thing is done for every node that is already in the tree until it encounters a nullptr link. Then that link is set to point to the new node.
Node* search(T data)
This node searches the nodes in the tree in the same manner, look to the right link if the data from the parameter is larger than the current node and to the left if the data is lesser. If the data is equal then it returns a pointer to that node. If it is not found it returns nullptr. This is because when you want to erase a node, you can reach that node directly via a pointer to it. Plus should the nodes in the tree hold many different types of data, all of the different data types can be accessed via this pointer.
void erase(T data)
Erases a node based on its data. This is probably the most complicated function because depending on where in the tree the node is located, different methods must be used to maintain the structure of the tree.
Let’s start with the simplest case: the node to be erased is a leaf node, meaning it has no nodes after it. This one can simply be erased. The only thing that has to be considered is that the link that used to point to this node must be set to nullptr, or else there can be errors if some other function tries to access data on this freed memory location.
The second case is if the node to be erased has one child. In this case, the parent of the node to be erased is linked to this child instead, and then the node can be safely deleted. If this node had its own children, they will be maintained linked in the tree, because its own links will still point to the same memory locations.
The third case is if the node to be erased has two children. What the function in this program does here is that it replaces the node’s to be erased data with the closest value data in one of the node’s children or ‘grand children’.
This is done by either choosing the left most grand child of the node’s to be erased right child. Or symmetrically, the right most grand child of the node’s to be erased left child. This function goes to the right and then to the left most node. When the data values are swapped, the node furthest down can be erased.
This figure is how a node with two children can be deleted (left) and how a node with one child can be deleted (right)
The function accomplishes this by making use of the separate functions :RemoveLeaf(Node* previous, Node* eraser), RemoveWithOneChild(Node* previous, Node* eraser) and RemoveWithTwoCHildren(Node* previous, Node* eraser). (in one of these function there is a redundant parameter T data that I simply forgot to remove.) These are the functions that take care of these operations, and the erase function checks the conditions to determine which of the functions to call and calls them.
Simply returns a member int m_size which is pre – incremented and pre – decremented when a new node is added and removed.
void Traversal_pre_order(Node* node)
This function traverse the tree in a specific order. The order, at least in my function is like this: start by the root, print its value and then recursively call the function again with the left link and print every one until reaching a nullptr node. This exits the current function call and continue where the last function call ended, namely the previous node. There another recursive call but with its right link and print every one of those until nullptr.
In other words, print every node to the left and then every node to the right of the previously printed nodes.
void Traversal_post_order(Node* node)
This one works the same way only the printing of data is the last thing that happens in the function. This way all nodes to the left are traversed until nullptr and then the left nodes of the right nodes, and when all the nodes have been traversed, they are printed in reverse order.
void Traversal_in_order(Node* node)
In this function the printing takes place in between the recursive calls. This walks to the smallest data value (farthest down left), print its data when the left child is nullptr, then checks any right child, and goes down as far left as it can. The result is this prints all values from smallest to largest in order.
void Delete_post_order(Node* node)
Finally, I wanted to clear all the nodes in the tree and I noticed that the root was traversed last, or at least printed last in the traversal post order algorithm. That means that this is perfect for deleting the nodes, because then all the nodes would be deleted in an order that deleted the root last.
I don’t know if this works for all cases, unfortunately. Say the tree had been dealt with in a manner that the root only had, say right children. But I believe that it would still work because it would still traverse all the right nodes’ left children and delete in reverse order or symmetrically the left side. So I think that my idea is general for this purpose.
Summary – Binary Search Tree
So that was pretty much the what and how I did it and in some cases why. I can try to explain why I did the erase functions (except the delete post traversal) iterative and the traversal functions recursive. The erase functions became iterative because that was how I looked upon the problem from lectures and the notes I made while thinking about these problems. I drew a lot of boxes with diagonal right and left links and arrows here and there to try to figure out how I would go about doing it. This way of looking at the problem was very iterative and that reflected in how I coded it.
The traversal functions was recursive quite simply because I saw a class mate do her functions like that. I had no idea how I was going to make them before I saw her functions and I must say, I really enjoy how recursive functions work in general, not only in programming, but also mathematics such as fractal geometry, where the whole picture can be described by many elements identical, or similar to the whole and vice versa, or to give another concrete and simpler example: N! (factorial). The product of N! can be described like this; N! = Nx(N-1!). If you look at this you can realize that you call the same function N!, but with a smaller version of the original: N-1. This is done until the stopping condition 0!, which is defined to be = 1.
A numerical example N = 5:
5! = 5 x (4!) = 120 which is the same as doing this:
5! = 5 x 4 x 3! = 5 x 4 x 3 x 2! = 5 x 4 x 3 x 2 x 1! = 5 x 4 x 3 x 2 x 1 = 120.
So I went over the traversal functions until I understood them, which made me feel ok about using them. These could be translated into an iterative process as well but the code would be both longer and more difficult to read. I think that a while – loop with two pointers, one to iterate and one to take the place of its parent, much like I have done in the iterative functions, and a few if-statements and a print at the correct placement would do the trick as well. Perhaps a few loops after one another because you would need the ‘grand parents’ all the way back to the root at least in the post order traversal.
Hope it was of some use.
For assignment part two we will create a web server in C. This will be tricky since I have no experience in this before.