算法 - 符号表-上

img

🏠个人主页:尘觉主页

文章目录

  • 算法 - 符号表
    • 前言
    • 初级实现
      • 1. 链表实现无序符号表
      • 2. 二分查找实现有序符号表
    • 二叉查找树
      • 1. get()
      • 2. put()
      • 3. 分析
      • 4. floor()
      • 5. rank()
      • 6. min()
      • 7. deleteMin()
      • 8. delete()
      • 9. keys()
      • 10. 分析

算法 - 符号表

前言

符号表(Symbol Table)是一种存储键值对的数据结构,可以支持快速查找操作。

符号表分为有序和无序两种,有序符号表主要指支持 min()、max() 等根据键的大小关系来实现的操作。

有序符号表的键需要实现 Comparable 接口。

public interface UnorderedST<Key, Value> {

    int size();

    Value get(Key key);

    void put(Key key, Value value);

    void delete(Key key);
}
public interface OrderedST<Key extends Comparable<Key>, Value> {

    int size();

    void put(Key key, Value value);

    Value get(Key key);

    Key min();

    Key max();

    int rank(Key key);

    List<Key> keys(Key l, Key h);
}

初级实现

1. 链表实现无序符号表

public class ListUnorderedST<Key, Value> implements UnorderedST<Key, Value> {

    private Node first;

    private class Node {
        Key key;
        Value value;
        Node next;

        Node(Key key, Value value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    @Override
    public int size() {
        int cnt = 0;
        Node cur = first;
        while (cur != null) {
            cnt++;
            cur = cur.next;
        }
        return cnt;
    }

    @Override
    public void put(Key key, Value value) {
        Node cur = first;
        // 如果在链表中找到节点的键等于 key 就更新这个节点的值为 value
        while (cur != null) {
            if (cur.key.equals(key)) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        // 否则使用头插法插入一个新节点
        first = new Node(key, value, first);
    }

    @Override
    public void delete(Key key) {
        if (first == null)
            return;
        if (first.key.equals(key))
            first = first.next;
        Node pre = first, cur = first.next;
        while (cur != null) {
            if (cur.key.equals(key)) {
                pre.next = cur.next;
                return;
            }
            pre = pre.next;
            cur = cur.next;
        }
    }

    @Override
    public Value get(Key key) {
        Node cur = first;
        while (cur != null) {
            if (cur.key.equals(key))
                return cur.value;
            cur = cur.next;
        }
        return null;
    }
}

2. 二分查找实现有序符号表

使用一对平行数组,一个存储键一个存储值。

二分查找的 rank() 方法至关重要,当键在表中时,它能够知道该键的位置;当键不在表中时,它也能知道在何处插入新键。

二分查找最多需要 logN+1 次比较,使用二分查找实现的符号表的查找操作所需要的时间最多是对数级别的。但是插入操作需要移动数组元素,是线性级别的。

public class BinarySearchOrderedST<Key extends Comparable<Key>, Value> implements OrderedST<Key, Value> {

    private Key[] keys;
    private Value[] values;
    private int N = 0;

    public BinarySearchOrderedST(int capacity) {
        keys = (Key[]) new Comparable[capacity];
        values = (Value[]) new Object[capacity];
    }

    @Override
    public int size() {
        return N;
    }

    @Override
    public int rank(Key key) {
        int l = 0, h = N - 1;
        while (l <= h) {
            int m = l + (h - l) / 2;
            int cmp = key.compareTo(keys[m]);
            if (cmp == 0)
                return m;
            else if (cmp < 0)
                h = m - 1;
            else
                l = m + 1;
        }
        return l;
    }

    @Override
    public List<Key> keys(Key l, Key h) {
        int index = rank(l);
        List<Key> list = new ArrayList<>();
        while (keys[index].compareTo(h) <= 0) {
            list.add(keys[index]);
            index++;
        }
        return list;
    }

    @Override
    public void put(Key key, Value value) {
        int index = rank(key);
        // 如果找到已经存在的节点键为 key,就更新这个节点的值为 value
        if (index < N && keys[index].compareTo(key) == 0) {
            values[index] = value;
            return;
        }
        // 否则在数组中插入新的节点,需要先将插入位置之后的元素都向后移动一个位置
        for (int j = N; j > index; j--) {
            keys[j] = keys[j - 1];
            values[j] = values[j - 1];
        }
        keys[index] = key;
        values[index] = value;
        N++;
    }

    @Override
    public Value get(Key key) {
        int index = rank(key);
        if (index < N && keys[index].compareTo(key) == 0)
            return values[index];
        return null;
    }

    @Override
    public Key min() {
        return keys[0];
    }

    @Override
    public Key max() {
        return keys[N - 1];
    }
}

二叉查找树

二叉树 是一个空链接,或者是一个有左右两个链接的节点,每个链接都指向一颗子二叉树。

image-20240404154010822

二叉查找树 (BST)是一颗二叉树,并且每个节点的值都大于等于其左子树中的所有节点的值而小于等于右子树的所有节点的值。

BST 有一个重要性质,就是它的中序遍历结果递增排序。

image-20240404154034969

基本数据结构:

public class BST<Key extends Comparable<Key>, Value> implements OrderedST<Key, Value> {

    protected Node root;

    protected class Node {
        Key key;
        Value val;
        Node left;
        Node right;
        // 以该节点为根的子树节点总数
        int N;
        // 红黑树中使用
        boolean color;

        Node(Key key, Value val, int N) {
            this.key = key;
            this.val = val;
            this.N = N;
        }
    }

    @Override
    public int size() {
        return size(root);
    }

    private int size(Node x) {
        if (x == null)
            return 0;
        return x.N;
    }

    protected void recalculateSize(Node x) {
        x.N = size(x.left) + size(x.right) + 1;
    }
}

为了方便绘图,下文中二叉树的空链接不画出来。

1. get()

  • 如果树是空的,则查找未命中;
  • 如果被查找的键和根节点的键相等,查找命中;
  • 否则递归地在子树中查找:如果被查找的键较小就在左子树中查找,较大就在右子树中查找。
@Override
public Value get(Key key) {
    return get(root, key);
}

private Value get(Node x, Key key) {
    if (x == null)
        return null;
    int cmp = key.compareTo(x.key);
    if (cmp == 0)
        return x.val;
    else if (cmp < 0)
        return get(x.left, key);
    else
        return get(x.right, key);
}

2. put()

当插入的键不存在于树中,需要创建一个新节点,并且更新上层节点的链接指向该节点,使得该节点正确地链接到树中。

image-20240404154054094

 @Override
public void put(Key key, Value value) {
    root = put(root, key, value);
}

private Node put(Node x, Key key, Value value) {
    if (x == null)
        return new Node(key, value, 1);
    int cmp = key.compareTo(x.key);
    if (cmp == 0)
        x.val = value;
    else if (cmp < 0)
        x.left = put(x.left, key, value);
    else
        x.right = put(x.right, key, value);
    recalculateSize(x);
    return x;
}

3. 分析

二叉查找树的算法运行时间取决于树的形状,而树的形状又取决于键被插入的先后顺序。

最好的情况下树是完全平衡的,每条空链接和根节点的距离都为 logN。

image-20240404154208696

在最坏的情况下,树的高度为 N。

image-20240404154139062

4. floor()

floor(key):小于等于键的最大键

  • 如果键小于根节点的键,那么 floor(key) 一定在左子树中;
  • 如果键大于根节点的键,需要先判断右子树中是否存在 floor(key),如果存在就返回,否则根节点就是 floor(key)。
public Key floor(Key key) {
    Node x = floor(root, key);
    if (x == null)
        return null;
    return x.key;
}

private Node floor(Node x, Key key) {
    if (x == null)
        return null;
    int cmp = key.compareTo(x.key);
    if (cmp == 0)
        return x;
    if (cmp < 0)
        return floor(x.left, key);
    Node t = floor(x.right, key);
    return t != null ? t : x;
}

5. rank()

rank(key) 返回 key 的排名。

  • 如果键和根节点的键相等,返回左子树的节点数;
  • 如果小于,递归计算在左子树中的排名;
  • 如果大于,递归计算在右子树中的排名,加上左子树的节点数,再加上 1(根节点)。
@Override
public int rank(Key key) {
    return rank(key, root);
}

private int rank(Key key, Node x) {
    if (x == null)
        return 0;
    int cmp = key.compareTo(x.key);
    if (cmp == 0)
        return size(x.left);
    else if (cmp < 0)
        return rank(key, x.left);
    else
        return 1 + size(x.left) + rank(key, x.right);
}

6. min()

@Override
public Key min() {
    return min(root).key;
}

private Node min(Node x) {
    if (x == null)
        return null;
    if (x.left == null)
        return x;
    return min(x.left);
}

7. deleteMin()

令指向最小节点的链接指向最小节点的右子树。

image-20240404154255376

public void deleteMin() {
    root = deleteMin(root);
}

public Node deleteMin(Node x) {
    if (x.left == null)
        return x.right;
    x.left = deleteMin(x.left);
    recalculateSize(x);
    return x;
}

8. delete()

  • 如果待删除的节点只有一个子树, 那么只需要让指向待删除节点的链接指向唯一的子树即可;
  • 否则,让右子树的最小节点替换该节点。

image-20240404154326939

public void delete(Key key) {
    root = delete(root, key);
}
private Node delete(Node x, Key key) {
    if (x == null)
        return null;
    int cmp = key.compareTo(x.key);
    if (cmp < 0)
        x.left = delete(x.left, key);
    else if (cmp > 0)
        x.right = delete(x.right, key);
    else {
        if (x.right == null)
            return x.left;
        if (x.left == null)
            return x.right;
        Node t = x;
        x = min(t.right);
        x.right = deleteMin(t.right);
        x.left = t.left;
    }
    recalculateSize(x);
    return x;
}

9. keys()

利用二叉查找树中序遍历的结果为递增的特点。

@Override
public List<Key> keys(Key l, Key h) {
    return keys(root, l, h);
}

private List<Key> keys(Node x, Key l, Key h) {
    List<Key> list = new ArrayList<>();
    if (x == null)
        return list;
    int cmpL = l.compareTo(x.key);
    int cmpH = h.compareTo(x.key);
    if (cmpL < 0)
        list.addAll(keys(x.left, l, h));
    if (cmpL <= 0 && cmpH >= 0)
        list.add(x.key);
    if (cmpH > 0)
        list.addAll(keys(x.right, l, h));
    return list;
}

10. 分析

二叉查找树所有操作在最坏的情况下所需要的时间都和树的高度成正比。

算法 - 符号表-下

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了,如果有什么疑问的地方请指出,诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力,今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下,创造不易您们的支持是我的动力🤞

img

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/525308.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Latex表格制作详细教程(table, tabular, multirow, multicolumn)

一、简单表格制作 Latex表格需要用到 table 和 tabular 环境。其中 table 环境里写表格的标题(caption&#xff09;、表格的位置之类的。 tabular 环境则是绘制表格的内容。一个简单的表格绘制代码如下所示&#xff1a; \documentclass{article}\begin{document}\begin{table…

怎么保证缓存与数据库的最终一致性?

目录 零.读数据的标准操作 一.Cache aside Patten--旁路模式 二.Read/Write Through Pattern--读写穿透 三.Write Back Pattern--写回 四.运用canal监听mysql的binlog实现缓存同步 零.读数据的标准操作 这里想说的是不管哪种模式读操作都是一样的&#xff0c;这是一种统一…

2 万字 42 道Java经典面试题总结(2024修订版)- Java集合篇

目录 1、Java中常用的集合有哪些&#xff1f;2、Collection 和 Collections 有什么区别&#xff1f;3、为什么集合类没有实现 Cloneable 和 Serializable 接口&#xff1f;4、数组和集合有什么本质区别&#xff1f;5、数组和集合如何选择&#xff1f;6、list与Set区别7、HashMa…

力扣刷题 102.二叉树的层序遍历

目录 题干 解题思路 总结与反思 题干 给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09;。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;[[3],[9…

C语言——顺序表

文章目录 一、线性表二、顺序表顺序表和数组的区别顺序表的分类1.静态顺序表2.动态顺序表 三、动态顺序表的实现1.动态顺序表头文件2.动态顺序表源文件3.测试源文件 一、线性表 线性表&#xff08;linear list&#xff09;是n个具有相同特性的数据元素的有限序列。线性表是⼀种…

LeetCode-33. 搜索旋转排序数组【数组 二分查找】

LeetCode-33. 搜索旋转排序数组【数组 二分查找】 题目描述&#xff1a;解题思路一&#xff1a;二分查找。1.找哨兵节点&#xff08;nums[0]或nums[-1]&#xff09;可以确定nums[mid]位于前一段或后一段有序数组中。2. 就是边界left和right的变换&#xff0c;具体看代码。解题思…

阿里面试总结

ThreadLocal 线程变量存放在当前线程变量中&#xff0c;线程上下文中&#xff0c;set将变量添加到threadLocals变量中 Thread类中定义了两个ThreadLocalMap类型变量threadLocals、inheritableThreadLocals用来存储当前操作的ThreadLocal的引用及变量对象&#xff0c;把当前线程…

MySQL数据库版本为5.5.62,时间戳超出2038年1月19日的解决方案

MySQL数据库版本是 5.5.62&#xff0c;已设置字段的类型为BIGINT&#xff0c;使用FROM_UNIXTIME()函数来转换时间戳&#xff0c;返回NULL。 SELECT FROM_UNIXTIME(1617970800)SELECT FROM_UNIXTIME(2185743121)MySQL数据库版本为5.5.62&#xff0c;已设置字段的类型为BIGINT&a…

golang web 开发 —— gin 框架 (gorm 链接 mysql)

目录 1. 介绍 2. 环境 3. gin 3.1 gin提供的常见路由 3.2 gin的分组 main.go router.go 代码结构 3.3 gin 提供的Json方法 main.go route.go common.go user.go order.go 3.4 gin框架下如何获取传递来的参数 第一种是GET请求后面直接 /拼上传递的参数 第二种是…

Rust语言入门第一篇-环境搭建

Rust语言入门第一篇 Rust官网 一&#xff0c;环境搭建 1、C开发环境配置 Rust 语言的底层是依赖于 C/C 编译器的。在安装 Rust 编译器时&#xff0c;通常会自动安装所需的 C/C 编译环境&#xff0c;以便 Rust 能够生成可执行文件或库。因此&#xff0c;在安装 Rust 之前&…

用Vue全家桶手工搓了一个类似抖音短视频的软件,全开源

用Vue全家桶手工搓了一个类似抖音短视频的软件&#xff0c;全开源 软件简介 用Vue全家桶手工搓了一个高仿抖音&#xff0c;全开源 PC浏览器请用手机模式访问。先按F12调出控制台&#xff0c;再按CtrlShiftM切换到手机模式&#xff0c;手机请用Via浏览器或者Chrome浏览器预览。…

Vue的学习之旅-part4

Vue的学习之旅-part1 vue的自带指令v-if v-else-if v-else虚拟DOM的复用v-show 与 v-if 的不同之处&#xff1a;v-if v-show各自合适的使用位置&#xff1a; v-for 循环v-for 循环遍历 :key"item" 绑定key&#xff0c;区分循环的内容循环的应用&#xff1a; 前几篇博…

目标检测——色素性皮肤病数据集

一、重要性及意义 首先&#xff0c;色素性皮肤病变是一类常见的皮肤疾病&#xff0c;其发病率有逐年增高的趋势。这些病变可能由遗传或环境因素导致黑素细胞生成异常&#xff0c;如黑色素瘤等。黑色素瘤具有极高的恶性率和致死率&#xff0c;而且恶化可能性大&#xff0c;容易…

汇编——SSE打包整数

SSE也可以进行整数向量的加法&#xff0c;示例如下&#xff1a; ;sse_integer.asm extern printfsection .datadummy db 13 align 16pdivector1 dd 1dd 2dd 3dd 4pdivector2 dd 5dd 6dd 7dd 8fmt1 db "Packed Integer Vector 1: %d, %d, %d, %d",…

鸿蒙ArkTS开始实例:【canvas实现签名板功能】

使用ArkTS中的canvas实现签名板的功能&#xff0c;canvas画布大家都很熟悉&#xff0c;我们会用它经常实现一些画板或者图表、表格之类的功能。canvas签名板是我在开发APP过程中实现的一个功能&#xff0c;开发过程中也是遇到比较多的问题。我会按照以下几点来讲解开发整个过程…

面试算法-153-旋转图像

题目 给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像&#xff0c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,2,3],[4,5,6],[7,8,…

计算机网络实验——学习记录四(TCP协议)

1. 打开TCP服务&#xff1a; nc -e /bin/sh -lv 4499 注释&#xff1a; &#xff08;1&#xff09;nc是Linux下启动通讯服务的命令&#xff1b; &#xff08;2&#xff09;-e表示在nc命令后再执行bin文件夹下的shell命令&#xff0c;启动shell命令会导致所有从TCP连接传递到…

JavaEE初阶——多线程(一)

T04BF &#x1f44b;专栏: 算法|JAVA|MySQL|C语言 &#x1faf5; 小比特 大梦想 此篇文章与大家分享多线程的第一部分:引入线程以及创建多线程的几种方式 此文章是建立在前一篇文章进程的基础上的 如果有不足的或者错误的请您指出! 1.认识线程 我们知道现代的cpu大多都是多核心…

【蓝桥杯嵌入式】第十三届省赛(第二场)

目录 0 前言 1 展示 1.1 源码 1.2 演示视频 1.3 题目展示 2 CubeMX配置(第十三届省赛第二场真题) 2.1 设置下载线 2.2 HSE时钟设置 2.3 时钟树配置 2.4 生成代码设置 2.5 USART1 2.5.1 基本配置 2.5.2 NVIC 2.5.3 DMA 2.6 TIM 2.6.1 TIM2 2.6.2 TIM4 2.6.3 …

ICP配准算法

配准算法 问题定义ICP(point to point)算法思想步骤分解point to point和point to plane的区别ICP配准算法的标准流程NDT 本篇将介绍配准算法&#xff0c;将介绍ICP(point to point)、ICP(point to plane)和NDT算法。其中ICP有两种&#xff0c;point to point表示通过构建点与点…