红黑树是一种特定类型的二叉树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是在1972年由RudolfBayer发明的,他称之为"对称二叉B树",它现代的名字是在LeoJ.Guibas和RobertSedgewick于1978年写的一篇论文中获得的。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的,它可以在O(logn)时间内做查找,插入和删除,这里的n是树中元素的数目。
中文名:红黑树
性质:自平衡二叉查找树
用途:实现关联数组
学科:计算机学
别名:对称二叉B树、二叉树
发明人:鲁道夫·贝尔
发明时间:1972年
属性:计算机科学中用到的数据结构
红黑树数据结构
红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的,他称之为\"对称二叉B树\",它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(log )时间内做查找,插入和删除,这里的是树中元素的数目。
它的统计性能要好于平衡二叉树(有些书籍根据作者姓名,Adelson-Velskii和Landis,将其称为AVL-树),因此,红黑树在很多地方都有应用。在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,这些修改提供了更好的性能,以及对set操作的支持)。其他平衡树还有:AVL,SBT,伸展树,TREAP 等等。