树

二叉树

满足以下条件的树就是二叉树：

树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2。

满二叉树

如果二叉树中除了叶子结点，每个结点的度都为2，则此二叉树称为满二叉树。

完全二叉树

如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。

二叉查找树（BST）

也称二叉搜索树或二叉排序树，是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

AVL树

平衡二叉树又称为AVL树，是一种特殊的二查搜索树。

任意节点左右子树高度之差的绝对值不超过1。

平衡二叉树的搜索和插入，删除时间复杂度都是O(logn)。

平衡因子

某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子，平衡二叉树中不存在平衡因子大于 1 的节点。

在一棵平衡二叉树中，节点的平衡因子只能取 0 、1 或者 -1 ，分别对应着左右子树等高，左子树比较高，右子树比较高。

红黑树

红黑树是一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。

通过着色的方式的限制，红黑树确保任意节点到叶子节点的路径最长不超过最短路径的2倍。

红黑树的搜索和插入，删除时间复杂度O(logn)。

基本特点：

每个节点非红即黑。

根节点是黑的。

每个叶节点（叶节点即树尾端NULL指针或NULL节点）都是黑的。

红色节点的子节点都是黑色的。

任意节点到叶子节点的路径都包含相同数目的黑节点。

如何实现平衡：

通过改变节点颜色和左右旋转实现高度平衡。

红黑树较AVL树的优点：

AVL树是高度平衡的，频繁的插入和删除，会引起频繁的Rebalance，导致效率下降

红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转

• 红黑树在查找，插入删除的性能都是O(logn)，且性能稳定

Trie树

Trie树（前缀树）是一种用于高效检索的树形数据结构，主要用于字符串处理

Trie树主要特点：

• 共享相同前缀的字符串路径，从而降低了空间复杂度和查询时间

跳跃表

对于下面这个链表，需要查找元素9。

• 一共遍历8个节点才能找到元素9。

由于元素是有序的，可以通过增加一些路径来加快查找速度。

• 通过这种方法，只需要遍历5次就可以找到元素9了（红色线路为查找路径）。

如果再加一层，只需要查找4次就能找到了。

对于具有n个元素的链表，可以采取（logn+1）层指针路径的形式

• 就可以实现在O(logn)的时间复杂度内，查找到某个目标元素了，这种数据结构，称之为跳跃表。

跳跃表有关性质

跳跃表的每一层都是一条有序的链表。

跳跃表的查找次数近似于层数

• 时间复杂度为O(logn)，插入、删除也为O(logn)。

最底层的链表包含所有元素。

跳跃表是一种随机化的数据结构(通过抛硬币来决定层数)。

跳跃表的空间复杂度为O(n)。

查找操作

顶层索引节点定位：

• 从顶层索引节点开始，跳跃表会比较顶层索引节点所指向的节点值与目标值的大小关系
  • 然后根据比较结果选择继续向右移动还是向下移动。

向下移动：

• 如果顶层索引节点所指向的节点值小于目标值，则跳跃表将向右移动到下一个节点进行比较
  • 直到找到大于或等于目标值的节点为止。

回溯与向下查找：

• 一旦跳跃表在某一层找到了不小于目标值的节点后，就会回溯到下一层该节点所对应的位置
  • 然后继续向下查找，直到定位到目标节点或者无法向下查找为止。

插入操作

在跳跃表中进行插入操作时，首先需要确定插入节点的层数。

• 跳跃表通过随机生成节点的层数

使得每个插入的节点都有一个随机的层数

• 这种特性使得跳跃表可以根据数据动态调整索引结构，从而保证插入操作的高效性。

布隆过滤器

布隆过滤器它实际上是一个很长的二进制向量和一系列随机映射函数。

• 可以用于检索一个元素是否在一个集合中。

它的优点是空间效率和查询时间都远远超过一般的算法。

• 缺点是有一定的误识别率和删除困难。

布隆过滤器原理：

当一个元素被加入集合时，通过 K 个散列函数将这个元素映射成一个位数组中的 K 个点，把它们置为 1。

检索时，我们只要看看这些点是不是都是 1 就（大约）知道集合中有没有它了：

• 如果这些点有任何一个 0，则被检元素一定不在。
• 如果都是 1，则被检元素很可能在。

如上图，位数组的长度是８，散列函数个数是 3，先后保持两个元素ｘ，ｙ。

• 这两个元素都经过三次哈希函数生成三个哈希值，并映射到位数组的不同的位置，并置为1。

元素 x 映射到位数组的第０位，第４位，第７位，元素ｙ映射到数组的位数组的第１位，第４位，第６位。

保存元素 x 后，位数组的第4位被设置为1之后，在处理元素 y 时第4位会被覆盖，同样也会设置为 1。

• 当布隆过滤器保存的元素越多，被置为 1 的 bit 位也会越来越多。

元素 x 即便没有存储过，假设哈希函数映射到位数组的三个位都被其他值设置为 1 了。

• 对于布隆过滤器的机制来讲，元素 x 这个值也是存在的，也就是说布隆过滤器存在一定的误判率。

如何减少布隆过滤器的误判？

增加二进制位数。

增加 Hash 的次数（Hash函数个数）。

• 其实每一次 Hash 处理都是在增加数据的特征，特征越多，出现误判的概率就越小。

布隆过滤器支持删除吗?

不支持删除元素，因为多个元素可能哈希到一个布隆过滤器的同一个位置。

• 如果直接删除该位置的元素，则会影响其他元素的判断。

时间和空间效率

布隆过滤器的空间复杂度为 O(m) ，插入和查询时间复杂度都是 O(k) 。

存储空间和插入、查询时间都不会随元素增加而增大。

• 空间、时间效率都很高。

哈希函数类型

Murmur3，FNV 系列和 Jenkins 等非密码学哈希函数适合。

Murmur3 算法简单，能够平衡好速度和随机分布。

• 很多开源产品经常选用它作为哈希函数。

使用场景

缓存穿透场景:

首先需要初始化布隆过滤器，然后当用户请求时，判断过滤器中是否包含该元素。

• 若不包含该元素，则直接返回不存在。

若包含则从缓存中查询数据，若缓存中也没有。

• 则查询数据库并回写到缓存里，最后给前端返回。

黑名单校验

识别垃圾邮件，只要是邮箱在黑名单中的邮件，就识别为垃圾邮件。

假设黑名单的数量是数以亿计的，存放起来就是非常耗费存储空间的。

• 布隆过滤器则是一个较好的解决方案。

把所有黑名单都放在布隆过滤器中，在收到邮件时，判断邮件地址是否在布隆过滤器中即可。

元素删除场景：

现实场景，还存在删除元素的场景，比如说商品的删除。

两种方案：

计数布隆过滤器：

在插入元素时给对应的 k （k 为哈希函数个数）个 Counter 的值分别加 1。

• 删除元素时给对应的 k 个 Counter 的值分别减 1。

虽然计数布隆过滤器可以解决布隆过滤器无法删除元素的问题。

• 但是：更多的资源占用，而且在很多时候会造成极大的空间浪费。

定时重新构建布隆过滤器:

从工程角度来看，定时重新构建布隆过滤器这个方案可行也可靠，同时也相对简单。

定时任务触发全量商品查询

将商品编号添加到新的布隆过滤器

• 任务完成，修改商品布隆过滤器的映射（从旧 A 修改成 新 B ）

商品服务根据布隆过滤器的映射，选择新的布隆过滤器B进行相关的查询操作

选择合适的时间点，删除旧的布隆过滤器 A

Hash

Hash叫做散列表，就是把任意长度的输入，通过散列算法，变成固定长度输出，该输出结果是散列值。

这种转换是一种压缩映射，散列表的空间通常小于输入的空间，不同的输入可能会散列成相同的输出，所以不能从散列表来唯一的确定输入值，这就出现了Hash冲突。

Hash冲突：

根据Key（键）即经过一个函数F(key)得到的结果的作为地址去存放当前的Key Value键值对(这个是HashMap的存值方式)，但是却发现算出来的地址上已经被占用了，这就是所谓的Hash冲突。

解决Hash冲突

开放定址法：

• 也叫做再散列法，基本原理是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，直到找出一个不冲突的哈希地址pi。

再Hash法：

• 这种方法就是同时构造多个不同的哈希函数。

• 当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key），直到冲突不再产生。

• 这种方法不易产生聚集，但增加了计算时间。

链地址法（Java就是采用这种方法）:

• 将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。
• 链地址法适用于经常进行插入和删除的情况。

建立公共溢出区：

• 将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。