数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究数据结构中的压缩四叉树和八叉树
压缩四叉树
在存储每个对应于细分单元的节点时，我们最终可能会存储大量空节点。通过仅存储其叶子具有有趣数据（即“重要子树”）的子树，可以减少此类稀疏树的大小。我们实际上可以进一步减少大小。当我们只考虑重要的子树时，修剪过程可能会避免树中的长路径，其中中间节点的度数为二（一个指向父节点的链接和一个指向子节点的链接）。事实证明，我们只需要存储此路径开始处的节点 U（并与其关联一些元数据以表示已删除的节点）并将以其结尾为根的子树附加到 U。当给定“不良”输入点时，这些压缩树仍然具有线性高度。
虽然我们在执行此压缩时减少了大量树，但仍然可以通过利用 Z 阶曲线来实现对数时间插入、删除和搜索。Z 阶曲线将完整四叉树（以及压缩四叉树）的每个单元在 O(1) 时间内转换为一维线（并在 O(1) 时间内将其转换回来），从而在元素上构建一个总顺序。现在，我们能够将四叉树存储在有序集的数据结构中（其中我们存储树的节点）。现在，我们必须在继续之前陈述一个合理的假设：我们假设给定两个表示为二进制的实数 α、β € [0,1]，我们可以在 O(1) 时间内计算出它们不同的第一个位的索引。我们还假设我们可以在 O(1) 时间内计算出四叉树中两个点/单元的最小公共祖先并确定它们的相对 Z 顺序，并且我们可以在 O(1) 时间内计算出 floor 函数。有了这些假设，给定点 Q 的点定位（即查找包含 Q 的单元格）、删除和插入操作都可以以 O(n log n) 时间执行（即在底层有序集数据结构中执行搜索所需的时间）。
要对 Q 执行点定位（即确定其在压缩树中的单元格）
- 在压缩树中找到在 Z 顺序中位于 Q 之前的现有单元格。将此单元格称为 V。
- 如果执行 Q€V，则返回 V。
- 否则，找到在未压缩四叉树中点 Q 和单元格 V 的最小公共祖先。将此祖先单元格称为 U。
- 在压缩树中找到在 Z 顺序中位于 U 之前的现有单元格并返回它。
在不深入具体细节的情况下，要执行插入和删除操作，我们首先对要插入/删除的内容执行点定位，然后插入/删除它。必须注意根据需要重塑树，根据需要构建和删除节点。
八叉树
八叉树定义为一种树形数据结构，其中每个内部节点都与恰好八个子节点相关联。
八叉树最常用于通过递归地将三维空间细分为八个卦限来对三维空间进行分区。
八叉树被视为四叉树的三维类似物。名称由 oct + tree 组成，但请注意，它通常写成“octree”，只有一个“t”。
八叉树通常在 3D 图形和 3D 游戏引擎中实现。
用于空间表示
八叉树中的每个节点负责将其表示的空间细分为八个卦限。在点区域 (PR)
八叉树中，节点存储一个显式三维点，它是该节点细分的“中心”；该点
为八个子节点中的每一个指定一个角。在基于矩阵 (MX) 的八叉树的情况下，细分点隐式地是节点表示的空间的中心。PR 八叉树的根节点能够表示无限空间；MX 八叉树的根节点必须能够表示有限的有界空间，以便隐式中心定义明确。
常见用途
- 3D 计算机图形中的细节层次渲染
- 空间索引
- 搜索最近邻
- 三维空间中有效的碰撞检测
- 有限元分析
- 稀疏体素八叉树
- 状态估计
- 集合估计
1K+ 阅读量
