查找

顺序查找

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

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;

二叉查找树

  • 高效

特点

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

每个孩子又是二叉查找树

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

插入

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

  • floor:是最接近key值且 小于 key的节点
  • ceil:是最接近key值且 大于 key的节点

遍历

  • 前序遍历

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

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

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

局限性

  • 同样的数据会对应不同的查找树
    • 有可能退化成链表

2-3查找树

插入

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

节点分裂

插入示例

删除

红黑树

基本操作

旋转

反色

插入

新插入的节点均设为红色

  • 情况1

对b逆时针旋转

  • 情况2

反色

  • 情况3

进行顺时针旋转,变成情况2

删除

散列表

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

散列函数

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

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

散列冲突

当不同的输入得到相同的hash值时,称为散列冲突

解决:拉链法

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

解决:线性探测

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

  • 在查找的时候,如插入一样一直进行线性探测,直至碰到一个键为空的槽

删除

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

调整大小

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

java中的实现

JDK8后,HashMap当冲突列表超过8个之后,会使用红黑树

results matching " "

No results matching " "

results matching " "

No results matching " "