哪些网站图片做海报好,简单手机网站开发软件有哪些,用微信微博网站来做睡眠经济,广西百度推广1.容器 容器用于容纳元素集合#xff0c;并对元素集合进行管理和维护#xff0e; 传统意义上的管理和维护就是#xff1a;增#xff0c;删#xff0c;改#xff0c;查#xff0e; 我们分析每种类型容器时#xff0c;主要分析其增#xff0c;删#xff0c;改#xff…1.容器 容器用于容纳元素集合并对元素集合进行管理和维护 传统意义上的管理和维护就是增删改查 我们分析每种类型容器时主要分析其增删改查动作实现及复杂度
2.红黑树 2.1.结构 2.1.1.图解 红黑树是容器类型 其元素组织采用二叉树结构 上图是一个包含五个元素的二叉树 二叉树容器内元素间具备兄弟父子关系这种关系通过每个节点内三个指针来维护它们是 (1). 指向节点父节点指针 (2). 指向节点左孩子节点指针 (3). 指向节点右孩子节点指针
为了发挥出这类容器的优势红黑树在二叉树基础上增加了多个一致性约束这些一致性约束可分为两种类型 一种类型为了元素有序一种类型为了树中任意节点左子树右子树的高度平衡 (1). 服务于元素有序的一致性约束 对树中任意节点p 若p的左孩子节点lp存在则以lp为根子树中所有节点内元素均小于p节点内元素 若p的右孩子节点rp存在则rp为根子树中所有节点内元素均大于p节点内元素
通过这个一致性约束我们保证了二叉树的有序性但这个性质给我们带来的好处是什么呢 通过该性质在二叉树中查找元素时候我们可以运用二分查找加快查找速度 上述二叉树满足有序的约束我们若在其中查找值为5的元素 二分查找过程如下 (1). 初始查找节点为根节点 (2). 判断当前节点p和5关系 a. p中元素小于5由于有序性质只能将当前节点p设置为p的右孩子继续查找 b. p中元素大于5由于有序性质只能将当前节点p设置为p的左孩子继续查找 c. p中元素等于5则找到停止迭代 d. p为空指针查找结束树中不存在匹配节点
(2). 服务于树中任意节点左子树右子树高度平衡的一致性约束 a. 任意节点需要携带颜色标记颜色标记要么为红色要么为黑色 b. 树的根节点的颜色标记必须为黑色 c. 对树中任意节点p若p的父节点pp存在且颜色标记为红色则p的颜色标记必须为黑色 d. 对树中任意节点pp的左子树的黑高和p的右子树的黑高必须一致 上图是一个包含五个元素的红黑树 首先这棵树是一颗二叉树 然后这棵树满足有序的一致性约束 最后这棵树满足关于高度平衡的一致性约束 如何确定树的黑高 由于红黑树一致性约束规定了树中任意节点的左子树右子树黑高一致 为了得到树的黑高我们只需确定一条从根节点到叶子节点的路径然后统计此路径上颜色标记为黑色的节点个数即可
通过平衡性的一致性约束可以带给我们什么好处呢 给定一个红黑树 a. 其根节点为pp的左孩子为lpp的右孩子为rp b. 容器内元素总数为n c. 树的黑高为h 对一个黑高为h的树来说极端情况下该树内所有节点颜色标记均为黑色下该树中的节点数量最少 由于任意节点左右子树黑高一致的约束此时树中节点全黑的树只能是一颗满二叉树 满二叉树下给定高度h可以计算树中节点总数 2 0 2^{0} 20 2 1 2^{1} 21 … 2 h − 1 2^{h-1} 2h−1 2 h 2^{h} 2h-1
这样存在h和n之间存在下面的关系 2 h 2^{h} 2h-1 n 可以简化为h log以2为底n1的对数
又因为父节点颜色标记为红色子节点颜色标记必须为黑色的约束 所以给定一颗黑高为h的红黑树从根节点到叶子节点理论上最长的一条路径只能是路径上交替出现黑色红色这样的情况此情况下理论上根节点到叶子节点最长路径的高度为2h
这样当我们满足平衡约束时我们获得的好处是 可以确定根节点到叶子节点最长的一条路径高度小于等于2*log以2为底n1的对数
2.1.2.存在一致性约束容器特点 (1). 插入无需提供位置信息 (2). 不支持直接原地修改一般分解为移除添加两个过程 (3). 由于元素值决定其位置这类容器一般插入元素时一般以std::pairkey, value形式插入即元素包含键值两部分键用来实现一致性约束值是此键关联的实际内容
