区域四叉树数据结构

区域四叉树用于表示二维空间的划分，即将区域划分为四个相等的象限、子象限等，每个叶节点包含与特定子区域对应的数据。树中的每个节点要么与正好四个子节点关联，要么没有子节点（叶节点）。遵循这种分解策略（即细分子象限，直到子象限中存在需要进一步细化的有趣数据）的四叉树的高度，对空间中有趣区域的空间分布敏感并依赖于它。区域四叉树被认为是一种trie。

深度为n的区域四叉树可以用来表示一个由2n × 2n像素组成的图像，其中每个像素值要么是0要么是1。根节点用于表示整个图像区域。如果任何区域中的像素既不是全部为0也不是全部为1，则对其进行细分。在此应用中，每个叶节点用于表示全部为0或全部为1的像素块。请注意，当这些树用于存储图像时，在空间方面可能节省的潜力；这些图像通常具有许多相当大的区域，在整个区域中具有相同的颜色值。与其存储图像中每个像素的大的二维数组，不如使用四叉树，它能够以比我们原本需要的像素分辨率大小的单元大许多划分级别来捕获相同的信息。像素和图像大小能够绑定树的分辨率和整体大小。

区域四叉树也可以实现为数据字段的可变分辨率表示。例如，某个区域的温度可以存储为四叉树，每个叶节点存储其表示的子区域的平均温度。

如果实现区域四叉树来表示一组点数据（例如一组城市的纬度和经度），则对区域进行细分，直到每个叶节点最多包含一个点。

更新于：2020年1月8日

578 次浏览

启动你的职业生涯

完成课程获得认证

开始学习
广告