Back to Basics — Data Structures Vol I: Binary Search Trees
What is the Back to Basics Series?
I named this series Back to Basics, but the name here might be a bit deceiving. Basics here does not imply that the topics talked about will be easy, nor will they be topics that you should already know by heart. But they are topics that will help you have a better understanding of every single line of code you write.
I have this very strong opinion that programming should not just be about writing code. Being a programmer is so much more. It involves knowing how computers work, knowing specific computer logic, and the ability to solve real-life problems programmatically. Nowadays, there are many tools and frameworks that make our job as programmers so seamless and easy. However, this takes away an important aspect, which is understanding what is under the hood of the technology we use. To me, programming is an art form, and an artist needs to know every single detail about the masterpiece they are creating.
This might give a bit of context of what I mean when I say Back to Basics. This blog series is aimed to talk about core concepts that give you a better understanding of computer science in its very core, bareboned, fundamental concepts. For this series, I will be talking about what I know best, data structures and algorithms, each in their own separate blogs. That isn’t the only goal, however. I don’t want to talk about everyday topics. The secondary goal is introducing people to unique, yet very useful, data structures and algorithms. Ones that can be used in many disciplines within the programming field.
Now, with that out of the way, welcome to the first topic of Back to Basics! The first topic for this is a very commonly known data structure that I surprisingly have not seen being used quite enough, and that is the Binary Search Tree. I think this a great topic to start with because it is a basis for several topics like RB trees, AVL trees, and they are also involved in several algorithms that I will be writing about.
What are Data Structures?
To start off, we need a concrete definition of what data structures are. Most of the people reading this blog are probably familiar with what they are, but I think it is better to have a unified definition for the audience of this series, to base everything off of. In summary, data structures are a way to organize data within a bigger set of data.
Let’s use a real-life example. Imagine you are moving from one apartment to another. You have three things left that you need to move to your new apartment: towels, wine glasses, and your cutlery. For each of those things, you will use different packaging. For towels, it's not really consequential where you store them when you are moving. For wine glasses, you want to store it in something that will prevent them from breaking, sometimes they even have their own boxes. For your cutlery, you need to maybe wrap them in something so they would not damage surrounding items. Now let's move back to data structures
Data structures have a very similar mechanic. You have different types of data, with each one having its uses depending on the business and that business’s requirements. Your job as a developer is to choose the data structure that fits your requirements best. Some criteria while choosing data structures are: Frequency of accessing the data, time complexity, how critical time complexity is for your business, etc…
Introduction to Binary Search Trees
Now that we have a unified understanding of what a data structure is, we can dive deeper into binary search trees.
A binary search tree is a data structure that looks as follows:
To understand a binary tree, we have to understand some terms. The first node we have on top is called a root. The root, in this case, has a value of 8. Anything that a node points at are called children. If these children nodes do not have their own children nodes, or in other words, are at the end of the tree, like 4, 7, and 13, they are called leaves. The height of the tree is the maximum distance from the root to the leaves. In this case, the root starts at height 0. Let us call it h = 0. The nodes 3, and 10 are h = 1. The following nodes 1, 6, and 14 are h = 2. And finally, leaves 4, 7, and 13 are h = 3. Meaning that this tree has a height 3. The height is used to calculate the maximum amount of nodes a tree can have, amongst other calculations, but that is a topic for a different day.
In short, a binary tree has one rule of thumb: Anything to the right has a bigger value, and anything to the left has a smaller value, across all levels of the tree. Let me explain more using the tree we have above.
All the children to the right of the root node have to be bigger than 8, and everything to the left has to smaller than 8. And so on and so forth for each node and its children. But, we do see something interesting about the tree. If we go to h = 3, we notice that the leaf with the value 7 is to the right of its parent node with value 6, which abides by the rules. However, something interesting to note is that if we look all the way to the top at the root, we will notice that even three heights down, the leaf still abides by the rule of everything to the left is smaller, as 7 < 8. Usually, when I visually insert something into a binary tree, I go top to bottom, asking myself “Bigger or Smaller”, then going right or left accordingly!
Is it Always Useful?
Without properly taking care of your tree, it might as well become a list. Look at the example below:
When you look at this tree, it isn’t really a tree anymore. This case where it has a worst-case scenario is called a Degenerate Binary Search Tree. That is because there was no proper rotation applied to that tree. Rotation is when you adjust the root of your tree, in order to have the best possible root for it not to act and look like a list. One of these rotation mechanisms and their implementation will be discussed in the next blog. Hint hint: Red-Black!
Use Cases of Binary Search Trees
When a binary tree is implemented properly, there can be several use cases to it. From the visual you saw from the first example of a proper binary search tree above, you already might have concluded some use cases where this structure might be used. But there are ones that automatically pop into my head when I see this diagram.
A binary search tree can be a perfectly sound substitute for a list. The reason is, when a binary search tree is properly implemented, the average time complexity for searching, deleting, and inserting nodes is O(log n). and that is faster than the time complexity of these operations for an array, which has a time complexity of O(n). If you are unfamiliar with time complexity, it is really a worthwhile topic to read about.
This time complexity difference between both an array and a binary search tree can be very important for tasks that are time-critical. The faster you can search for something, the faster the result pops up, which makes the program you write more efficient.
What’s Next?
Like I mentioned at the start of the blog, this is just the beginning, or the bases, of more topics to come. Now that we understand what a binary search tree is, it can give us some understanding of the next topic that I will be writing about in the Back to Basics — Data Structures series, the Red-Black Search tree. A form of a binary search tree that implements the self-balancing and rotation mechanism that the binary search tree lacks.
Having said that, I would like to hear about what you think would be interesting to talk about. Any data structures you find interesting? Any Algorithms? Let me know! It’s always a good time to go Back to Basics!
