Hello and welcome! This is part two of a blog post series on the binary search tree data structure.
If you have not real my previous post, I highly recommend you to read introduction to the binary search tree before proceeding.
Finally, in this post, we will be writing our own binary search tree implementation, dissecting the key operations and understanding exactly how the binary search tree works under the scenes.
Attached below is our Binary search tree interface. The available public methods are
add(data): Should be common sense that consumers should be able to add items to the tree.
remove(data): Search for the data to remove and remove it from the tree.
max(): Return the “largest” data from the set by traversing to the far right of the tree.
min(): Return the “smallest” data from the set by traversing to the far left of the tree.
Re-iterating the importance of assumptions, it is because of the rules, that we are able to implement the
max() method in a sound and cohesive manner. Once you have gotten the hang of Binary Search Trees, feel free to extend the API and add your own methods.Continue reading
The binary search tree is a fundamental data structure in computer science. Just as with all other data structures and algorithms, the binary search tree is built on specific rules and assumptions. These assumptions, enable us to examine the shortcomings of previous data structures such as the linked list, and improve the search time. In this article, we will explore the binary search tree data structure and some of the searching algorithms used.
Please do take note that this is part one of a series of posts on the Binary Search Tree. The Implementation details will be provided in part 2, along with a detailed guide on how to implement the binary search tree.
Well, it is because of these assumptions that we are able to get such high performance from certain data structures. Assumptions enable us to code specifically. For example, if we only had forks to eat food with, it would definitely be inconvenient to eat rice. Hope you understood my analogy in the previous sentence. As the same suggests, the binary search tree enables us to search for items much more quickly. If we didn’t have the binary search tree, we might have to just do a brute force search. The time complexity for the brute force search would be O(n). With binary search trees, it is possible to reduce the search time to O(log n). In the worst case situation however, the search time can be the same as with a brute-force search O(n).
Now that we understand the need for assumptions, we will examine the key features.
c++ const is used very commonly. If you have ever written any code in C++, you will definitely have used
const and come across it. Needless to say, is a very useful and important feature. Using c++
const can greatly improve the robustness of your code. It is also a great way to document to other developers that the object marked as const should not be modified. On the other hand, omission of the
const keyword in places where it is needed results in more brittle, error-prone code.
In a nutshell,
const (constant) means that a property or value cannot change.
Separating code into smaller parts by placing them inside of a function (based on operation) allows developers to easily look up which part is responsible for certain features, making the debugging process much more pleasant.