# 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?


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://emory.gitbook.io/dsa-java/binary-search-trees/red-black-trees.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.