【STL源码剖析】第五章关联式容器之树的导览

本文主要是介绍【STL源码剖析】第五章关联式容器之树的导览，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第五章关联式容器

标准的STL关联式容器分为set（集合）和map（映射表）两大类，以及这两大类的衍生体multiset（多建集合）和multimap（多键映射表）。这些容器的底层实现极值均以RB-tree（红黑树）完成。RB-tree也是一个独立容器，但并不开放给外界使用。

此外，SGI STL还提供了一个不在标准规格之列的关联式容器：hash table（散列表），以及以此hash table为底层实现机制而完成的hash_set（散列集合）、hash_map（散列映射表）、hash_multiset（散列多键集合）、hash_multimap（散列多键映射表）。

关联式容器（associative containers）

所谓关联式容器，观念上类似关联式数据库（实际上则简单许多）：每笔数据（每个元素）都有一个键值（key）和一个实值（value）。当元素被插入关联式容器中时，容器内部结构（可能是RB-tree，也可能是hash-table）便依照其键值大小，以某种特定规则将这个元素置于适当位置。关联式容器没有所谓的头尾（只有最大元素和最小元素），所以不会有所谓的push_back()、push_front()、pop_back()、pop_front()、begin()、end()这样的操作行为。

树的导览

树由节点（nodes）和边（edges）构成。整棵树有一个最上端节点，称为根节点（root）。每个节点可以拥有具有方向性的边（directed edges），用来和其他节点相连。相连节点之中，在上者称为父节点（parent），在下者称为子节点（child）。无子节点者称为叶节点（leaf）。子节点可以存在多个，如果最多只允许两个子节点，即所谓二叉树（binary tree）。不同的节点如果拥有相同的父节点，则彼此互为兄弟节点（siblings）。根节点至任何节点直接有唯一路径（path），路径所经过的边数，称为路径长度（length）。根节点至任一节点的路径长度，即所谓该节点的深度（depth）。根节点的深度永远是0。某节点至其最深子节点（叶节点）的路径长度，称为该节点的高度（height）。整棵树的高度，便以根节点的高度来代表。任何节点的大小（size）是指其所有子代（包括自己）的节点总数。

二叉搜索树

所谓二叉树，其意义是："任何节点最多只允许两个子节点"，即左右子节点。递归方式定义：”一个二叉树如果不为空，便是一个根节点和左右两子树构成；左右子树都可能为空“。二叉树应用广泛，例子：编译器表达式树、哈夫曼编码树。

所谓二叉搜索树，可提供对数实际的元素插入和访问 。二叉搜索树的节点放置规则是：任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中的每一个节点的键值。因此，从根节点一直往左走，直至无路可走，即得最小元素；从根节点一直往右走，直至无右路可走，即得最大元素。

二叉搜索树插入新元素时，可以从根节点开始，遇键值较大者就向左，遇键值较小者就向右，一直到尾端，即为插入点。

二叉搜索树移除操作。欲删除就节点A，情况可分两种。如果A只有一个子节点，我们就直接将A的子节点连至A的父节点，并将A删除。如果A有两个子节点，我们就以右子树内的最小节点取代A。注意，右子书的最小节点极易获得。

平衡二叉搜索树

所谓树形平衡与否，并没有一个绝对的测量标准。“平衡”的大致意义是：没有任何一个节点过深。不同的平衡条件，造就不同的效率表现，以及不同的实现复杂度。有数种特殊结构如AVL-tree、RB-tree、AA-tree，均可实现平衡二叉搜索树，它们比一般二叉搜索树复杂，因此，插入节点和删除节点的平均时间也比较长，但是它们可以避免极难应付的最坏情况，况且由于它们总数保持某种程度的平衡，所以元素的访问时间平均而言也就比较少，一般而言其搜素时间可节省25%左右。