二叉树进阶：二叉搜索树、平衡二叉树、KD树（实现KNN算法的快速寻找k个邻居）

二叉搜索树又称为二叉排序树、二叉查找树。请记住，本篇所介绍的所有树，都是二叉搜索树，也就是说都用到了二分查找的思想。

• 二叉搜索树的特征：每个结点的左结点都小于结点本身，右结点都大于结点本身。用中序遍历来遍历一棵二叉搜索树，结果必然是有序的。
• 时间复杂度很低
  查找元素：二分查找，O(logN）。当树形状退化为链表时，时间复杂度增加到O(N)
  增加元素：二分查找，直到找到一个位置时空，O（logN）。同样受到树的形状影响。
  删除元素：
  1. 删除叶子节点：找到并删除即可
  2. 删除只有左子树或者右子树的结点：直接把子树放到被删除节点的原本位置
  3. 删除既有左子树又有右子树的结点：先删除左子树的最大值或者右子树的最小值，并放到原本要被删除节点的位置

平衡二叉树（AVL）

定义：左子树的高度和右子树的高度的差不超过1的二叉查找树
作用：避免退化为链表
原理：对于每个新加入的结点计算平衡因子：左子树高度减右子树高度。平衡因子只可以是-1、0或1，否则会需要旋转调整。旋转的作用是调整树的形状，让树变得平衡。
具体旋转操作：分为左旋和右旋，旋转前后的中序遍历结果相同（等价，只有树高度变化）。旋转的具体过程较为复杂，不便演示，可以去网上寻找动画资料学习。这里给出一个网址链接：平衡二叉树(AVL树)

KD树

简介：所谓KD树，其实就是数据特征有K维的平衡二叉树。我们都知道二叉搜索树的一个特点是查找速度快，但是只有当节点数据是一维数据的时候二叉搜索树才可以进行查找。如果将数据规模扩展到多维的时候，我们就需要KD树（k-dimension）来帮助我们实现快速查找了。KD树的本质是多维下的二分查找，依次对每一维都采用二分查找的方式，试图去找到一个总体来说距离较近的点。

典型用途：在实现KNN算法时，我们会需要找到与某个点距离最近的N个点，通常我们的样本特征维度都会大于1，此时就可以使用KD树算法。当数据维度不超过20时，KD树的效率会显著高于暴力搜索。

以2D树为例（这是我自己取的名字）：如果我们的数据是二维的，在一个平面上，我们的数据以点状分布，此时使用2D树，可以快速找到与我们相邻最近的N个点。

• 用已有的训练数据构建KD树：对于我们已经有的数据，我们首先要构建一棵KD树。
  

  • 步骤一：如图所示，二维平面上有数个点，每个点有2个维度的特征。我们的做法是先确定一个坐标轴（例：x轴），根据对应的坐标（x坐标），在所有数据中找到一个中位点a(\(x_{0}\),\(y_{0}\))（图中为a（6.5,5）），利用其所在的垂直于该轴的直线x=\(x_{0}\)(图中为x=6.5）将平面划分为两块P左和P右。如果在多维空间中，这将会是一个超平面。这样，我们的数据就依据x坐标值被分为了两部分，即x小于\(x_{0}\)的数据点和x大于\(x_{0}\)的数据点。这个数据点a会被作为KD树的根结点。每个结点，需要保存四个信息：这个样本的特征向量、左节点、右节点以及它是依据哪个维度被选择为中位点的。x小于\(x_{0}\)的数据点被放入a点的左子树中，但是暂时没有进行构建。同理，x大于\(x_{0}\)的数据点被放入a点的右子树中。
  • 步骤二：选择样本数据的第二个特征维度，对于每个被分出来的块P左和P右，我们依据这个维度再一次进行划分。对于这个二维例子，就是依据y坐标的值进行划分。同样，我们可以把每个划分区域再次一分为二。
  • 步骤三：重复第二个步骤，不断遍历所有的特征维度，以此作为我们寻找中位数据的依据，直到每个块中只有不超过一个的数据点时，我么的2D树就构建好了。

• 搜索KD树

1. 寻找最近邻的点
   以KNN为例，如果我们想要找到最近的K个邻居点（KNN算法具体流程暂不讨论），我们可以先准备好一个容量为k的列表，用来保存最近的k个邻居。然后从根节点开始，依次将当前节点切分维度的特征值与目标样本相同维度的特征值进行比较。例如：对于根节点，切分维度为第一个维度，即x值。如果目标点为s(1,8)，显然s的x坐标1小于根节点的x坐标6.5，所以我们可以进入到x=6.5这条直线的左侧继续进行下一轮寻找。
   第二轮，我们找到根节点的左孩子结点，此时我们应该按照第二个维度进行比较了，因为这个节点的切分维度为y轴。显然 \(y_{s}\)=8要大于第二个结点（在坐标轴上即为位于切分线上的点）的y坐标-3，所以我们从y=-3这条切分线上方继续去寻找，重复这个过程，直至找到一个叶子节点，即某一块中只有一个数据位置。这个数据，我们就放入k列表中，作为找到的第一个邻居（临时）。同时，我们标记这个点为已经访问过。
2. 进行回溯
   回溯过程又有一大堆可以写，分到下一篇再补充了