红黑树 编辑
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型用途是实现关联数组。它在1972年由鲁道夫·贝尔发明，被称为"对称二叉B树"，它现代的名字源于Leo J. Guibas和罗伯特·塞奇威克于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况算法分析，并且在实践中高效：它可以在




O




{\displaystyle {\text{O}}}

时间内完成查找、插入和删除，这里的



n


{\displaystyle n}

是树中元素的数目。
1
相关
鲁道夫·拜尔，自1972年以来一直是慕尼黑工业大学信息技术系的名誉教授。他因发明数据结构而出名: B-树和UB-树以及 红黑树。
鲁道夫·拜尔，自1972年以来一直是慕尼黑工业大学信息技术系的名誉教授。他因发明数据结构而出名: B-树和UB-树以及 红黑树。
完全公平排程器，Linux内核的一部分，负责行程排程。参考了康恩·科里瓦斯提出的排程器源代码后，由匈牙利程式员英格·蒙内所提出。在Linux kernel 2.6.23之后采用，取代先前的O(1)排程器，成为系统预设的排程器。它负责将CPU资源，分配给正在执行中的行程，目标在于最大化程式互动效能与整体CPU的使用率。使用红黑树来实作，算法效率为大O符号。
鲁道夫·拜尔，自1972年以来一直是慕尼黑工业大学信息技术系的名誉教授。他因发明数据结构而出名: B-树和UB-树以及 红黑树。
左倾红黑树是一种类型的自平衡二元搜寻树。它是红黑树的变体，并保证对操作相同渐近的复杂性，但被设计成更容易实现。
完全公平排程器，Linux内核的一部分，负责行程排程。参考了康恩·科里瓦斯提出的排程器源代码后，由匈牙利程式员英格·蒙内所提出。在Linux kernel 2.6.23之后采用，取代先前的O(1)排程器，成为系统预设的排程器。它负责将CPU资源，分配给正在执行中的行程，目标在于最大化程式互动效能与整体CPU的使用率。使用红黑树来实作，算法效率为大O符号。