二叉树

二叉树的特点是，左子树的键值小于根的键值，右子树的键值大于根的键值

然而二叉树在某些场景下，会是这样的构造

这种构造的二叉树是非均衡的，层级过高，甚至曾经进化成链表，会导致查问效率过低

均衡二叉树（AVL）

在二叉树的根底上，衍生出了均衡的二叉树，均衡二叉树的规定是，任何节点的两个子树的高度差<=1

以上述二叉树为例，在插入1~5的时候，过程如下

能够看见每次子树的高度差在大于1的时候，均衡二叉树都会进行旋转，让构造保持平衡

依据失衡前的状态，能够分为4种状态
LL:插入或删除一个节点后，发现根节点的左节点的左节点下还有非空节点，导致根节点的左节点的高度比根节点的右节点的高度大2，均衡树失衡，须要进行旋转来保持平衡，示意图如下

LR:插入或删除一个节点后，发现根节点的左节点的右节点下还有非空节点，导致根节点的左节点的高度比根节点的右节点的高度大2，均衡树失衡，须要进行旋转来保持平衡，示意图如下

RR:插入或删除一个节点后，发现根节点的右节点的右节点下还有非空节点，导致根节点的右节点的高度比根节点的左节点的高度大2，均衡树失衡，须要进行旋转来保持平衡，示意图如下

RL:插入或删除一个节点后，发现根节点的右节点的左节点下还有非空节点，导致根节点的右节点的高度比根节点的左节点的高度大2，均衡树失衡，须要进行旋转来保持平衡，示意图如下

均衡二叉树谋求相对均衡，每次插入或删除新节点之后须要旋转的次数不能预知，如果相干的插入和删除操作并不频繁，而是查找操作绝对更频繁，那么就优先选择均衡二叉树树进行实现

红黑树

红黑树也是一种均衡的二叉树，不过相比于AVL树，红黑树的均衡没有那么相对，红黑树须要一直的去变色或者旋转来满足以下规定：

  • 节点是红色或彩色。
  • 根是彩色。
  • 所有叶子都是彩色（叶子是NIL节点）。
  • 每个红色节点必须有两个彩色的子节点。（从每个叶子到根的所有门路上不能有两个间断的红色节点。）
  • 从任一节点到其每个叶子的所有简略门路都蕴含雷同数目的彩色节点（简称黑高）。

Hash表

说到hash表，很多人会想到hashmap，hash表是一种基于散列，在关键字key和值value之间建设映射关系f的数据结构，这种映射关系f咱们称为哈希函数，通过计算并存储value的这块间断存储空间称为哈希表，通过计算的key失去的存储地址称为哈希地址。

1.哈希函数

哈希函数有多种计算方法

  • 间接定址法：将key的某个线性函数值作为哈希地址
  • 数字分析法：选取key中的一部分作为运算参数计算哈希地址
  • 平方取中法 ：对key进行平方计算，取两头段作为哈希地址
  • 折叠法：将key分成长度雷同的几段，计算叠加和，再选取后几位作为哈希地址
  • 除留余数法 ：对key间接取模（求余数），将值作为哈希地址
  • 随机数法：取key的随机函数值作为哈希地址
2.哈希碰撞（哈希抵触）

在进行哈希函数计算之后，失去的hash值仍然有相等的可能，这种景象称作哈希碰撞，智慧的先驱者们又想出了几种计划来解决这种抵触问题。

3.哈希碰撞解决方案
  • 凋谢地址法：发生冲突就去探测寻找下一个空的地址，凋谢地址法有可能会产生多个不同key探测到同一个空的地址并进行竞争的景象，称为沉积
  • 再哈希：发生冲突后，采纳另一个哈希函数进行哈希运算，直到失去一个惟一的哈希地址
  • 链表地址法：对于每个哈希地址，都保护一个单向链表进行value的存储，链表的每个节点都存储下一个节点的指针地址，hashmap就是用的这种数据结构
  • 公共溢出区法：保护两张表，根本表和溢出表，将未发生冲突的数据放入根本表，将发生冲突的数据放入溢出表，查问时先在根本表中查找到对应哈希地址的地位并比拟（揣测应该是在哈希地址雷同的根底上进一步比拟key），如果不相等再去溢出表中查找
    ps:对于溢出表中多个雷同哈希地址的数据，我也查阅了很多材料，然而这块没有说的比拟清晰的，集体猜想溢出表的构造也是以链表的模式进行存储的

B-tree

B-tree的构造如图所示，它的所有指针，或者叫索引元素不反复，因而，B-tree的数据在每一阶都有相应的存储数据。另外，它的叶子节点没有指针，只单纯的存储数据。


（相干图例援用自https://blog.csdn.net/a764340703/article/details/82621781）

B+tree

B+tree的构造如图所示，它和B-tree最大的区别在于：

  • B+tree的非叶子节点会有冗余索引
  • B+tree的所有数据全副存储在叶子节点上，这样操作益处在于同阶条件下，能存储更多的数据
  • B+tree的叶子节点有双向指针，对于范畴查找的效率能大大晋升

更多的B+tree构造在数据库中的利用我会在mysql章节介绍，敬请期待

举荐一个数据结构可视化网站，来自旧金山大学 David Galles
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html