> For the complete documentation index, see [llms.txt](https://emory.gitbook.io/dsa-java/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emory.gitbook.io/dsa-java/binary-search-trees/red-black-trees.md).

# 4.3. Red-Black Trees

Red-Black trees preserve the balance at most time by satisfying the following conditions:

* Every node is either **red** or **black**.
* The root and all leaves (`null`) are **black**.
* Every red node must have two black children.
* Every path from a given node to any of its **leaves** goes through the same number of **black** nodes.

{% embed url="<https://www.slideshare.net/jchoi7s/redblack-trees-overview-238749781>" %}

## Red-Black Node

Let us create the [`RedBlackNode`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/tree/balanced/RedBlackNode.java) class inheriting `AbstractBinaryNode`:

```java
public class RedBlackNode<T extends Comparable<T>> extends AbstractBinaryNode<T, RedBlackNode<T>> {
    private boolean is_red;

    public RedBlackNode(T key) {
        super(key);
        setToRed();
    }

    public void setToRed() { is_red = true; }

    public void setToBlack() { is_red = false; }

    public boolean isRed() { return is_red; }

    public boolean isBlack() { return !is_red; }
}
```

* `L2`: if `is_red` is `true`, the color of this node is red; otherwise, it is black.
* `L6`: the color of the node is black by default upon instantiation.

Let us the [`RedBlackTree`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/tree/balanced/RedBlackTree.java) class inheriting `AbstractBalancedBinarySearchTree`:

```java
public class RedBlackTree<T extends Comparable<T>> extends AbstractBalancedBinarySearchTree<T, RedBlackNode<T>> {
    @Override
    public RedBlackNode<T> createNode(T key) {
        return new RedBlackNode<T>(key);
    }
}
```

Finally, let us override `balance()` method that handles 3 cases:

```java
@Override
protected void balance(RedBlackNode<T> node) {
    if (isRoot(node))
        node.setToBlack();
    else if (node.getParent().isRed()) {
        RedBlackNode<T> uncle = node.getUncle();

        if (uncle != null && uncle.isRed())
            balanceWithRedUncle(node, uncle);
        else
            balanceWithBlackUncle(node);
    }
}
```

* `L3`: sets the color to **black** if `node` is the root.
* `L5`: if the color of `node`'s parent is **red**:
  * `L8`: checks if the color of `node`'s uncle is also **red**.
  * `L10`: the color of `node`'s uncle is **black**.

> What about the case when the color of `node`'s parent is **black**?

The following shows a method that handles when both the parent and the uncle are **red**:

```java
private void balanceWithRedUncle(RedBlackNode<T> node, RedBlackNode<T> uncle) {
    node.getParent().setToBlack();
    uncle.setToBlack();
    RedBlackNode<T> grandParent = node.getGrandParent();
    grandParent.setToRed();
    balance(grandParent);
}
```

> Are there any structural changes after this method is called?

The following shows a method that handles when the parent is **red** but the uncle is **black**:

```java
private void balanceWithBlackUncle(RedBlackNode<T> node) {
    RedBlackNode<T> grandParent = node.getGrandParent();

    if (grandParent != null) {
        RedBlackNode<T> parent = node.getParent();

        if (grandParent.isLeftChild(parent) && parent.isRightChild(node)) {
            rotateLeft(parent);
            node = parent;
        }
        else if (grandParent.isRightChild(parent) && parent.isLeftChild(node)) {
            rotateRight(parent);
            node = parent;
        }

        node.getParent().setToBlack();
        grandParent.setToRed();

        if (node.getParent().isLeftChild(node))
            rotateRight(grandParent);
        else
            rotateLeft(grandParent);
    }
}
```

* `L7`: the case of left zig-zag.
* `L11`: the case of right zig-zag.
* `L19`: the case of left linear.
* `L21`: the case of right linear.

The followings demonstrate how the `balance()` method works in Red-Black trees:

{% embed url="<https://www.slideshare.net/jchoi7s/red-black-trees-add>" %}

> How does a Red-Black tree know when it is unbalanced?