Âng-o͘-chhiū

紅烏樹 (Âng-o͘-chhiū) (英語 (Eng-gí): red-black tree) 是 (sī)一 (chi̍t)款 (khoán)二分 (jī-hun)搜索樹 (so͘-sek-chhiū) (binary search tree)，特色 (te̍k-sek)是概念 (khài-liām)上 (siōng)美 (bí)一節 (chiat)node和 (hâm)一个 (chi̍t-ê)色緻 (sek-tī)的 (ê)性質 (sèng-chit)，通 (thang)是紅色 (âng-sek)或者 (he̍k-chiá)烏色 (o͘-sek)相 (siang)款其中 (kî-tiong)之 (chi)一 (it)。利用 (Lī-ēng)對 (tùi)node色緻的漢制 (hàn-chè)，會當 (ē-tàng)戶 (hō͘)認遐 (jīn-hô)一條 (tiâu)根部 (kin-pō͘) (root) 過 (kòe)葉部 (hio̍h-pō͘) (leaf) 的路徑 (lō͘-kèng)莫 (mài)超過 (chhiau-kòe)別 (pa̍t)條路 (lō͘)的雙 (siang)倍 (pōe)長 (tn̂g)，維持 (î-chhî)樹 (chhiū)大概 (tāi-khài)的平均 (pêng-kin)發展 (hoat-tián)。

性質

紅湖樹舉例

紅烏樹是滿 (boán)chio̍k以下 (í-hā)性質的二分搜索樹:

• 逐个 (Ta̍k-ê)node是紅色或者烏色之一。
• 根部 (Kun-pō͘)是烏色的 (o͘-sek--ê)。
• 逐个葉部 (NIL) 是烏色的。
• 若 (Nā)某 (bó͘)一个node是紅色的 (âng-sek--ê)，伊的 (i-ê)兩个 (nn̄g-ê)囡仔 (gín-á) (接出來 (chiap--chhut-lâi)的下層 (ē-chân)) 愛 (ài)是烏色的。
• 米 (Bí)一个node，美一條對彼个 (hit-ê)node痛 (thàng)到 (kàu)接 (chiap)後 (āu)葉埠 (hio̍h-po͘)的單純 (tan-sûn)路徑 (simple path)，怹 (in)當中 (tang-tiong)的烏色node數量 (sò͘-liōng)是相 (sio)siâng的。

參考 (Chham-khó)

• Cormen, Thomas H.; Leiserson, Charles E; Rivest, Ronald L; Stein, Clifford (2009). Introduction to Algorithms (第3 pán.). The MIT Press. ISBN 9780262259460.