红黑树维基百科,自由的 encyclopedia 红黑树(英语:Red–black tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型用途是实现关联数组。它在1972年由鲁道夫·贝尔发明,被称为“对称二叉B树”,它现代的名字源于利奥尼达斯·J·吉巴斯和罗伯特·塞奇威克于1978年写的一篇论文。红黑树的结构复杂,但它的操作有着良好的最坏情况运行时间,并且在实践中高效:它可以在 O ( log n ) {\displaystyle {\text{O}}(\log n)} 时间内完成查找、插入和删除,这里的 n {\displaystyle n} 是树中元素的数目。 Quick Facts 红黑树, 类型 ...红黑树类型树发明时间1978年发明者利奥尼达斯·J·吉巴斯、罗伯特·塞奇威克用大O符号表示的时间复杂度算法 平均 最差空间 O ( n ) {\displaystyle O(n)} 搜索 O ( log n ) {\displaystyle O(\log n)} [1] O ( log n ) {\displaystyle O(\log n)} 插入 O ( 1 ) {\displaystyle O(1)} O ( log n ) {\displaystyle O(\log n)} 删除 O ( 1 ) {\displaystyle O(1)} O ( log n ) {\displaystyle O(\log n)} Close
红黑树(英语:Red–black tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型用途是实现关联数组。它在1972年由鲁道夫·贝尔发明,被称为“对称二叉B树”,它现代的名字源于利奥尼达斯·J·吉巴斯和罗伯特·塞奇威克于1978年写的一篇论文。红黑树的结构复杂,但它的操作有着良好的最坏情况运行时间,并且在实践中高效:它可以在 O ( log n ) {\displaystyle {\text{O}}(\log n)} 时间内完成查找、插入和删除,这里的 n {\displaystyle n} 是树中元素的数目。 Quick Facts 红黑树, 类型 ...红黑树类型树发明时间1978年发明者利奥尼达斯·J·吉巴斯、罗伯特·塞奇威克用大O符号表示的时间复杂度算法 平均 最差空间 O ( n ) {\displaystyle O(n)} 搜索 O ( log n ) {\displaystyle O(\log n)} [1] O ( log n ) {\displaystyle O(\log n)} 插入 O ( 1 ) {\displaystyle O(1)} O ( log n ) {\displaystyle O(\log n)} 删除 O ( 1 ) {\displaystyle O(1)} O ( log n ) {\displaystyle O(\log n)} Close