查找

顺序查找

按照顺序一个个比较,直到序列末尾

int seq_search(int array[], int n, int key)
{
    int i;
    for(i = 0; i < n; i++)
    {
        if(key == array[i])
        {
            return i;   //查找成功
        }   
    }
    return -1;          //查找失败
}

二分查找

通过对一个有序数组中对元素依次比较,从而能实现对数级别时间复杂度的查找

二分查找

根据左右指针计算出一个mid指针 如果mid指针处的元素等于目标值 则要查找的目标就是在这里

否则如果mid处的指针比目标值大 则右指针等于mid-1 否则左指针等于mid+1

然后重复上述操作 直到左指针大于右指针

int l = 0, r = a.length - 1;
while (l <= r) {
    int mid = l + (r - l) / 2;
    if (a[mid].equals(target)) {
        return mid;
    }
    
    if (less(target, a[mid])) {// 要查找的元素在左边
        r = mid - 1;
    } else if (greater(target, a[mid])) { // 要查找的元素在右边
        l = mid + 1;
    }
}
return -1;

这个算法在快速定位BUG的时候也挺好用,一分为二,确定问题在前端还是后端,再继续划分,确定问题在系统哪一层

二叉查找树

特点

每个结点的键值大于左孩子,小于右孩子

每个孩子又是二叉查找树

二分查找树不一定是完全二叉树

对于任何节点:

插入

if (root == null) {
    count++;
    return new Node(key, value); // 当前节点为null,则创建一个节点返回
}
if (key.equals(root.key)) { // 当前节点等于要插入的节点,则直接覆盖
    root.value = value;
} else if (less(key, root.key)) { // 当前节点比要插入的大,则向当前节点的左子树插入
    root.left = insert(root.left, key, value);
} else if (greater(key, root.key)) {  // 当前节点比要插入的小,则向当前节点的右子树插入
    root.right = insert(root.right, key, value);
}

查找

原理同插入,根据左子树比父节点小,右子树比父节点大的条件

if (root == null){
    return null;
}
if (key.equals(root.key)){
    return root.value;
}else if(less(key,root.key)){
    return search(root.left,key);
}else {
    return search(root.right,key);
}

floor与ceil

遍历

先访问当前节点,再递归访问左右子树

if (root != null){
    consumer.accept(root.key,root.value);
    preOrder(root.left,consumer);
    preOrder(root.right,consumer);
}

先递归访问左子树,再访问自身,再递归访问右子树

if (root != null){
    preOrder(root.left,consumer);
    consumer.accept(root.key,root.value);
    preOrder(root.right,consumer);
}

先递归访问左右子树,在访问自身

if (root != null){
    preOrder(root.left,consumer);
    preOrder(root.right,consumer);
    consumer.accept(root.key,root.value);
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
    var node = queue.remove();
    consumer.accept(node.key,node.value);
    if (node.left != null){
        queue.add(node.left);
    }
    if (node.right != null){
        queue.add(node.right);
    }
}

删除

分为三种情况

private Node removeMax(Node node) {
    
    if (node.right == null) {
        // 代表当前节点就是最大节点,所以返回当前节点的左子树给父节点
        count--;
        return node.left;
    }
    // 将删除的节点的左子树作为父节点的右子树
    node.right = removeMax(node.right);
    return node;
}

Hubbard Deletion

使用被删除节点右子树中的最小节点来代替被删除节点

局限性

平衡二叉树

AVL树

在增加和删除节点时通过旋转来保持平衡

右旋:以某个节点为中心 将它沉入当前右子节点的位置 然后让当前左子节点作为新树的根

屏幕截图 2020-09-22 120018

左旋:

屏幕截图 2020-09-22 120118

2-3查找树

20227816630

搜索

搜索的过程和二叉树并没有太多的区别,只是遇到 3 节点的时候,多判断一次是否介于 a、b 之间

插入

2-3树之所以完美平衡,关键在于插入时的维护

插入的时候节点分裂

删除

红黑树

红黑树,正是采用标准的二叉查找树节点附着上额外的颜色信息来表示 2-3 树的实现,每一个红色节点都和它的父亲节点一起,构成了一个 3 节点的模拟,通过旋转操作完成 2-3 节点的合并和分裂,从而在不改变二叉树节点结构的前提下,保证二叉树的有序性和平衡性

红黑树不追求左右子树高度差不超过1

而是保证从根节点到叶尾的最长路径不超过最短路径的2倍

其他约束条件:

红黑树的任何旋转至多3次就能完成

这些约束,都是为了保证每一颗红黑树和 2-3 Tree 是一一对应的

20227816326

基本操作

旋转

左旋:本质上就是将某个 3 节点从以较小的键为根转移成较大的键为根

202278164648

反色

插入

新插入的节点均设为红色

黑节点插入

202278164949

红节点插入

202278165136

20227816521

颜色反转

删除

跳表

202031284446

查找时,从上层开始查找,找到对应的区间后再到下一层继续查找,类似于二分查找

这种查找数据结构跟红黑树相比:

完美跳表:所用的存储空间和查询过程,应该和二叉树是非常像的,要求每一层都包含下一层一半的节点,且同一层指针跨越的节点数量是一样的,第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2,第 k级索引结点的个数就是 $\frac{n}{2^k}$

但随着元素不断增减,很难维护这样的完美跳表,在插入元素时可以引入随机性:通过随机函数来决定将将结点插入到哪一层索引中,来维护索引和原始链表大小的平衡,避免退化为链表的查找效率

散列表

根据键(Key)而直接访问在内存存储位置的数据结构,也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度

stateDiagram-v2
    aaa --> hash(key)
    aab --> hash(key)
    aac --> hash(key)
    hash(key) --> 1
    hash(key) --> 3
    hash(key) --> 9

散列函数

这个过程会将键转化为数组的索引

把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值

设计散列函数

  1. 要保证散列函数输出的数值是一个非负整数,因为这个整数将是散列表底层数组的下标
  2. 在使用有限数组空间的前提下,导致的哈希冲突尽量少
  3. 不宜过于复杂,避免过多计算开销

装载因子

装载因子被用来描述散列表 已用槽数 / 总槽数 比值,当这个值过大,会加剧散列冲突,当值过小,会浪费存储空间

散列冲突

当不同的输入得到相同的hash值时,称为散列冲突,理想的散列函数:如果 key1 ≠ key2,那 hash(key1) ≠ hash(key2),但这很难

不管采用哪种探测方法,当散列表中空闲位置不多的时候,散列冲突的概率就会大大提高

拉链法

当发生碰撞的时候,拉链法是将碰撞的元素串成一个链表

拉链法

比较适合存储大对象、大数据量的散列表,而且,比起线性探测,它更加灵活,支持更多的优化策略,比如用红黑树代替链表

线性探测

当发生碰撞的时候,直接检查散列表中的下N个位置(N可正可负)

线性探测

这种方法删除数据的时候比较麻烦,需要特殊标记已经删除掉的数据。而且所有的数据都存储在一个数组中,比起拉链法来说,冲突的代价更高

二次探测

二次探测探测的下标序列是 $hash(key)+0$,$hash(key)+1^2$,$hash(key)+2^2$……

双重散列

使用一组散列函数 hash1(key),hash2(key),hash3(key)……先用第一个散列函数,如果计算得到的存储位置已经被占用,再用第二个散列函数,依次类推

删除

删除的时候,不能简单地将槽置为空,需要将与该键同散列值的键都往前移动,填补因为该键被删除而造成的空缺

调整大小

当数组大小发生改变,不能直接位置一对一迁移,而是需要对先前的每个元素,重新计算散列(rehash),重新放入槽

当散列表过大时,一次性扩容会耗费更多时间,一种优化手段是渐进式扩容

时间轮

round时间轮

2022616155327

时间轮被划分为 8 个 slot,每个 slot 代表 1s,当前时针指向 2。假如现在需要调度一个 3s 后执行的任务,应该加入 2+3=5 的 slot 中;如果需要调度一个 12s 以后的任务,需要等待时针完整走完一圈 round 零 4 个 slot,需要放入第 (2+12)%8=6 个 slot

怎么区分每个任务是否需要立即执行,还是需要等待下一圈 round,甚至更久时间之后执行呢?所以我们需要把 round 信息保存在任务中。例如图中第 6 个 slot 的链表中包含 3 个任务,第一个任务 round=0,需要立即执行;第二个任务 round=1,需要等待 18=8s 后执行;第三个任务 round=2,需要等待 28=8s 后执行。所以当时针转动到对应 slot 时,只执行 round=0 的任务

分层时间轮

2022616155817

当上层的时间轮转完一圈时,下层的定时器就要增加一个刻度

假设我们的任务需要在每天的 7:30:20 秒执行一次。任务首先添加于小时级别时钟轮的第 7 号刻度上,当其轮询线程访问到第 7 号刻度时,就将此任务转移到分钟级别时钟轮的第 30 号刻度上。当分钟级别的时钟轮线程访问到第 30 号刻度,就将此任务转移到秒级别时钟轮的第 20 号刻度上。当秒级别时钟轮线程访问到第 20 号刻度时,最终会将任务交给异步线程负责执行