---
tags: fall 2018 cs61b
---
# 2-3/2-3-4 Trees
[TOC]

## Introduction

### Terminology
* **Node:** refers to the struture containing the numbers (ex. 15 35 45)
* **Element:** refers to the numbers inside the node (ex. 15)
* **Children:** refers to the nodes stemming out from one arbitrary node

### Properties
* Should still follow the BST property (less on the left, greater on the right)
* For a 2-3-4 tree, each node contains 1-3 elements with 2-4 children nodes
* For a 2-3 Tree, each node contains 1-2 elements with 2-3 children nodes

## Common Insertion Misconceptions
### Where to Insert
Suppose we want to insert 13 into the 2-3 tree below.

**Issue:**
A common misconception is to insert the 13 into the node with the closest number. It seems to make sense because 10 is still smaller than 13 and 15 and 16 are still greater than 14.

**Correct Way:**
However, this is incorrect! The correct resulting 2-3 tree should look like the one below.

**Key Takeaway:** **Always insert into a leaf node.**

### Pushing up Nodes
Suppose we want to insert 17 into the 2-3 tree below.

**Issue:**
Since we know the 15-16 node will be full with the insertion of 17, we must push the 16 up. However, a common misconception is to keep 16 at the same level and create a new level for its children nodes.

**Correct Way:**
Instead, the correct way is to push the 16 up to the previous level with 14! Intuitvely, we can realize that the previous 2-3 tree becomes even more unbalanced if we create a new level while the one below maintains its previous height.