---
tags: 進階資料結構
title: 紅黑樹
---

:::success
# 紅黑樹 Red-Black Tree
#### <font color="blue">*set、map等關聯容器背後的資料結構*</font>
## 定義
- 二元樹
- 每個node只有黑和紅兩種顏色
- 根節點為黑色，葉節點為黑色空指標
- ==紅節點的子節點必為黑節點(不能有連續的兩個紅節點)==
- ==從任一節點到其葉節點的所有捷徑包含相同數量的黑節點==

## 性質
- 為自平衡二元樹的一種
- 從根到葉子的最長的可能路徑不多於最短的可能路徑的兩倍長

## 操作實現

###
:::