Binary Search Tree in Ruby
I wanted to touch upon a topic we started covering in our last week at Flatiron, which were data structures and sorting algorithms. This week reminded me of my few years of taking computer science courses, creating our own stacks, queues and linked lists. Writing sorting algorithms such as quicksort, mergesort and bubble sort. I was ecstatic to find out we were covering these topics! Remembering how much fun I had with these is partially what got me to change careers and enroll in Flatiron School in the first place. Even back in week 1 I was asking myself, what kind of sort does Ruby use? I learned so many sorts long ago, which one is it? After some Google-ing, interestingly enough, Ruby uses the quicksort algorithm for its sort method over mergesort.
Binary Search Tree
So one of my favorite problems that I came across was constructing your own Binary Search Tree(BST). I am going to walk through my process, but first we need to know what a BST is. A BST is a series of connecting nodes, where each node contains data, a left and a right. The left and right are pointers to a subtree of nodes where left is less than or equal to and right is greater than.
With this information we can start by creating our Binary Search Tree class which will represent our data structure. The walkthrough will consist of the structure and inserting into the BST.
1 2 3
Back to what a BST contains: data, left and right. Data will represent the data we store and left and right will represent subtrees.
1 2 3 4 5 6 7
Great! Now that we have the basic structure of the BST, we will need to be able to insert data into our BST class. Lets create a insert method which takes in 1 argument, data. I’m going to go ahead and pseudocode my thought process of how I think it works.
1 2 3 4 5 6 7 8
We start at the top of the tree and keep track of the location. Following this, compare the data being inserted into our tree with the current location. This will determine if we are going left or right. If that direction results in a nil, we have reached our destination! We insert here, but if not we will need to change the current location to the top of the subtree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
We want to keep doing this process until the data has been inserted into the correct location. Since the number of times this loop will run is unknown, a while or until loop will do the trick with a placeholder variable for confirmation of when the loop is finished.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
Running some tests that were developed prior and eureka!! It works! While our task is complete, I’m not satisfied. To me this looks dirty. The 2 variables declared outside the loop, the loop itself, the seemingly repetitive code inside the loop and all the if-else statements!! I needed to refractor this. So back to thinking about the 5 steps, it appears the first 4 steps are repeated on BST instances, where each time all that is changing is the BST is becoming a subtree of itself. It seems like this can be done recursively.
1 2 3 4 5
With recursion I am able to clean up the code to something I am satisfied with.
1 2 3 4 5 6 7 8 9 10 11
This was just the first step in creating the BST data structure. Next I’ll explore deletion, searching and sorting in Binary Search Trees.