## Jupyter at Bryn Mawr College

Public notebooks: /services/public/dblank / CS206 Data Structures / 2017-Spring / Notebooks

# 1. Self-Balancing Search Trees¶

We looked at Search Trees previously, and we knew that they were better if balanced. Now we explore how to automatically keep them balanced.

## 1.1 Tree Balance and Rotation¶

Most of the algorithms that we will discuss use the ideas of balance and rotation.

## 1.2 AVL Trees¶

We have explored AVL trees very thoroughly.

## 1.3 Red-Black Trees¶

Rules (Invariants):

• initial color is red
• if parent is black, you are done
• else if parent is red, and parent has a red sibling
• change grandparent to red
• change parent/sibling to black
• if root is red, change to black
• else parent is read, but no red sibling
• grandparent to red
• parent black
• rotate around grandparent

Fig 9.22:

1. insert 35
2. 30 and 10 are red, so:
3. change 10, 30, 20
4. done

Fig 9.23:

1. insert 35
2. change 20 and 30
3. rotate grandparent left
4. done

Fig 9.25:

1. insert 25
2. rotate parent to right
3. rotate grandparent to left

Other notes:

• TreeMap - Map interface implemented by a Red-Black Tree, implements SortedSet
• get, put, remove, containsKey - all O(log n)

## 1.4 Non-Binary Trees¶

### 1.4.1 Two-Three (2-3) Tree¶

Children are either 2-node or 3-node

### 1.4.2 B-Tree¶

• n children per node
• useful as a database with fixed "block" size (disk)
• each node has between n/2 and n children

If n = 200, then each node has between 100 and 200 children. Tree of height 4 could hold:

$$100 ^ 4$$

or 100 million values.

### 1.4.4 One-Two-Three-Four (1-2-3-4) Tree¶

A B-Tree with n set to 4.