存档

文章标签 ‘红黑树’

STL笔记之二叉查找树

2014年9月7日 没有评论

SGI STL的关联容器(map、set、multimap、multiset)底层都是基于红黑树(Red Black Tree,RBT)来实现的,红黑树是一种被广泛使用的二叉查找树(Binary Search Tree,BST),有比较良好的操作效率。
1. 二叉查找树
二叉查找树可提供对数时间的元素插入和访问,其遵循以下规则:任何节点的键值一定大于其左子树中每一个节点的键值,并小于其右子树中每一个节点的键值。不过在极端情况下,当所有节点位于一条链上时,二叉查找树的操作时间为O(N)。二叉查找树[……]

继续阅读