Before proceeding, be warned: The AVL tree implementation in Java is fairly challenging. It requires users to have a strong working knowledge of the Java programming language. Furthermore, I also recommend users to have an understanding of the binary search tree.
For the sake of technicality, we are now going to refer to the data node values as keys or refer to them simply by the numeric value E.g. 7. In past tutorials, I called them node values, but from now on, we will refer to its proper term: keys.
We will also be writing out pseudo code for each of the operations. Pseudo code is a high-level description of an algorithm or a computer program. Pseudo code is generally written to be read by other human beings. Therefore, pseudo code enables us to abstract out the low-level operation, and focus purely on the logic.
As a software engineer, writing pseudo code can help you organize your thoughts and extract it into written form. Thus, it opens up a pathway to share and communicate your thought process and ideas to your team.
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.