Algorithms & Data Structures: Self-Balancing Trees
Recently, I’ve decided to revisit some core computer science fundamentals and take a look at some of the most common algorithms and data structures. My background in college was MIS so we didn’t study much computer science theory or algorithms and data structures. Since I’ll be on the job hunt in the next few months, I thought it’d be a great idea to revisit some topics I had learned throughout the years and on the job. This post and subsequent posts titled “Algorithms & Data Structures I & II” are a review of the video series on Pluralsight but rewritten in Ruby. You can view the series here, assuming you have a Pluralsight account,https://www.pluralsight.com/courses/ads-part1&https://www.pluralsight.com/courses/ads2
In the following post, we’ll be covering the AVL tree or self-balancing tree. Before diving into this topic, it’s strongly encouraged that you have a solid understanding of how a regular binary tree functions. Also, for this topic, I’ll be taking a slightly different approach from explaining the functionality to seeing the actual code. Since these posts are based off the video series, Robert Horvick also has a PDF version. I won’t be explaining this topic, since it’s all explained way better than I could have explained things. Below is the PDF and you’ll want to start at page 71. Below this will be the code translated into Ruby.