紅黑樹- 維基百科，自由的百科全書 - Wikipedia
文章推薦指數： 80 %
紅黑樹
維基百科，自由的百科全書
跳至導覽
跳至搜尋
紅黑樹（英語：Red–blacktree）是一種自平衡二元搜尋樹，是在電腦科學中用到的一種資料結構，典型用途是實現關聯陣列。
它在1972年由魯道夫·貝爾發明，被稱為"對稱二元B樹"，它現代的名字源於LeoJ.Guibas和RobertSedgewick於1978年寫的一篇論文。
紅黑樹的結構複雜，但它的操作有著良好的最壞情況執行時間，並且在實踐中高效：它可以在
O
(
log
n
)
{\displays
