【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%左右。
AVL tree
AVL tree是一个“加上了额外平衡条件”的二叉搜索树。其平衡条件的建立是为了确保整棵树的深度为O(logN)。AVL tree要求任何节点的左右子树高度相差最多为1。
如图AVL tree，插入了节点11之后，灰色节点违反了AVL tree的平衡条件。由于只有“插入点至根节点”路径上的各节点可能改变平衡状态，因此，只要调整其中最深的那个节点，便可使整棵树重新获得平衡。
前面说过，只要调整“插入节点至根节点”路径上，平衡状态被破坏之各节点种最深的那一个，便可使得整棵树重新获得平衡。假设该最深节点X，由于节点最多拥有两个子节点，二所谓“平衡被破坏”意味着X的左右两棵子树的高度相差2，因此可以分为一些四种情况：
插入点位于X的左子节点的左子树——左左。
插入点位于X的左子节点的右子树——左右。
插入点位于X的右子节点的左子树——右左。
插入点位于X的右子节点的右子树——右右。
情况1，4彼此对称，称为外侧插入，可以采用单选转操作调整解决。情况2，3彼此对此对此，称为内存插入，可采用双旋转调整解决。