Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

Georgia Institute of Technology

Data Structures & Algorithms III: AVL and 2-4 Trees, Divide and Conquer Algorithms

Georgia Institute of Technology via edX


This Data Structures & Algorithms course completes the data structures portion presented in the sequence of courses with self-balancing AVL and (2-4) trees. It also begins the algorithm portion in the sequence of courses. A short Java review is presented on topics relevant to new data structures covered in this course. The course does require prior knowledge of Java, object-oriented programming, and linear and nonlinear data structures. Time complexity is threaded throughout the course within all the data structures and algorithms.

You will investigate and explore the two more complex data structures: AVL and (2-4) trees. Both of these data structures focus on self-balancing techniques that will ensure all operations are O(log n). AVL trees are a subgroup of BSTs and thus inherit all the properties and constraints from BSTs. Additionally, AVLs incorporate rotations that are triggered when the tree is mutated and becomes out of balance. (2-4) trees are a subgroup of B-Trees and are non-binary trees with more than 2 children. 2-4 defines the range of children that exists in the trees. However, these trees are extremely flexible and allow the nodes to shrink and grow as needed to store more data. With this flexibility comes more issues to handle, like overflow and underflow which require more intense techniques to resolve the issues.

As you enter the algorithm portion of the course, you begin with a couple of familiar iterative sorting algorithms: Bubble and Selection. There are optimizations that can be included in the standard Bubble sort to make it more adaptive in sorting. There is also a derivation of bubble sort, called Cocktail Shaker sort, that puts new a spin on the basic algorithm. Insertion sort is the last iterative sort that is investigated in this group of sort algorithms. Divide & Conquer sorting algorithms are examined and are broken into two groups: comparison sorts and non-comparison sorts. The two comparison sorts are Merge and In-place Quick sort. Both are recursive and focus on subdividing the array into smaller portions. LSD Radix sort is the non-comparison sort that deconstructs an integer number and examines the digits. All algorithms are analyzed for stability, memory storage, adaptiveness, and time complexity.

The course design has several components and is built around modules. A module consists of a series of short (3-5 minute) instructional videos. In between the videos, there are textual frames with additional content information for clarification, as well as video errata dropdown boxes. All modules include an Exploratory Lab that incorporates a Visualization Tool specifically designed for this course. The lab includes discovery questions that lead you towards delving deeper into the efficiency of the data structures and examining the edge cases. This is followed by a set of comprehension questions on topics covered in the module that count for 10% of your grade. The modules end with Java coding assignments which are 60% of your grade. Lastly, you'll complete a course exam, which counts for the remaining 30% of your grade.


Module 0: Introduction and Review

  • Review of important Java principles involved in object-oriented design
  • The Iterator & Iterable design patterns, and the Comparable & Comparator interfaces
  • Basic “Big-Oh” notation and asymptotic analysis

Module 8: AVL Trees

  • Explore the AVL tree subgroup from Binary Search Trees (BST) and their distinguishing properties
  • Discover the self-balancing of AVL trees, and which rotations are used to balance
  • Implement the entire AVL tree data structure, and examine its performance

Module 9: (2-4) Trees

  • Extend understanding of tree structures beyond binary trees to a more complex model
  • Study the properties of (2-4) trees, and how operations maintain those properties
  • Recognize when overflow and underflow situations arise within the (2-4) tree, and how to resolve those situations with promotion, fusion and transfer

Module 10: Iterative Sorting Algorithms

  • Understand and implement four basic iterative, comparison sorting algorithms: Bubble Sort, Insertion Sort, Selection Sort and Cocktail Shaker Sort
  • Examine the characteristics of sorting algorithms: Stability, Adaptation and Memory
  • Implement optimizations of these algorithms to yield better performance
  • Analyze the time complexity of each of the algorithms

Module 11: Divide & Conquer Sorting Algorithms

  • Introduction to the Divide & Conquer approach to sorting algorithms
  • Implement and comprehend each of the divide & conquer algorithms presented: Merge Sort, In-Place Quick Sort and LSD Radix sort
  • Examine the stability and memory usage of these sorting algorithms
  • Explore the novel approach that LSD Radix sort uses to solve the sorting dilemma

Taught by

Mary Hudachek-Buswell


4.8 rating, based on 5 Class Central reviews

Start your review of Data Structures & Algorithms III: AVL and 2-4 Trees, Divide and Conquer Algorithms

  • Anonymous
    Really good course. The lectures are consistently divided in < 10 mins chunks, each focusing on one thing to cover, so it's as easy to binge them as it is to segment the learning experience. Perhaps due to the nature of the course, it was also prett…
  • Helped me to learn about advance tree data structures and different types of sorting algorithms with ease
  • Anonymous
    I just successfully finished the verified track of GTx CS1332xIII, AVL and 2-4 Trees, Divide and Conquer Algorithms. Overall, it's a very good class. The choice and presentation of the material is outstanding. The TAs are very responsive and hel…
  • Profile image for Anton Nikulin
    Anton Nikulin
    One of the best course I've taken. Love the tests, they are well written and clearly states what is wrong with your solution.
    Few things to improve:
    - some tests could be better.
    - more coding exercises, it would be good, in addition to implementing algorithm or DS, to have few coding tasks to solve some real life problem.

    Overall great course 5/5

    P.S. Please do a follow up with more algorithms and data structures
  • Anonymous
    Overall this was a great course, covering a lot of material. There are two things I would like to see improved.

    First, fix the errata, especially in the psuedocode. At least give us a clean copy within the text.

    Second, I needed more detail on how adding and removing are supposed to work in 2-4 trees. Just fooling around with the visualization tool isn't enough. If it's a bit too difficult to code for homework, maybe you could make it "fill in the blanks" the way you did in the AVL balance method homework.

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.