镇平县两学一做网站,服装网站建设推荐,wordpress搭建本地博客,网站界面设计的流程1.Tree–Basic
参考链接
2.Binary Tree
参考链接 二叉树是有序树。
简单地理解#xff0c;满足以下两个条件的树就是二叉树#xff1a;
1. 本身是有序树#xff1b;
2. 树中包含的各个节点的度不能超过 2#xff0c;即只能是 0、1 或者 2#xff1b;2.1 满二叉树
如果…1.Tree–Basic
参考链接
2.Binary Tree
参考链接 二叉树是有序树。
简单地理解满足以下两个条件的树就是二叉树
1. 本身是有序树
2. 树中包含的各个节点的度不能超过 2即只能是 0、1 或者 22.1 满二叉树
如果二叉树中除了叶子结点每个结点的度都为 2则此二叉树称为满二叉树
2.2 完全二叉树
如果二叉树中除去最后一层节点为满二叉树且最后一层的结点依次从左到右分布则此二叉树被称为完全二叉树。
2.3 Binary Tree–Implementation
2.3.1 顺序存储结构
利用数组实现。
2.3.2 链式存储结构
利用链表实现。
2.4 Binary Tree–Traversal
遍历有两种实现方式 1.递归 2.利用栈模拟递归思想实现
2.4.1 Preorder Traversal
参考链接
2.4.1.1 概念 先序遍历得到的序列为1 2 4 5 3 6 72.4.1.2 实现–递归
c
void PreOrderTraverse(Tree * t)
{if(t NULL)return;printf(%c,t-data);PreOrderTraverse(t-lchild);PreOrderTraverse(t-rchild);
}2.4.1.3 实现–栈
2.4.2 Inorder Traversal
参考链接
2.4.2.1 概念 中序遍历得到的序列为4 2 5 1 6 3 72.4.2.2 实现–递归
void InOrderTraverse(Tree * t)
{if(t NULL)return;InOrderTraverse(t-lchild);printf(%c,t-data);InOrderTraverse(t-rchild);
}2.4.2.3 实现–栈
2.4.3 Postorder Traversal
参考链接
2.4.3.1 概念 后序遍历的结果为4 5 2 6 7 3 12.4.3.2 实现–递归
c
void PostOrderTraverse(Tree * t)
{if(t NULL)return;PostOrderTraverse(t-lchild);PostOrderTraverse(t-rchild);printf(%c,t-data);
}2.4.3.3 实现–栈
2.4.4 Hierarchical Traversal
2.4.4.1 概念 层次遍历结果为1 2 3 4 5 6 72.4.4.2 利用队列实现
参考链接
3. Binary Search Tree
3.1 概念
参考资料
又称 二叉排序树Binary Sort Tree。
二叉搜索树的基本性质满足二叉树性质的同时左子树根右子树 平均查找时间复杂度为 O(log(n))。
最好情况下的算法时间复杂度为O(1)最坏情况下的算法时间复杂度为O(n)。
BST 是数据结构中的一类。在一般情况下查询效率比链表结构要高。
针对优化查找效率衍生出众多 自平衡二叉查找树。 其中包括
··Size Balanced Tree节点大小平衡树Size Balanced Tree简称SBT。 2007
··高度平衡树简称 AVL树。 1962
··红黑树Red Black Tree。 1978以上所有自平衡二叉树 都会利用旋转 保持自身平衡。
3.2 实现
实现一般包括插入删除。
插入的算法有两种类似前序遍历的思想
1. 递归
2. 利用栈。参考资料
4. Size Balanced Tree
4.1 概念
参考资料 参考资料
Size Balanced TreeSBT是一种通过大小Size域来保持平衡的二叉搜索树它也因此得名。 相比红黑树、AVL树等自平衡二叉查找树SBT更易于实现。
Size的概念对于树上某个节点而言它的Size指的是以它为树根的子树当中节点的数量。
SBT的平衡条件对于SBT的每个节点每棵子树的 Size 大小不小于其兄弟的子树 Size 大小。性质 它总是满足
4.2 保证自平衡方法–旋转调整
旋转的命名参考资料 旋转分别为 左旋 (RR型) 和 右旋 (LL型)两者过程是相反的。 如下图示例针对 x 的左旋和右旋。 至于 LR型先左旋后右旋和 RL型先右后左不需要再写额外的代码只需要调用两次 左旋转或者右旋转。
假设A节点需要进行LR型的旋转则只需A.left 左旋转一次再A 右旋转一次。
假设B节点需要进行RL型的旋转则只需B.right 右旋转一次再B 左旋转一次。4.3 何时触发自平衡调整
只有在添加节点时才会出现平衡调整因为删除后调整平衡与不调整平衡都不影响后续的操作。 为了达到优化在delete中不进行平衡性的调整。而是把平衡性的调整放在了add方法里。
Maintain方法就是SBT树最核心的地方。
触发旋转的条件是
T1的size 二叔的size LL型
T2的size 二叔的size LR型
T3的size 大叔的size RL型
T4的size 大叔的size RR型旋转操作之后还需要递归调用Maintain方法。 递归调用的对象就是
哪个节点的子树被换了则需要调用这个Maintain新子树
举个例子原先A节点的右子树是T2旋转操作之后A节点的右子树变为了T3那么就需要递归调用MaintainT3。4.4 删除节点
为了达到优化在delete中不进行平衡性的调整。而是把平衡性的调整放在了add方法里。 特别需要注意的是 就是被删除节点的左右子树都不为null时需要找一个节点来替换当前被删除的节点。一般都是在被删除节点的右子树上查找最小最左的节点进行替换。这一点也是搜索二叉树的删除操作最容易出错的一个点值得重点关注。
4.5 实现
mygitee
5.Balanced Binary TreeBBT简称 AVL 树
参考链接
5.1 概念
AVL树本质上是一颗二叉查找树但是它又具有以下特点
1.它是一棵空树或它的左右两个子树的高度差的绝对值不超过1
2.左右两个子树 也都是一棵平衡二叉树。平衡因子Balance Factor简写为bf结点的 左子树的深度 减去 右子树的深度。 结点的平衡因子 左子树的高度 - 右子树的高度 在 AVL树中所有节点的平衡因子都必须满足 -1bf1;
5.2 保证自平衡方法–旋转调整
和上面 BST 性质差不多都分为左旋RR型和右旋LL型。 左旋和右旋都针对的是 哪个节点发现了不平衡就以哪个节点进行旋转。
5.2.1 LL插入–右旋 如上图此时添加为 LL 型T发现不平衡故需以 T 右旋调整
5.2.2 RR插入–左旋 如上图此时添加为 RR 型T发现不平衡故需以 T 左旋调整 5.2.3 LR插入–先左旋再右旋
LR 插入需要进行两次调整
5.2.4 RL插入–先右旋再左旋 5.2.5 总结
故由上可知根据插入节点的位置触发某种平衡调整
插入位置状态操作在结点 T 的左结点L的 左子树L 上做了插入元素左左型 (LL)右旋在结点 T 的左结点L的 右子树R上做了插入元素左右型 (LR)左右旋在结点 T 的右结点R的 右子树R 上做了插入元素右右型 (RR)左旋在结点 T 的右结点R的 左子树L 上做了插入元素右左型 (RL)右左旋
5.3 实现
5.3.1 分析–插入
插入最重要的是怎样更新 bf以及何时触发旋转。
插入是一个迭代的过程每次更新 bf 的值要从插入位置开始向上迭代。因为只有插入位置的 bf 值 是知道的其他节点的 bf 值在插入后都要变化。
插入分两种 1.向左子树插入temp 可能的情况有如下图 4 种
是否触发旋转要根据各个节点 a x z 的 bf 值来判断决定。
1 可能触发 x 的 右旋LL。
2 可能触发 双旋RLx 先右旋LLz 再左旋RL。
3 可能触发 双旋RLA 先右旋LLx 再左旋RL。
4 可能触发 双旋RLA 先右旋LLx 再左旋RL。2.向右子树插入temp 是否触发旋转要根据各个节点 a x z 的 bf 值来判断决定。
1 可能触发 z 的右旋LL。
2 可能触发 双旋LR先对 A 左旋RR再对 x 右旋LL。
3 可能触发 x 的左旋RR也可能触发 z 的左旋RR
4 可能触发 x 的左旋RR也可能触发 双旋RL先对 x 左旋RR再对 z 右旋LL。 总结
当插入节点在某颗树的 右子树 时只会发生 左旋RR 或 双旋RL。
当插入节点在某颗树的 左子树 时只会发生 右旋LL 或 双旋LR。故可以根据这个性质去写代码。5.3.2 实例–插入
以先序插入 70,90,50,40,60,55,45,48,49,75,57 实际插入流程如下 每次插入都要向上遍历遍历包含更新 bf 以及 根据 父节点 bf 的值调整子树平衡。
分析这里只举一个例子详细的拿着代码看。 示例1如上图 add 48 add 48后首先更新父节点45 bf -1上例中 原始父父节点40 bf -1故此次添加是RR型应左旋调整。延伸若 父父节点40 bf 0则 更新父父节点40 bf -1此时这颗子树满足平衡无需调整。若 父父节点40 bf 1则更新父父节点40 bf 0此时这颗子树满足平衡无需调整。5.3.3 分析–删除
删除最重要的删除后如何触发旋转调整。
前提无论 BST(二叉搜索树) SBT域二叉树 还是 BBT平衡二叉树删除节点都是拿 右子树最小节点右子树最左节点替换 被删除节点。同样可以理解为左子树 增加节点。和插入节点的思路一样。每次删除成功后根据 父节点 bf 的值 进行 判断 是否旋转调整子树。5.3.4 实例实现–插入、删除
实现最重要的一点就是要知道怎样更新 bf 的值以及何时进行旋转调整平衡。
实现代码实现分两种第一种是无论何时都获取树的高度第二种是无论何时每个节点都保存 bf 值。
第二种详细代码实现
6. Red Black TreeRBT
6.1 概念
1. 每个结点是红的或者黑的2. 根结点是黑的3. 每个叶子结点是黑的4. 如果一个结点是红的则它的两个儿子都是黑的5. 对每个结点从该结点到其子孙结点的所有路径上的包含相同数目的黑结点6.1 保持自平衡方法-旋转调整 6.2 实现
6.2.1 分析-插入 总结
为了更好的实现插入将默认生成的节点颜色设置为红色因此经分析得出只有当插入位置cur的父节点p为 红色时 才会出现 旋转及变色调整此时违背性质 4需要发生调整又会根据 叔父节点u的颜色而出现 调整 的区别。详见上图 情况 3.1.1 至 3.1.6当插入位置的父节点为 黑色时直接插入即可。实现代码时详见 6.3多看看上面的分析和总结。 6.2.2 分析-删除
7. B Tree/ B-Tree B Tree 就是 B-Tree“-” 是个连字符号不是减号。 B Tree 是在多叉树的基础上加上一些限制条件来的多叉的好处非常明显有效的降低了 B-树的高度。
7.1 B Tree 性质 一颗 M 阶 M阶指多叉树有多少个叉B 树 T满足以下条件 每个节点至多拥有 M 棵子树根节点至少拥有两颗子树除了根节点以外其余每个分支节点至少拥有 M/2 棵子树所有叶节点都在同一层上这个概念就能看出 B tree 相比 平衡类二叉树 降层高有 k 棵子树的分支节点则存在 k-1 个关键字关键字按照递增顺序进行排序关键字数量满足 ceil(M/2) - 1 n M-1 B Tree 每个节点都包含 索引值 Key 和 对应数据 Data区别于 B 树。 - 因为每个节点包含 键值故在该树全集内做一次查找,性能逼近二分查找
7.2 B Tree 和 磁盘关系 B Tree 的作用 - 树是专门为外部存储器设计的如磁盘它对于读取和写入大块数据有良好的性能所以一般被用在文件系统及数据库中。 为什么会出现 B-树 这类数据结构 传统用来搜索的平衡二叉树有很多如 AVL 树红黑树等。这些树在一般情况下查询性能非常好但当数据非常大的时候它们就无能为力了。 原因当数据量非常大时内存不够用大部分数据只能存放在磁盘上只有需要的数据才加载到内存中。一般而言内存访问的时间约为 50 ns而磁盘在 10 ms 左右。速度相差了近 5 个数量级磁盘读取时间远远超过了数据在内存中比较的时间。这说明程序大部分时间会阻塞在磁盘 IO 上。 那么我们如何提高程序性能减少磁盘 IO 次数像 AVL 树红黑树这类平衡二叉树从设计上无法“迎合”磁盘。 从“迎合”磁盘的角度来看看B-树的设计 索引的效率依赖与磁盘 IO 的次数快速索引需要有效的减少磁盘 IO 次数如何快速索引呢 - 索引的原理其实是不断的缩小查找范围就如我们平时用字典查单词一样先找首字母缩小范围再第二个字母等等。平衡二叉树是每次将范围分割为两个区间。 - 为了更快B-树 每次将范围分割为多个区间区间越多定位数据越快越精确。那么如果节点为区间范围每个节点就较大了。 - 所以新建节点时直接申请页大小的空间磁盘存储单位是按 block 分的一般为 512 Byte。 磁盘 IO 一次读取若干个 block我们称为一页具体大小和操作系统有关一般为 4 k8 k或 16 k计算机内存分配是按页对齐的这样就实现了一个节点只需要一次 IO。 B-Tree 的查找 一般而言根节点都在内存中B-Tree 以每个节点为一次磁盘 IO. 比如下图中若搜索 key 为 25 节点的 data首先在根节点进行二分查找因为 keys 有序二分最快判断 key 25 小于 key 50所以定位到最左侧的节点此时进行一次磁盘 IO将该节点从磁盘读入内存接着继续进行上述过程直到找到该 key 为止。
7.2 B Tree 的实现 添加 添加的时候只有分裂添加情况两种 普通插入即插入的节点不满插入后要裂变即 插入后大于 M 。 特别注意裂变发生时机发生在下一次插入 大于 M 时而不是 插入后 等于 M 时。 删除 删除的时候只有合并删除情况四种 删除key不是叶子结点且 key值 前面节点大于 degree - 1后面节点大于 degree - 1前面节点等于 degree - 1 后面节点等于 degree - 1 删除key在叶子结点 直接把 key 值删除。
8. B Tree
B tree 是 B tree 的一种变形。
文件系统及数据库系统普遍采用 B-/Tree 作为索引结构.
8.1 性质
一棵 M 阶 B 树如下图必须满足如下条件 每个结点最多有 M 棵子树如果根不是终端结点则根结点至少有 1 个关键字即至少有 2 棵子树。根的关键字取值范围是[1m-1]每个关键字对应一棵子树与 B Tree 的不同具有 k 个子树的非叶结点包含 k 个键。每个非叶子结点除了根具有至少 m/2 子树即最少有 m/2 个关键字。特别注意终端结点包含全部关键字及相应记录的指针叶结点中将关键字按大小顺序排序并且相邻叶结点按大小顺序相互链接起来。所有分支结点可以视为索引的索引中金包含他的各个子节点即下一级的索引块中关键字最大值及指向其子结点的指针。 特别注意 B Tree 中所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data)相当于叶子节点的索引叶子节点携带真正的 data。 因此一般 B Tree 的叶节点和内节点大小不同而 B-Tree 的每个节点大小一般是相同的为一页。B Tree 中 叶子结点有一个链指针上面性质 5B Tree 做索引优点 因为 B Tree 叶子结点有链指针可大大增加区间访问性可使用在范围查询等而 B-Tree 每个节点 key 和 data 在一起则无法区间查找。 根据空间局部性原理如果一个存储器的某个位置被访问那么将它附近的位置也会被访问。 B Tree 可以很好的利用局部性原理, 可以利用磁盘预读原理提前将这些数据读入内存减少了磁盘 IO 的次数。 B Tree 更适合外部存储。由于内节点无 data 域每个节点能索引的范围更大更精确。 原因 前面说过磁盘是分 block 的一次磁盘 IO 会读取若干个 block具体和操作系统有关那么由于磁盘 IO 数据大小是固定的在一次 IO 中单个元素越小量就越大。这就意味着 BTree 单次磁盘 IO 的信息量大于 B-Tree从这点来看 BTree 相对 B-Tree 磁盘 IO 次数少。
