The Idea of a Binary Search Tree

Today I am going to discuss the idea behind a Binary Search Tree (BST) and how it can be extremely beneficial to learn as a programmer. This data structure was taught to me with great emphasis in CSC148 at UTM and has immensely improved my programming abilities. I believe understanding the concept behind this data structure will help readers gain a deeper understanding into run-time analysis and efficiency. Ultimately, my goal by explaining a BST today is to demonstrate how this data structure can open one’s mind to a world of new great ways to code.

To begin with, the way a BST tree is created and structured is crucial to understanding how it can be beneficial to use. Firstly, to grasp the concept of a BST we must understand what a tree is. The tree used for a BST consists of nodes where each has at most two children nodes connected to it. Any node linked directly above is referred to as a “parent” node. Similarly, any node linked directly below is called a “child” node. As mentioned above, a node can have at most two children; thus, these children nodes are referred to as “left child” and “right child” respectively. Furthermore, a tree consists of special nodes that have designated names assigned to them. For instance, any node with no children is referred to as a “leaf” node. Also, the very first node in the tree is called the “root” node. These key nodes play a crucial role in BST functions such as search, insert and delete which will be explained in the second paragraph from now. Overall, the tree structure of a BST is pivotal to learn in order to understand the benefits of using a BST data structure.

The basic properties of a BST and how it is designed are what make this data structure particularly useful. A BST consists of three basic properties which are: the left subtree of a node only consists of values less than the current node, the right subtree of a node only consists values greater than the current node, and all subtrees must be binary search trees. Essentially, this means that all smaller values are on the left side of a node and all greater ones are on the right. For instance, if we are given the values 1, 2, 3, 4, 5, and we are told that the root will be 3, what does this tell us? This tells us that 1 and 2 will be on the “left” subtree of 3 and that 4 and 5 will be on the “right” subtree of 3 as per the properties of a BST. This is essentially how a BST is built and we will next look at why this is a useful data structure.

The main reason to use a BST is because it extends the capability of a normal array while greatly improving run-time efficiency. One might ask, how does putting numbers into a tree help make functions run faster? The simple answer is that by using the way a BST is organized, we at most have to traverse the height of the tree for the functions search, insert and delete. This is because at each point in the traversal we choose to either go right or left down the tree. The structure of a BST means we will always go down the correct path and never have to look at every other path in the tree. This is beneficial because the run-time of traversing the height of a tree is proven to be O(log n) which is significantly faster than the O(n) run-time of arrays. For example, let’s say we have a sorted array with two million elements and we want to insert a number at index 10. We would have to re-sort every element after index 10 in the list by shifting it over to make room for the newly inserted element. This would result in almost two million operations! On the other hand, if we inserted into index 10 of a BST, it would take approximately 10 operations plus a few more for balancing. This demonstrates the massive difference in run-time obtainable by using a BST over an array.

There are multiple variations of a BST which improve its efficiency even more. For instance, a “balanced” BST is the most efficient and consistent version of a BST. This variation keeps the smallest possible height of the tree at all times by rebalancing itself whenever new elements are added or removed. What this does is minimize the height to traverse for a function call. When looking at a regular BST, it is possible to have O(n) run-time for the functions mentioned above. For instance, let’s look at the elements 1, 2, 3 and 4. If 1 is the root and 2 is its right child, we would end up having a height of 4 for the tree. This means if we were searching for the number 4, we would have to traverse the entire tree; thus, resulting in a run-time of O(n). Although this is unlikely, it is still possible which is why more efficient adaptations of a BST exist. Ultimately, a BST is efficient but it is simply the building block for much greater designs we are familiar with today.

In conclusion, a BST is one of the most fundamental data structures today. This data structure has led to new ways of organizing data and carrying out programs in a faster way. As programmers, it is our goal to create the fastest and most elegant design for anything we code. The BST is only the beginning, there are so many more data structures out there that would immensely enhance one’s coding skills. Next time I create a program, I will remember that just like the BST, there is always a way to make things faster.

Related posts:

Procrastination is an act of postponing, delaying or putting off the things, especially habitually or intentionally. It is actually a habit that gradually develops in us. It might be due to lack of…

Os petistas do governo saíram em defesa da vereadora do PT, Maria Tereza Capra, que chamou os moradores da cidade de São Miguel do Oeste, em Santa Catarina, de nazistas. A vereadora teve o mandato…

Different ways you can call your partner or friends in Chinese and Japanese.