树
<h4>硬盘读取原理</h4>
<p>分为三步走：寻道，旋转，传送</p>
<p>主存和磁盘以页为单位交换数据</p>
<p>页预读</p>
<p>减少树深度</p>
<p><br></p>
<h4>二叉查找树</h4>
<ul>
<li>若其左子树存在，则其左子树中每个节点的值都不大于该节点值；</li>
<li>若其右子树存在，则其右子树中每个节点的值都不小于该节点值。</li>
</ul>
<p>说的简单就是遇到比自己小的就插到左边，遇到比自己大的就插右边</p>
<p><img src="https://www.showdoc.cc/server/api/common/visitfile/sign/050b7087ffbc71081fc0b4b6d4599e43?showdoc=.jpg" alt="" /></p>
<p>但是，普通二叉查找树，最极端的情况下，只有 左子树 或者 右子树，退化成链表，就会失去快速查找的优点 （log(n) => O(n)）</p>
<p><img src="https://www.showdoc.cc/server/api/common/visitfile/sign/db6210674f04f4a45009f7e1ee2f991c?showdoc=.jpg" alt="" /></p>
<p><br></p>
<h4>平衡查找树</h4>
<p>要解决上面这个问题，就是每次插入或者删除的时候，设计一些套路去修正，让左右子树相差的深度尽可能小，来保证其搜索效率。所以就诞生了各种平衡树。</p>
<p>套路基本就是，通过设计各种左旋右旋，或者树的节点存取不止一个值，然后穷举可能出现的情况，每种情况对应每种操作，以此来让树在插入和删除的时候尽肯能保存平衡。</p>
<p>有的最求极致平衡，比如 avl</p>
<p>有的追求相对平衡，比如红黑树</p>
<p>有的多搞几个节点，比如 2-3 树</p>
<p><br></p>
<h4>2-3树</h4>
<p>理解 2-3树 应该是理解其他同类平衡查找树的起点。（这些树都是穷举各种情况来做各种转换）</p>
<p>普通树基本一个节点只会存一个数值，以及指向左右子节点。</p>
<p>2-3树的定义是，</p>
<p> 对于2节点，其实就是普通的 BST 节点一样：</p>
<p>有一个数据域和两个子节点指针，当前节点的数据的值要大于左子树中所有节点的数据，要小于右子树中所有节点的数据。</p>
<p> 对于3节点，有点特殊，但是也是遵从大小关系：</p>
<p>有两个数据域 a 和 b ，以及三个子节点指针。左子树中所有的节点数据要小于a，中子树中所有节点数据要大于 a 而小于b ，右子树中所有节点数据要大于 b。</p>
<p>2-3 树也可能会失去平衡，在插入和删除节点时需要动态维持平衡的，但维持平衡的策略和AVL树是不一样的。AVL树是通过旋转来恢复平衡的，而2-3树是通过节点分裂来维持的。</p>
<p>下面通过穷举情况来介绍：</p>
<p>情况1：插入k, 发现要查的地方是一个2-node节点，最简单，直接 2 变 3</p>
<p><img src="https://www.showdoc.cc/server/api/common/visitfile/sign/b347f264ded7bc977e77b85c6867fbde?showdoc=.jpg" alt="" /></p>
<p>情况2：插入s, 发现只有一个 3-node, 直接按区间分裂</p>
<p><img src="https://www.showdoc.cc/server/api/common/visitfile/sign/4586a28ec52234e53a3b2c0eee54bc64?showdoc=.jpg" alt="" /></p>
<p>情况3：插入z, 发现要查的节点是3-node，但是它的父节点是2-node</p>
<p>可以看出很像上一种情况，先成为一个临时的 4 - node，然后把中间值 x 往父基节点提升，以此来达到平衡。</p>
<p><img src="https://www.showdoc.cc/server/api/common/visitfile/sign/66b7f1292349f4af2f9121ae1e555f8e?showdoc=.jpg" alt="" /></p>
<p>情况 4： 要插入的节点是3-node，父节点也是3-node，但是继续向上走，存在 2-node 的节点</p>
<p>其实就是持续将中间元素提升至其父节点，直至遇到一个父节点是2-node节点，然后将其变为3-node，不需要继续进行拆分。</p>
<p><img src="https://www.showdoc.cc/server/api/common/visitfile/sign/28de3b2a14f1359d17b63335f4faca52?showdoc=.jpg" alt="" /></p>
<p>情况 5：最复杂，就是往上走，找不到 2-node，都是 2-node</p>
<p>当根节点到字节点都是3-node节点的时候，根节点也变成了一个4-node节点，这个时候，就需要将跟节点查分为两个2-node节点。4-node 变成 两个2-node 。涉及的情况较多，但是也都是按一定规则再去分裂重组。</p>
<p><br></p>
<h4>B树</h4>
<p>B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有多个子节点。</p>
<p>存储结构上：
<img src="https://www.showdoc.cc/server/api/attachment/visitfile/sign/b3f99ca32b7c6a7d325c18d126f0842c?showdoc=.jpg" alt="" /></p>
<p>节点的变化规则上：
具体多少个，B 树的定义如下
n 是存储关键字（数据）的个数
m 是子树最多的节点拥有子树的个数
⌈m/2⌉-1≤ n ≤m-1 （数据依据，能控制树的高度）</p>
<p>每次增加 or 删除，不满足 ⌈m/2⌉-1≤ n ≤m-1 的节点会经过一系列转换。</p>
<p>这样整体的数高度都不会太高，符合磁盘的快速存储和寻找。</p>
<p><br></p>
<h4>B+ 树</h4>
<p>存储结构上：（比 b 数多了横向）</p>
<p>B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题,正是为了解决这个问题,B+树应用而生.B+树只需要去遍历叶子节点就可以实现整棵树的遍历.而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）</p>
<p><img src="https://www.showdoc.cc/server/api/attachment/visitfile/sign/30a7b047262b279a6fbaf9763a3ad0cf?showdoc=.jpg" alt="" /></p>
<p><img src="https://www.showdoc.cc/server/api/attachment/visitfile/sign/27a5ee2f5668bf44757f766393b9c6bb?showdoc=.jpg" alt="" /></p>
<p>节点的变化规则上：
在 B-树中的每个结点关键字个数 n 的取值范围为⌈m/2⌉ -1≤n≤m-1，而在 B+树中每个结点中关键字个数 n 的取值范围为：⌈m/2⌉≤n≤m，另外，插入的操作全部都在叶子结点上进行</p>
<p>最左缀如何体现？
由于这种存储结构，所以范围查找更快？还是？</p>
<p><img src="https://www.showdoc.cc/server/api/attachment/visitfile/sign/922e713a92a3894fad43069030106ca4?showdoc=.jpg" alt="" /></p>
<p><br></p>
<h4>红黑树</h4>
<p>存储结构上：</p>
<p>红黑树就是二叉树，两个节点，所以不像b树，b+数那样适合磁盘存储，一般用于内存</p>
<p>定义上：
1.树中的节点有两种标记，红色节点和黑色节点；
2.根节点为黑色；
3.每个叶子节点都是空的黑色节点；
4.两个红色节点不能相邻；
5.每个节点，从它开始往叶子节点走的所有路径，每条路径都包含相同数量的黑色节点；</p>
<p><img src="https://www.showdoc.cc/server/api/attachment/visitfile/sign/ef777a04f2c21800b210e852bbf35e15?showdoc=.jpg" alt="" /></p>
<p><img src="https://www.showdoc.cc/server/api/attachment/visitfile/sign/8fa5aac4a0caa4318c358367a269d4a5?showdoc=.jpg" alt="" /></p>
<p>这样定义是为了让二叉树在性质上更像一颗 2-3-4 树
红点的作用就是连接左右，所有才有上面 4、5 两个规子</p>
<p>2-3-4 树在多数程式语言中实现起来相对困难，因为在树上的操作涉及大量的特殊情况。
红黑树实现起来更简单一些，所以可以用它来替代。
总体思想就是定义一系列规则，保证树相对健康的高度（高度健康，意味着查找快速）。</p>