k-d树是二叉搜索树在k维空间中的扩展，其定义如下：一棵k-d树要么是空树，要么是一棵满足如下性质的二叉树：(1)每一个节点的数据域为k元有序组(N0,N1,N2,—,Nk-1)(2)每一层i上的每一个节点(数据域为(N0,N1,—,Nk-1))的左子树中每一个节点的数据域(N’0,N’1,—,N’k-1)满足N’ (i-1 mod k)<N (i-1 mod k),右子树中每一个节点的数据域(N

使用KMP算法匹配字符串的关键就是正确计算出next数组(不清楚何为模式匹配，何为KMP算法，什么是next数组可以自行百度或参考数据结构教科书)。next数组的计算是一大难点，殷人昆的数据结构教科书中对此问题的论述不够清晰，所列代码和说明部分关联性不强，看了让人似懂非懂。自己花了很长时间琢磨next数组计算的问题，现在总算从头到尾弄明白了，于是就在这里将自己的思考所得与大家分享。现有长为M的模式

基于±RMQ和欧拉序列的LCA算法的思路是构建树的欧拉序列,树上两个节点的LCA就是欧拉序列对应区间内深度最小的节点,且欧拉序列上相邻两项的深度值的差要么为1，要么为-1，所以LCA的查询可以用±RMQ做到.以下代码简单起见没有使用±RMQ±RMQ实现见。tarjan LCA算法讲解见。strToTree.h内容。

逐步插入回路法构造欧拉回路的算法介绍