科技之家

科技之家,汇聚专业声音 解析IT潮流

滚动 >

首页 > 滚动 >

红黑树介绍(红黑树数据结构)

来源: 时间:2023-07-05 11:42:41

  红黑树是一种特定类型的二叉树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是在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 等等。

相关文章