百度站长平台网页版,新媒体营销工具有哪些,wordpress小工具开发,免费1级做爰片打网站目录
一.引言
二.高级树的简介
1.树
2.二叉树
3.二叉搜索树
4.平衡二叉树
三.AVL 树
◆ 插入节点
◆ 左旋
◆ 右旋
◆ 左右旋
◆ 右左旋
◆ 一般形式
◆ 实际操作
◆ 总结
四.红黑树
◆ 概念
◆ 示例
◆ 对比
五.总结 一.引言
前面我们介绍了二叉树、二叉…
目录
一.引言
二.高级树的简介
1.树
2.二叉树
3.二叉搜索树
4.平衡二叉树
三.AVL 树
◆ 插入节点
◆ 左旋
◆ 右旋
◆ 左右旋
◆ 右左旋
◆ 一般形式
◆ 实际操作
◆ 总结
四.红黑树
◆ 概念
◆ 示例
◆ 对比
五.总结 一.引言
前面我们介绍了二叉树、二叉搜索树、多叉树等基础的树形结构本文扩展一些新的树类型例如 AVL 树、红黑树、B 树等等完善一下整个框架内树的的概念。 二.高级树的简介
1.树 树这里就不多重复了包括根节点、左右子节点分为多个层级的扩散的结构因为其树形的结构天然的适合使用递归的方法进行遍历与处理。 2.二叉树 只有左右分叉的树即为二叉树 二叉树主要掌握其三种遍历方式。 - 前序 Pre-order 根-左-右 - 中序 In-Order 左-根-右 - 后序 Post-Order 左-右-根 3.二叉搜索树 通过对数据进行有序编排二叉搜索树将 o(n) 的搜索复杂度缩减为 o(log2n)其特点: 左子树所有节点小于根节点 右子树所有节点大于根节点 需要注意二叉搜索树的中序遍历是升序排列。
◆ 节点查找 只需要与根节点比较即可小于根节点到左子树大于2根节点到右子树。 可以看到其查询的时间复杂度就是树的深度即 Level。 ◆ 极端情况 当我们构建二叉搜索树时不注意树的结构或者平衡时其容易出现如上图所示的极端情况此时二叉树退化为链表其搜索复杂度也恢复至 o(n)。 4.平衡二叉树 上面这种情况最简单的平衡方法就是从中间把棍子打断然后对于左右的棍子依次打断直到平衡但是实际情况下我们不会等树发展到这种棍子的状态才进行调整我们一般在每一步插入元素的时候都会查看当前树是否平衡并对其进行平衡化的操作。下面我们就了解几种常见的平衡二叉树。 三.AVL 树 AVL 树命名来源于其发明者其在树中引入了平衡因子即 Balance Factor该因子的计算为 左子树高度 - 右子树高度 或者 右子树高度 - 左子树高度因此其值的范围控制在 -1、0、1。这里是高度而不是节点数的原因是二叉树的搜索时间复杂度与其深度即 Level 有关而不是节点个数 (考虑棍子的极端情况)。当检测到数非平衡时其会通过四种旋转操作使树达到平衡。 以上面的二叉树为例每一个节点的平衡因子都基于其左右子树的深度差计算以 J 为例右子树深度即 Level 为 4而左子树的深度为 3从而其值 4 - 3 1。 而所有叶子节点左右子树都为 0所以其值为 0。上面这个树的平衡因子范围在 [-1, 1]因而其是一颗严格意义上平衡的AVL 树因此保持一个树的平衡因子在 [-1,1] 范围内其就是一颗平衡二叉搜索树。
◆ 插入节点 14 增加后平衡因子在 [-1,1] 范围内因此无需调整。 3 增加后根节点与第一个左节点的平衡因子变为 -2此时平衡树被打破需要使用旋转操作进行 reblance共有四种旋转方式: ◆ 左旋 右右子树的情况需要进行一次左旋调整为 AVL树。 A B C所以 A B C 有效。 ◆ 右旋 左左子树的情况下依次右旋调整为 AVL 树。 A B C所以 C B A 有效。 ◆ 左右旋 左右子树即先一个单独左再一个单独右此时满足 A B C B A C结合在一起就是 A C B所以可以先左旋 BC 并调换位置调整为 A C B 的左左子树再右旋得到 B C A。 ◆ 右左旋 B AB CC A B C A所以可以切换为右右子树 A C B再一次左旋即可。 ◆ 一般形式 上面介绍了单节点的四种旋转方式实际场景带子树的情况比较多上面是几种通用的旋转方法。 我们再从头捋一遍 AVL 树首先树的查询是基于其深度 Level 来的所以通过引入平衡因子就能够获得高度差从而衡量一个树是否平衡当超过1不平衡时我们可以通过旋转进行 rebalance此时从单节点推广至多节点AVL 树的情况大致就这样。 ◆ 实际操作
下面基于真实的二叉搜索树进行旋转操作。
- 左左子树 红框所在部分为左左子树根据一般形式我们需要把 Pivot 5 提上去再把 10 放下来同时 Pivot 的 Right 挂到 root 10 的 Left就得到下面的结果没理解的同学看一般形式再对应一下: - 右左子树 红框部分为右左子树参考上面一般方法 进行右左旋先将 15 换到 16再把 16 改为 15.right最后把 15 拿上去9 改为 15.left 即可。 ◆ 总结 AVL 树在满足平衡二叉搜索的情况下每个 Node 都多余存储了一个平衡节点因此其会有额外的存储负担其次对于节点的增删很容易使其成为非平衡的状态从而频繁引发调整。 四.红黑树
◆ 概念
上面的 AVL 树通过平衡因子维持整个搜索树的平衡但是由于其因子范围太小 [-1,1] 导致这里调整的频率太高从而影响了查询的效率所以为了折中就推出了一些近似平衡二叉树红黑树就是其中的代表。其允许左右子树之间的高度差在两倍以内放宽了范围从而较少了调整的次数。 ◆ 示例 上面提到五条性质前三条比较 common主要看后两条:
- 不能有相临接的两个红色节点
- 任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
Most Important:
从根到叶子的最长的可能路径不多于最短路径的两倍长。 ◆ 对比 - AVL 树相比红黑树提供更快的查询效率因为其更严格的平衡
- 红黑树提供了更快的插入和移除效率因为 AVL 涉及到过多的旋转调整
- AVL 存储更多因为其需要 int 存储节点平衡度而红黑树只需要 bit 存储红或蓝即 0 或 1
- 读多写少适合使用 AVL 树而工程中二者兼顾所以红黑树的使用更加普遍例如 map/multimap 五.总结
截止到目前一些基础的搜索结构与算法我们也了解差不多了从最基本的树形结构到并查集、Trie 树、二叉树、完全二叉树、平衡树等等。由于 AVL 树和红黑树的实现相对复杂所以我们主要掌握其思想以及对应的几种旋转操作即可做到能够看懂说清。
