# Balanced BSTs

{% hint style="warning" %}
Please read [Binary Trees](https://cs61b.bencuan.me/abstract-data-types/binary-trees) before continuing!
{% endhint %}

**Balanced Binary Search Trees** are an even more specific subcategory of binary trees that have an important property: **they are always bushy.** 

## B Trees (2-4 Trees)

**The basic idea:** Nodes can hold multiple values now! When nodes have too many values, we will split it.

A **2-4 tree** is named such because each parent can have **2 to 4 children.** Another constraint we will put on is a **limit on the** **number of items allowed in a single node**, so that we can guarantee that searching a single node will always be $$\Theta(n).$$ 

### **Adding Values to a B-Tree**

Adding values to a B Tree can be a bit tricky because we need to make sure all the properties are still followed. Here are some example scenarios:

If a node already has 2 or more children, place the new value in one of its existing children.

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M78zVO5Z6VYMKZc8So6%2F-M794KDai2r46bedgKYV%2Fimage.png?alt=media\&token=fbaea114-ec6f-47a1-95af-c63b898d7036)

If a node is full (reaches the limit), we must **split the node** by **moving one value up to the parent** and **creating another child node**. Here, we'll use a limit of **3**.

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M78zVO5Z6VYMKZc8So6%2F-M794MCs85xfYD1iRn_j%2Fimage.png?alt=media\&token=366fb600-e6b3-49b1-b2f6-f3f5a904e0ce)

### Properties of B Trees

* Searching in a single node is **constant runtime** since the limit is a constant.
* All leaves must be the **same distance** from the root. 
* A non-leaf node with **k** items must have **k+1** children.
* The height of a B tree is guaranteed to be $$\Theta(\log(n))$$ because it is bushy.

## Red-Black Trees and Tree Rotation

**The basic idea:** Let's try to represent B trees in a **binary tree format.** That means that every parent can only have 2 children! In order to do this, we'll **add an extra color property** to each node.

**Black nodes** are just like any normal binary tree node, but **Red nodes** represent the nodes in B Trees that have **more than one value.** For example, let's convert the B Tree we were working with before into a RB Tree.

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M78zVO5Z6VYMKZc8So6%2F-M795SliFvUXgGpkyr_l%2Fimage.png?alt=media\&token=735dc227-c9ce-4a1f-a2a7-a7eb4a5455bf)

In order to make our lives easier, we'll restrict our Red Black trees into **left leaning red black trees** which can **only have red nodes on the left.** 

### **Tree Rotation**

In order to ensure that adding new nodes won't break the Red Black Tree structure, we will use a concept called **tree rotation** which swaps around nodes. There are two rotations, a **left rotation** and a **right rotation,** which move a child node up to replace its parent. For example, a **left rotation** moves the **right node up and left** to replace the parent.

A "left rotation on 7" looks like this:

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M78zVO5Z6VYMKZc8So6%2F-M797s0W-gA4QXWRWOcT%2Fimage.png?alt=media\&token=7f1a963f-7de6-4571-b1ba-404ce5ce54df)

Notice that the **8** gets moved to be a **right child** of **7** after the rotation! This is necessary to preserve the binary tree structure.

A "right rotation on 7" looks like this:

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M78zVO5Z6VYMKZc8So6%2F-M7985iSi34V1DrVhW3a%2Fimage.png?alt=media\&token=7747776e-7ddc-478e-943b-f44f3698c27b)

Here, the **6** gets moved to be a **left child** of **7.**

If you want to see how these rotations can be implemented into the `insert` algorithm, [try the homework](https://inst.eecs.berkeley.edu/~cs61b/sp20/materials/hw/hw8/index.html) on implementing a LLRB Tree! Below is a brief outline on how insert works:

* **Always add values to a leaf node as a red node first.** Follow normal sorted binary tree rules.
* If the link is leaning right, rotate the tree to make it left leaning.
* If a node already has a red link to the left, temporarily add it to the right also as a red link.
  * Then, flip the color of all links connected to the node (if previously black, turn red; if previously red, turn black)
  * Might need to fix right-leaning red nodes that are created as a result
* If a node has red links to both parent and child, rotate it such that it becomes the above case, and then handle that case like you did before.

### Properties of Red Black Trees

Like B Trees, Red Black Trees have some important properties that allow them to be easily distinguishable.

* Red Black trees have a **one-to-one correspondence** with B trees. That means for every Red Black tree, there is exactly one B Tree that represents the same connections. This also means that a Red Black Tree will have the same runtimes as their corresponding B Trees. (Take a linear algebra course to learn more about isomorphisms 🙂 )
* **Every node must have the same number of black nodes in between itself and the root.** This might be a bit surprising at first, but remember that their corresponding B Tree is always bushy, and red links mean a multi-value node in a B Tree.