> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-intro-to-algs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-intro-to-algs/part-iii-data-structures/13.-red-black-trees.md).

# 13. Red-Black Trees

## Exercises

### 13.1-1

<figure><img src="/files/2CQS6m3c1uYkaUwEFPt9" alt=""><figcaption><p>Red-black tree with black-height 2.<br>The image was produced with the <a href="https://www.cs.usfca.edu/~galles/visualization/RedBlack.html">Data Structure Visualizations</a> tool.</p></figcaption></figure>

If you color nodes 4 and 12 into black (children of the root node 8), then the resulting tree will have black-height of 3. If you color all nodes into black, then you will get a tree with black-height 4.

### 13.1-2

The node 36 would be placed as the right child of red node 35 in Figure 13.1 (see the book). [Exercise 13.1-8](#id-13.1-8) explains why this cannot be a legal red-black tree.

<figure><img src="/files/SdXY8slW6ZNjqOMKUSvM" alt=""><figcaption><p>Correct red-back tree after inserting node 36 into the tree from Figure 13.1 (see Section 13.3 in the book).<br>The image was produced with the <a href="https://www.cs.usfca.edu/~galles/visualization/RedBlack.html">Data Structure Visualizations</a> tool.</p></figcaption></figure>

### 13.1-3

**Available in the latest revision of the IM.**

### 13.1-4

**Available in the latest revision of the IM.**

### 13.1-5

**Available in the latest revision of the IM.**

### 13.1-6

**Available in the latest revision of the IM.**

{% hint style="danger" %}
The formulas in the IM are wrong, since they also count NIL leaves (external nodes). The largest possible number of internal nodes in a red-black tree with black-height $$k$$ is $$2^{2k}-1$$, whilst the smallest possible number is $$2^k-1$$.
{% endhint %}

### 13.1-7

**Available in the latest revision of the IM.**

### 13.1-8

**Available in the latest revision of the IM.**

### 13.2-1

**Available in the latest revision of the IM.**

### 13.2-2

**Available in the latest revision of the IM.**

### 13.2-3

**Available in the latest revision of the IM.**

### 13.2-4 🌟

{% hint style="success" %}
Shows that any arbitrary $$n$$-node binary search tree can be transformed into any other arbitrary $$n$$-node binary search tree using $$O(n)$$ rotations.
{% endhint %}

**Available in the latest revision of the IM.**

### ★ 13.2-5

**Available in the latest revision of the IM.**

{% hint style="warning" %}
The solution in the IM has a minor error in the proof that doesn't impact the end result. Namely, the expansion of $$(n-k-1)^2=n^2-2kn-2n+k^2+2k+1$$ contains the $$2k$$ term, while the text in the IM has $$k$$.
{% endhint %}

### 13.3-1

**Available in the latest revision of the IM.**

### 13.3-2

Use the [Data Structure Visualizations](https://www.cs.usfca.edu/~galles/visualization/RedBlack.html) tool and watch the resulting tree as you insert the nodes. You can adjust the animation speed to clearly see the re-colorings and rotations.

### 13.3-3

**Available in the latest revision of the IM.**

### 13.3-4

**Available in the latest revision of the IM.**

### 13.3-5

**Available in the latest revision of the IM.**

### 13.3-6

Observe that all nodes accessed via parent pointers in `RB-Insert-Fixup` are exactly those that are encountered by `RB-Insert` while finding the location for the new node. Therefore, `RB-Insert` should store them in a stack, initialized with the sentinel `T.nil`. `RB-Insert-Fixup` would pop and push nodes from this stack, as needed. The procedures for rotations would also need to have access to this stack.

The size of this stack will be commensurate with the height of the RB tree, which is $$O(\lg n)$$. Pushing and popping nodes execute in $$O(1)$$ time, so the asymptotic runtime of `RB-Insert` would remain the same.

### 13.4-1

**Available in the latest revision of the IM.**

### 13.4-2

**Available in the latest revision of the IM.**

### 13.4-3

**Available in the latest revision of the IM.**

### 13.4-4

Create the initial red-black tree according to [Exercise 13.3-2](#id-13.3-2). Use the [Data Structure Visualizations](https://www.cs.usfca.edu/~galles/visualization/RedBlack.html) tool and watch the resulting tree as you successively delete nodes. You can adjust the animation speed to clearly see the re-colorings and rotations.

### 13.4-5

**Available in the latest revision of the IM.**

### 13.4-6

Each row (in order) designates the corresponding case 1-4 from Figure 13.7. Each count remains the same after the transformation (see also the book's explanation for case 2 about $$x$$ pointing to a node with color $$c$$).

| ⍺          | β          | ɣ                               | 𝛿                              | 𝜀         | 𝜁         |
| ---------- | ---------- | ------------------------------- | ------------------------------- | ---------- | ---------- |
| 3          | 3          | 2                               | 2                               | 2          | 2          |
| 2+count(c) | 2+count(c) | 2+count(c)                      | 2+count(c)                      | 2+count(c) | 2+count(c) |
| 2+count(c) | 2+count(c) | 1+count(c)                      | 1+count(c)                      | 2+count(c) | 2+count(c) |
| 2+count(c) | 2+count(c) | <p>1+count(c)<br>+count(c')</p> | <p>1+count(c)<br>+count(c')</p> | 1+count(c) | 1+count(c) |

### 13.4-7

**Available in the latest revision of the IM.**

### 13.4-8

**Available in the latest revision of the IM.**

### ★ 13.4-9

**Available in the latest revision of the IM.**

## Problems

### 13-1 Persistent dynamic sets

**Available in the latest revision of the IM.**

### 13-2 Join operation on red-black trees

**Available in the latest revision of the IM.**

{% hint style="warning" %}
There is a typo in part (e) of the IM. Namely, we should find the smallest key in $$T\_2$$ instead of the largest.
{% endhint %}

### 13-3 AVL trees

**Available in the latest revision of the IM.**

{% hint style="warning" %}
The definition of height in the IM is not consistent with the book (see the proof of Lemma 13.1). This doesn't impact the proof, but may cause confusion.\
\
In the pseudocode, the operators in the two `if` statements comparing `y.right.h` and `y.left.h` should be changed from > to <.\
\
The corrected pseudocode for `AVL-Insert(T, z)` is\
`AVL-Insert(T, z)`\
&#x20; `Tree-Insert(T, z)`\
&#x20; `x = z.p`\
&#x20; `if x ≠ NIL and x.h == 0`\
&#x20;   `x.h = 1`\
&#x20;   `repeat`\
&#x20;     `x = x.p`\
&#x20;     `if x ≠ NIL`\
&#x20;       `subtree-height = x.h`\
&#x20;       `x = Balance(x)`\
&#x20;   `until x == NIL or subtree-height == x.h`
{% endhint %}