> For the complete documentation index, see [llms.txt](https://clu.gitbook.io/data-structure-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://clu.gitbook.io/data-structure-note/1.4.3-red-black-tree.md).

# 1.4.3 Red-Black Tree

樹的平衡: 所謂樹的平衡指的是, 樹中每個節點的左邊後代的數目應該與其右邊後代的數目大致相等(不用完全一樣多).

對於用隨機數構成的二元樹, 一般來說是大致平衡的, 但是對於有順序的資料, 就可能導致二元樹極度的不平衡了. 在最極端的情況下, 甚至會**退化成list**, 此時的時間複雜度會退化到O(n), 而不再是平衡樹的O(logn)了.

![](/files/-M523tkeycMOLWOm88wP)

紅黑樹(R-B Tree): 紅黑樹是增加了某些特性的二元搜尋樹, 它可以保持樹的大致平衡. 主要的思路為: 在插入或刪除節點的時候, 檢查是否破壞了樹的某些特徵, 若破壞了, 則進行糾正, 進而保持樹的平衡.

在JDK中, 以紅黑樹為實作基礎的資料結構如: TreeSet, TreeMap以及最新的HashTable

紅黑樹的特徵:

1. 節點都有顏色(紅/黑)
2. 在插入和刪除的過程中, 要遵循保持這些顏色的不同排列的規則

紅黑樹的規則(紅黑規則):

1. 每個節點不是紅就是黑的(廢話)
2. 根總是黑色的
3. 若節點是紅色的, 則其子節點必為黑色, 反之不必為真(亦即若節點是黑色, 則其子節點可為紅也可為黑), 這條規則其實也是在說明就垂直方向來看, 紅色節點不可以相連
4. 每個空子節點都是黑色的: 所謂的空子節點指的是, 對非葉節點而言, 本可能有, 但實際沒有的那個子節點. 譬如一個節點只有右子節點, 那麼其空缺的左子節點就是空子節點
5. 從根節點到葉節點或空子節點的每條路徑(簡單路徑), 必須包含相同數目的黑色節點(這些黑色節點的數目也稱為黑色高度)

一個滿足紅黑樹規則的二元搜尋樹大概長得像這樣:

![](/files/-M523tkgS-FfQ8a6JvB3)

紅黑樹的修正手段:

1. 改變節點顏色
2. 執行旋轉操作

旋轉操作示意圖:

![](/files/-M523tki5k4z5Ty_YIcZ)

以下是紅黑樹的節點程式碼:

```java
package idv.carl.datastructures.rbtree;

/**
 * @author Carl Lu
 */
public class RbNode {

    private int id;
    private int data;
    private boolean red = true;
    private RbNode parent;
    private RbNode left;
    private RbNode right;

    public RbNode(int id, int data) {
        super();
        this.id = id;
        this.data = data;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public boolean isRed() {
        return red;
    }

    public void setRed(boolean red) {
        this.red = red;
    }

    public RbNode getParent() {
        return parent;
    }

    public void setParent(RbNode parent) {
        this.parent = parent;
    }

    public RbNode getLeft() {
        return left;
    }

    public void setLeft(RbNode left) {
        this.left = left;
    }

    public RbNode getRight() {
        return right;
    }

    public void setRight(RbNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "RbNode{" + "id=" + id + ", data=" + data + ", red=" + red + '}';
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://clu.gitbook.io/data-structure-note/1.4.3-red-black-tree.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.