都有什么类别的网站,腾讯企业邮箱怎么申请,wordpress检查全站链接,萌导航在前文中介绍了STL的序列式容器#xff1b;
STL序列式容器之vector-CSDN博客
STL序列式容器之list-CSDN博客
STL序列式容器之deque-CSDN博客
STL序列式容器之stack-CSDN博客
STL序列式容器之queue-CSDN博客
STL序列式容器之heap#xff08;堆#xff09;-CSDN博客
ST…在前文中介绍了STL的序列式容器
STL序列式容器之vector-CSDN博客
STL序列式容器之list-CSDN博客
STL序列式容器之deque-CSDN博客
STL序列式容器之stack-CSDN博客
STL序列式容器之queue-CSDN博客
STL序列式容器之heap堆-CSDN博客
STL序列式容器之priority_queue-CSDN博客
STL序列式容器之slist-CSDN博客
接下来对关联式容器associative containers进行学习及分享 根据“数据在容器中的排列”特性容器可概分为序列式Sequence和关联式associative两种。 标准的STL关联式容器分为set(集合)和map映射表两大类以及两大类的衍生体multiset(多键集合和multimap(多键映射表)。这些容器底层机制均以RB-tree红黑树完成。RB-tree也是独立容器但并不开放给外界使用。 此外SGI STL还提供了一个不在标准规格之类的关联式容器hash table散列表以及以此hash table为底层机制完成的hash_set(散列集合)、hash_map散列映射表、hash_mulitset(散列多键集合)、hash_mulitmap散列多键映射表。 关联式容器观念上类似关联式数据库每条数据每个元素都有一个键值(key)和实值value。当元素被插入到关联式容器中时容器内部结构便依据其键值大小以某种特定规则将这个元素放置于适当位置。关联式容器没有所谓头尾、所以不会有push_back,push_front,pop_back,pop_front这样的操作行为。 begin()、end()可以在遍历时使用 一般而言关联式容器的内部结构是一个balanced binary tree (平衡二叉树)以便获得良好的搜索效率。balanced binary tree有许多种类型包括AVL-treeRB-treeAA-tree其中最被广泛运用于STL的是RB-tree(红黑树)。为了探讨STL的关联式容器我们必须先探讨RB-tree。 进入RB-tree主题之前让我们先对tree的来龙去脉有个概念。以下讨论都和最终目标RB-tree有密切关联。 树因为耳熟能详此处就不做过多的解释了
二叉搜索树binary search tree 所谓二叉树其意义是“任何节点最多只允许两个子节点”。这两个子节点称为左子结点和右子节点。如果以递归方式来定义二叉树我们可以说“如果一个二叉树不为空便是由一个根节点和左右两子树构成左右子树都有可能为空”。二叉树的应用极广 所谓二叉搜索数binary search tree,可提供对数时间logarithmic time的元素插入和访问。二叉搜索树的节点放置规则是任何节点的键值一定大于其左子树中的每一个节点的键值并小于其右子树中的每一个节点的键值。因此从根节点一直往左走直到无左路可走即得最小元素从根节点一直往右走直至无右路可走即得最大元素。下图即为一颗二叉搜索树 现在简要介绍二叉搜索树的插入节点及删除节点
对于插入节点首先进行查找将插入值与当前节点key进行比较如果比当前节点大就进入左子树如果比当前节点大进入右子树如果和当前节点key相等则退出找到了key值相同的节点说明节点已经存在则不进行插入操作直到叶子节点后将节点插入比如插入节点11则其查找路径沿着淡蓝色箭头往下如下所示 沿着10-20-14的路径向下发现14为叶子节点然后将11加入到其左子树。 对于删除操作分为三种情况1删除节点为叶子节点2删除节点只有一个子节点3删除节点由两个子节点。
对于情况1直接将节点移除出即可比如删除节点为9则删除节点后状态为 为了演示方便在8和9之间新增了一个虚线箭头事实上8的右节点置为了空此时9节点将会被删除。最终节点状态为 对于情况2比如删除节点8此时8正好有一个子节点将8的子节点替换掉待删除的节点即可完成删除操作如下图所示 节点6将替换节点8
最后树将变成 再来看情况3比如删除节点key为20此时节点20存在两个节点首先找到20右子树的最小节点21而后将21替换到20过程如下 第一步定位到节点20发现节点20存在两个子节点然后查找右子树的最小节点并将最小节21点替换当前节点20如下所示 最终二叉搜索树转换为 参考文档《STL源码剖析--侯捷》
