Algorithms & Data Structures: Self-Balancing Trees

Introduction

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

Topic

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.

Like what you read? Give Jon Shyu a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.