算法笔记:点四叉树

  • 点四叉树是一种用于主要是针对空间点存储与索引的树形数据结构
  • 在点四叉树中,空间被分割成四个矩形,四个不同的多边形对应于SW、NW、SE、NE四个象限

1 基本操作

1.1 初始化

创建一个根节点,该节点代表整个二维空间区域

1.2 插入点

  • 当一个新点需要被插入
    • 从根节点开始,根据点的坐标确定它应该属于哪个象限,并递归地进入该象限。
      • 对于k维数据空间而言,以新插入的点为中心将其对应索引空间分为两两不相交的2k个子空间,依次与它的2k个孩子结点相对应,对于位于某一子空间的点,则分配给对应的子树

1.3 查询

查询一个区域内的所有点时,从根节点开始,检查该区域与每个节点(象限)的交集,并递归地进入与查询区域有交集的节点。

2 举例

假设我们有一个二维空间,范围是[0, 16) x [0, 16),我们要插入以下几个点:

  • A(2, 3)
  • B(4, 7)
  • C(14, 14)
  • D(9, 4)

2.1 初始化

初始时,有一个[0, 16) x [0, 16)的正方形作为根节点

2.2 插入点

2.2.1 插入A:

2.2.2 插入B:

2.2.3 插入C:

2.2.4 插入D

D在以B为中心的右下方,不用再分割空间

2.2.5 建树

3 优缺点

3.1 优点

  • 结构简单
  • 对于精确匹配的点查找性能较高

3.2 缺点

  • 树的动态性差,删除结点处理复杂
    • 比如上面例子中删除B点之后,应该是C还是D跟上去?如果C,D还有子节点呢?
  • 每一个节点除了存储有子节点的信息外,还需要存很多的空指针
    • 比如上面A点,除了存储B外,其他三个象限还需要存空指针
      • ——>空间存储开销大,空间利用率第

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于SSM的新能源汽车在线租赁系统

末尾获取源码 开发语言:Java Java开发工具:JDK1.8 后端框架:SSM 前端:采用Vue技术开发 数据库:MySQL5.7和Navicat管理工具结合 服务器:Tomcat8.5 开发软件:IDEA / Eclipse 是否Maven项目&#x…

ELK高级搜索(三)

文章目录 11.索引Index入门11.1 索引管理11.2 定制分词器11.3 type底层结构11.4 定制dynamic mapping11.5 零停机重建索引 12.中文分词器 IK分词器12.1 Ik分词器安装使用12.2 ik配置文件12.3 使用mysql热更新 13.java api 实现索引管理14&…

kafka-- kafka集群环境搭建

kafka集群环境搭建 # 准备zookeeper环境 (zookeeper-3.4.6) # 下载kafka安装包 https://archive.apache.org/dist/kafka/2.1.0/kafka_2.12-2.1.0.tgz # 上传 : 172.16.144.133 cd /usr/local/softwaretar -zxvf /usr/local/software/kafka_2.12-2.1.0.tgz -C /usr/local…

Kubernetes_概念篇

Kubernetes_概念篇 一、架构二、概念1,Label(对象标签)2,Namespace3,Deployment4,Service 三、资源对象Master组件1,kube-apiserver2,kube-controller-manager3,kube-sch…

go语言基础语法

1、注释 package mainimport "fmt"/* *多行注释*/ func main() {//单行注释fmt.Println("hello world") }2、变量 2.1、变量定义 标准格式 var 变量名 变量类型 如 var age int Go语言的基本类型有: boolstringint、int8、int16、int32、…

什么是安全运营中心(SOC),应该了解什么

安全运营中心(SOC) 是一种企业监视和警报设施,可帮助组织检测安全威胁、监视安全事件和分析性能数据以改进公司运营。 什么是安全运营中心(SOC) 安全运营中心(SOC)是一个中央监视和监视中心&a…

Flowable7 设计器

1、flowable7 已经在主版本上移除了Flowable UI相关的包,包含bpm-json相关的所有包和流程设计器相关前端文件。 2、flowable7 版本目前只保留了xml运行相关的包,ui modeler已经移除 3、目前官方给的回复是只能在 flowable 云产品上使用设计器&#xff…

Servlet属性、监听者和会话

没有servlet能单独存在。在当前的现代Web应用中,许多组件都是在一起协作共同完成一个目标。怎么让这些组件共享信息?如何隐藏信息?怎样让信息做到线程安全? 1 属性和监听者 1.1 初始化 容器初始化一个servlet时,会为…

国标GB28181视频平台EasyGBS国标视频云平台级联到EasyCVR,上级平台无法播放通道视频的问题解决方案

EasyGBS国标视频云平台是基于国标GB28181协议的视频能力兼服务平台,可实现的视频能力包括将设备通过国标GB28181协议接入、流媒体转码、处理及分发、直播录像、语音对讲、云存储、告警、平台级联等功能。其中,平台级联功能是指平台与平台之间可以通过国标…

真香:Alibaba开源GitHub星标100K微服务架构全彩进阶手册

前言: 微服务架构作为一种高效灵活的应用架构,正在成为企业级应用开发的主流选择。在众多的微服务架构指南中,阿里巴巴开源的GitHub微服务架构全彩进阶手册备受瞩目,其100star更是证明了其在开发者社区中的重要地位。 这本手册汇…

结构体的简单介绍(2)

目录 结构体的特殊声明 结构体的自引用 结构体的特殊声明 在声明结构的时候,可以不完全的声明。 比如: struct {int a;char b;float c; }x; 以上结构在声明的时候省略掉了结构体标签(tag)。 那么会有什么影响呢&#xff1f…

Unity 切换场景后场景变暗

问题 Unity版本:2019.4.34f1c1 主场景只有UI,没有灯光,天空盒;其他场景有灯光和天空盒所有场景不烘焙主场景作为启动场景运行,切换到其他场景,场景变暗某一个场景作为启动场景运行,光影效果正…

【zip密码】zip压缩包删除密码方法

Zip压缩包设置设置了密码,想要删除密码,除了将压缩包解压出来之后再将文件压缩为不带密码的压缩文件以外,还有一种删除密码的方法。设置方法如下: 右键点击zip文件,找到打开方式,以Windows资源管理器方式打…

数据结构:排序解析

文章目录 前言一、常见排序算法的实现1.插入排序1.直接插入排序2.希尔排序 2.交换排序1.冒泡排序2.快速排序1.hoare版2.挖坑版3.前后指针版4.改进版5.非递归版 3.选择排序1.直接选择排序2.堆排序 4.归并排序1.归并排序递归实现2.归并排序非递归实现 5.计数排序 二、排序算法复杂…

手写Mybatis:第17章-Plugin插件功能实现

文章目录 一、目标:Plugin插件二、设计:Plugin插件三、实现:Plugin插件3.1 工程结构3.2 Plugin插件代理模式类图3.3 自定义拦截注解3.3.1 方法签名3.3.2 拦截注解 3.4 拦截器接口定义3.4.1 调用信息3.4.2 拦截器接口 3.5 类代理包装操作3.5.1…

Vulnhub: Hogwarts: Bellatrix靶机

kali:192.168.111.111 靶机:192.168.111.228 信息收集 端口扫描 nmap -A -sC -v -sV -T5 -p- --scripthttp-enum 192.168.111.228访问80端口 查看源码,提示ikilledsiriusblack.php和文件包含的参数名file 漏洞利用 ikilledsiriusblack.p…

seata升级1.1.0后遇到io.seata.common.exception.ShouldNeverHappenException

我们这一节主要讲的是seata升级后的主要修改,至于seata的基本部署可以参考我之前的随笔。 一开始我在升级SpringBoot版本之后,seata就突然启动不起来了,报了下面的错: Caused by: io.seata.common.exception.ShouldNeverHappenExc…

etcd读写请求的执行过程

etcd读请求如何执行 首先,etcdctl 会对命令中的参数进行解析。在解析完请求中的参数后,etcdctl 会创建一个 clientv3 库对象通过gRPC API来访问 etcd server。对应流程一。 然后通过负载均衡算法选择一个etcd server节点,然后调用 etcd ser…

互联网医院|医疗系统新模式改善看病效率

伴随着互联网时代的进步,医疗也在不断的发展,越来越多的医院和诊所开始使用医疗软件。医疗软件广泛的被使用着,软件几乎覆盖了我们的日常生活。在我们日常生活当中健康一直是需求专业渠道,医疗软件开发会把用户的数据打造出一个数…

2023年了,java后端还有未来吗?

前言 Java当下确实是比较的内卷,但关键在于个人,可以看看不同地方(这里主要举例北上广深一线城市)对于Java开发工程师这个职位的具体要求: 在以下北上广深这些一线大城市的面试招聘当中不难看出,凡是工资…