本文涉及到 SGI STL 源码的文件主要是 stl_tree.h 这个文件。
0. 关联式容器
之前几篇文章详细介绍了SGI STL中序列式容器的实现,并提到过STL中还有一类关联式的容器。标准的STL管理师容器分为 set(集合)和map(映射表)两大类,以及这两大类的衍生体multiset(多键集合)和multimap(多键映射表),这些容器的底层机制均以RB-Tree(红黑树)完成。RB-Tree是一种非常高效的数据结构,它本质上是一种平衡的二叉搜索树,因而其查找的平均时间复杂度为元素总个数的对数(即logN)。在STL中RB-Tree是一个独立的容器,但并没有对用户的公开接口,仅提供给STL的set和map使用。
SGI STL在标准STL之外,还提供了一类关联式容器——hash table(哈希表),以及以此为低层机制的hash set(散列集合)、hash map(散列映射表)、hash multiset(散列多键集合)和hash multimap(散列多键映射表)。相比于RB-Tree,hash table的时间效率更高,插入、删除、查找的时间复杂度均为常数时间,但需要比元素总个数多得多的空间。
本文接下来主要介绍树及RB-Tree相关的内容,后续文章将具体介绍SGI STL中set、map、hash table的实现。
1. 树与二叉搜索树
树是一种非常常见而且实用的数据结构,几乎所有的操作系统都将文件存放在树状结构里,几乎所有编译器需要实现一个表达式树(expression tree),文件压缩所用的哈夫曼算法也需要用到树状结构,数据库所使用的B-tree则是一种相当复杂的树状结构。
关于树的一些基本概念相信大家都比较熟悉,这里就不赘述了,如果需要可以google或看wikipedia,这里重点重温一下数据结构里的二叉搜索树、平衡二叉搜索树、AVL树。
二叉搜索树:任何节点的键值大于其左子树中每一个节点的键值,并小于其右子树中的每一个节点的键值。根据二叉搜索树的定义可知,按照中序遍历该树可以得到一个有序的序列。平均情况下,二叉搜索树可以提供对数时间的插入和访问。其插入和查找的算法也很简单,每次与根节点的键值进行比较,小于根节点的键值则往根节点的左子树插入或查找,大于则往右子树插入或查找,无论是递归实现还是非递归实现都很简单。
平衡二叉搜索树:上面提到二叉搜索数的平均性能为对数时间,这是因为二叉搜索树的深度与数据插入的顺序有关,如果插入的数据本身就比较有序,那么就会产生一个深度过大的树,甚至会退化为一个链表的结构,这中情况下,其查找的效率就是线性时间了。平衡二叉搜索树就是为了解决这个问题而产生的,“平衡”的意义是,没有任何一个节点过深。不同的平衡条件造就出不同的效率表现,以及不同的实现复杂度,如 AVL-Tree、RB-Tree、AA-Tree _等。他们都比简单的二叉搜索树要复杂,特别是插入和删除操作,但他们可以避免高度不平衡的情况,因而查找时间较快。
