数据结构——KD树

这篇具有很好参考价值的文章主要介绍了数据结构——KD树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

KD树(K-Dimensional Tree)是一种用于多维空间的二叉树数据结构,旨在提供高效的数据检索。KD树在空间搜索和最近邻搜索等问题中特别有用,允许在高维空间中有效地搜索数据点。
重要性质
1.分割K维数据空间的数据结构
2.是一颗二叉树
3.切分维度上,左子树值小于右子树值
kd树构建,数据结构,数据结构
kd树构建,数据结构,数据结构
kd树构建,数据结构,数据结构
kd树构建,数据结构,数据结构
kd树构建,数据结构,数据结构文章来源地址https://www.toymoban.com/news/detail-732093.html

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

// 定义二维点的结构体
struct Point2D {
    double x;
    double y;
    Point2D(double _x, double _y) : x(_x), y(_y) {}
};

// 定义KD树节点
struct KDTreeNode {
    Point2D point;
    KDTreeNode* left;
    KDTreeNode* right;

    KDTreeNode(Point2D _point) : point(_point), left(nullptr), right(nullptr) {}
};

class KDTree {
private:
    KDTreeNode* root;

    // 构建KD树的递归函数
    KDTreeNode* buildKDTree(std::vector<Point2D>& points, int depth) {
        if (points.empty()) {
            return nullptr;
        }

        // 选择轴线,交替选择x和y坐标
        int axis = depth % 2;

        // 按轴线排序点
        if (axis == 0) {
            std::sort(points.begin(), points.end(), [](const Point2D& a, const Point2D& b) {
                return a.x < b.x;
            });
        } else {
            std::sort(points.begin(), points.end(), [](const Point2D& a, const Point2D& b) {
                return a.y < b.y;
            });
        }

        // 选择中间点作为节点
        int median = points.size() / 2;
        KDTreeNode* node = new KDTreeNode(points[median]);

        // 递归构建左子树和右子树
        std::vector<Point2D> leftPoints(points.begin(), points.begin() + median);
        std::vector<Point2D> rightPoints(points.begin() + median + 1, points.end());

        node->left = buildKDTree(leftPoints, depth + 1);
        node->right = buildKDTree(rightPoints, depth + 1);

        return node;
    }

    // 在KD树中查找最近邻点的递归函数
    KDTreeNode* findNearestNeighbor(KDTreeNode* node, Point2D target, int depth, KDTreeNode* best, double& bestDistance) {
        if (node == nullptr) {
            return best;
        }

        // 计算当前节点到目标点的距离
        double currentDistance = distance(node->point, target);

        // 更新最近邻点和距离
        if (currentDistance < bestDistance) {
            best = node;
            bestDistance = currentDistance;
        }

        // 选择子树
        int axis = depth % 2;
        KDTreeNode* nearSubtree;
        KDTreeNode* farSubtree;
        if (axis == 0) {
            if (target.x < node->point.x) {
                nearSubtree = node->left;
                farSubtree = node->right;
            } else {
                nearSubtree = node->right;
                farSubtree = node->left;
            }
        } else {
            if (target.y < node->point.y) {
                nearSubtree = node->left;
                farSubtree = node->right;
            } else {
                nearSubtree = node->right;
                farSubtree = node->left;
            }
        }

        // 递归搜索更近的子树
        best = findNearestNeighbor(nearSubtree, target, depth + 1, best, bestDistance);

        // 如果可能,搜索更远的子树
        if (shouldSearchFarSubtree(node, target, bestDistance)) {
            best = findNearestNeighbor(farSubtree, target, depth + 1, best, bestDistance);
        }

        return best;
    }

    // 计算两点之间的欧几里得距离
    double distance(Point2D a, Point2D b) {
        double dx = a.x - b.x;
        double dy = a.y - b.y;
        return std::sqrt(dx * dx + dy * dy);
    }

    // 检查是否需要搜索更远的子树
    bool shouldSearchFarSubtree(KDTreeNode* node, Point2D target, double bestDistance) {
        int axis = node->point.x > target.x ? 0 : 1; // 如果轴线是x,则比较x坐标;如果轴线是y,则比较y坐标
        double nodeDistance = axis == 0 ? node->point.x - target.x : node->point.y - target.y;
        return nodeDistance * nodeDistance < bestDistance;
    }

public:
    KDTree(std::vector<Point2D>& points) {
        root = buildKDTree(points, 0);
    }

    // 查找最近邻点
    Point2D findNearestNeighbor(Point2D target) {
        double bestDistance = std::numeric_limits<double>::max();
        KDTreeNode* bestNode = findNearestNeighbor(root, target, 0, nullptr, bestDistance);
        return bestNode->point;
    }
};

int main() {
    // 创建一些二维点
    std::vector<Point2D> points = {
        {2.0, 3.0},
        {5.0, 4.0},
        {9.0, 6.0},
        {4.0, 7.0},
        {8.0, 1.0},
        {7.0, 2.0}
    };

    // 构建KD树
    KDTree kdTree(points);

    // 查找最近邻点
    Point2D target(9.0, 2.0);
    Point2D nearestNeighbor = kdTree.findNearestNeighbor(target);

    std::cout << "The nearest neighbor to (" << target.x << ", " << target.y << ") is (" << nearestNeighbor.x << ", " << nearestNeighbor.y << ")" << std::endl;

    return 0;
}

到了这里,关于数据结构——KD树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 八叉树(Octree)和KD树区别?2d tree与3d tree区别?

    八叉树(Octree) 结构 :八叉树是一种用于三维空间数据的树状结构,每个分支节点恰好有八个子节点。每个节点代表空间中的一个立方体区域,这个立方体区域被均匀地分割成八个小立方体。 用途 :八叉树常用于计算机图形学中,比如体素渲染、碰撞检测、空间查询等。

    2024年02月19日
    浏览(46)
  • 伯俊ERP与金蝶云星空对接集成表头表体组合查询连通分布式调出单新增(调拨出库对接分布式调出(KD调拨)6月)

    伯俊科技,依托在企业信息化建设方面的领先技术与实践积累,致力于帮助企业实现全渠道一盘货。伯俊提供数字经营的咨询与系统实施,助力企业信息化升级、加速数字化转型,覆盖零售市场中时尚鞋服、母婴内衣、珠宝饰品、食品酒水等多个行业,为5000+家机构及企业提

    2024年02月09日
    浏览(37)
  • (FEDCVAE-KD)DATA-FREE ONE-SHOT FEDERATED LEARNING UNDER VERY HIGH STATISTICAL HETEROGENEITY论文笔记

    出于对扩展通信和潜在攻击的担忧,一次性FL将通信限制在单一回合,同时试图保持性能。 然而,一次性FL方法在高统计异质性的情况下往往会退化,无法提高管道的安全性,或者需要一个辅助的公共数据集。 为了解决这些局限性,我们提出了两种新的无数据的一次性FL方法

    2024年02月04日
    浏览(43)
  • 【紫光同创盘古PGX-MINI-4K教程】——(盘古PGX-MINI-4K开发板/PGC4KD-6ILPG144第三章)​键控彩灯实验例程

    本原创教程由深圳市小眼睛科技有限公司创作,版权归本公司所有,如需转载,需授权并注明出处(www.meyesemi.com) 适用于板卡型号: 紫光同创PGC4KD-6ILPG144开发平台(盘古PGX-MINI-4K) 仅需一根TypcC线,插上即用,轻松操作。兼容下载器的一体版,配套资料丰富, 快速掌握国产

    2024年03月12日
    浏览(83)
  • 【紫光同创盘古PGX-Lite 7K教程】——(盘古PGX-Lite 7K开发板/PGC7KD-6IMBG256第七章)数字钟实验例程

    本原创教程由深圳市小眼睛科技有限公司创作,版权归本公司所有,如需转载,需授权并注明出处(www.meyesemi.com) 适用于板卡型号: 紫光同创PGC7KD-6IMBG256开发平台(盘古PGX-Lite 7K) 仅需一根TypcC线,插上即用,轻松操作。兼容下载器的一体版,配套资料丰富, 快速掌握国产

    2024年04月28日
    浏览(39)
  • 05-使用结构体构建相关数据

    上一篇: 04-了解所有权         结构体(struct)是一种自定义数据类型,可以将多个相关值打包命名,组成一个有意义的组。如果你熟悉面向对象的语言,那么结构体就像是对象的数据属性。在本章中,我们将对元组和结构体进行对比,在已有知识的基础上说明结构体是

    2024年01月24日
    浏览(31)
  • 【数据结构之二叉树的构建和遍历】

    前言: 前篇学习了 数据结构之树和二叉树的基本概念知识,那么这篇继续完善二叉树的相关知识并完成实现二叉树的构建和遍历的内容。 / 知识点汇总 / 因为前篇已经非常详细的单独学习了数和二叉树的基本知识概念,那么这里就简单回顾一下即可。 概念 : 二叉树(Bina

    2024年02月21日
    浏览(47)
  • 【数据结构】二叉树的构建与基本操作实现

    👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.前序建立二叉树 2.销毁二叉树 3.统计 4.查找值为x的节点 5.前中后序遍历 6.层序遍历 7.判断二叉树是否

    2024年02月07日
    浏览(45)
  • 数据结构:三元组的构建、相加和快速转置

    目录 1.三元组表的定义 2.三元组表的数据结构 3.三元组表的构建 4.输出三元组表 5.两个三元组表相加  代码的流程图​  实现代码 6.三元组表的快速转置  算法思想  代码实现 7.三元组表输出矩阵 8.全部代码 9.总结         三元组研究目的 对于在实际问题中出现的大型的

    2024年02月02日
    浏览(37)
  • 13.JavaWeb & XML:构建结构化数据的重要工具

    目录 导语: 一、XML概念 (1)可拓展 (2)功能-存储数据 (3)xml与html的区别 二、XML内容 三、XML用途 四、案例:使用XML构建在线书店的书籍数据库 结语:     在当今的信息时代,数据结构化和管理成为了一个重要课题。XML(eXtensible Markup Language,可扩展标记语言)作为一

    2024年04月09日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包