前言

\(KD-Tree\)是一个十分神奇的东西,其实本质上类似于一个\(K\)维的二叉搜索树

核心思想

\(KD-Tree\)的核心思想与\(BST\)是差不多的(插入等操作也都基本上一样)。

唯一的区别就在于,它每次比较的是某一维度上的值。

但是,与\(BST\)一样,\(KD-Tree\)也有可能会在某些情况下退化成一条链

怎么办呢?

呃,\(BST\)有平衡树,我们的\(KD-Tree\)有... ...

其实,我们可以采用替罪羊树的思想,对不平衡的子树直接重构

这样就能使复杂度较为稳定了。

\(KD-Tree\)有什么用?

呃,话说\(KD-Tree\)有什么用?

其实\(KD-Tree\)的主要应用如下:

所以,其实\(KD-Tree\)还是有很多用途的。

后记

\(KD-Tree\)的某些用法还是非常玄学的,强烈推荐去做一做文中提到的【BZOJ2648】SJY摆棋子一题,。

05-16 00:27