Overview

The main issue with binary search trees is that they have to be relatively balanced to maintain their efficient time complexity and keeping them balanced can be complicated. There are many solutions to this issue, but one of them is to break away from the limitation of a binary tree and instead have nodes with more flexibility: the 2-3 tree.

Basic Learning Objectives

Before class, you should be able to:

  • Explain what nodes in a 2-3 tree consist of
  • Explain at a high-level how values are added to a 2-3 tree

Advanced Learning Objectives

After class, you should be able to:

  • Implement a basic 2-3 tree

Resources

You should read the following:

Checks

Submit pictures of the following to Moodle.

Given the following 2-3 tree: Diagram of 2-3 tree

Draw the tree after adding each of the following (so you should draw out three trees):

  • 6
  • 3
  • 8