面试数据结构问题总结

一、 平衡二叉树：除叶子节点外，任意节点的子树高度之差不超过1。

二、完全二叉树：除了最底下一层外，每层都是满节点，最底下一层节点是从左到右排列的。

三、二叉搜索树：左儿子val<父节点val<右儿子val

四、红黑树

红黑树有哪些性质？

1. 只有红色和黑色两种节点；

2. 根节点是黑色的；

3. 叶子节点是null节点并且是黑色的；

4. 红色节点的两个儿子都是黑色的；

5. 对于任意一个节点，它到其叶子节点的所有路径上有相同数量的黑节点；

由上面这些性质，可以推导出红黑树任意节点到以其为子树的叶子节点最长路径长度不超过最短路径长度的2倍。解释一下，为了使最长路径和最短路径差距尽可能大，我们不能增加黑色节点的数量，因为两条路径上的黑色节点数量应该是相同的，所以会同时增加，应该增加红色节点的数量，但是由于红色节点的儿子必须是黑色节点，因此最长路径之只能是红黑交替的，加之最短路径上的黑色节点数量是和最长路径上相同的，所以最长路径的长度不会超过最短路径长度的2倍。

2. 红黑树相比BST和AVL有哪些优势？

相比AVL的高度平衡，红黑树并不是高度平衡的，通过旋转，任何不平衡都可以在三次旋转之内解决，插入和删除这些动态操作维护起来比AVL容易，对于数据分布较好的情况可以使用AVL，如果数据分布比较随机那么用红黑树较好。

相比于BST可能退化成一条链，红黑树可以保证最长路径的长度不超过最短路径长度的2倍，最坏情况下仍是O(logn)的操作复杂度，而BST最坏情况下查找复杂度是O(N)的。

3. 什么时候用hash什么时候用map？

要根据查找速度、数据规模、内存使用和可扩展性几个方面去综合权衡。

总的来说哈希的速度要比map速度快，因为哈希是常数复杂度，而map是O(logn)的，但是hash更耗内存。如果数据都是静态的，不会动态的添加和删除，那么就构建一个hash表。如果数据是动态的，那么就用map。

通过统计以每个节点为根节点的子树中的节点个数，可以求某个数的秩和第k大的数。

五、空间划分树

1. 四叉树

主要用来管理二维平面上的点对象，首先整个平面作为四叉树的根节点，然后将平面分成四份，每份作为根节点的一个儿子，然后再对每个子平面做同样的划分。这种数据结构一般用来动态查询某个区域内包含哪些点对象，主要是用来剪枝的，比如说查询一个圆内包含哪些点，那么就从根节点开始，判断当前节点所表示的矩形区域是否在圆内，如果在，则区域内所有点都在，如果完全不在圆内，那么可以进行剪枝，不用再继续往下搜了，如果部分在，那么就继续往下搜他的子孙节点。

n个节点的四叉树每个节点都有四个指针，那么空指针的个数是3n+1个，首先n个节点，那么指针一共有4n个，除了根节点外，每个节点都有一个指针指向它，那么总共有n-1个指针不是空指针，剩下的都是空指针，也就是4n-(n-1)=3n+1个。

2. 八叉树

原理和四叉树是一样的，只不过它是用来管理三维区间的，也就是把一个立方体区域划分为8个子立方体，剩下的和四叉树一样。

3. kd树

k纬空间划分树，采用分治建树的思想，每一层遍历L~R的所有点，找出这些点在某一维上的最大距离差，然后就以每个点在这一维度上的坐标进行排序，其实不用完美的排序，只要保证找到排序后的中间点，然后把所有不大于它的点放到左边，所有不小于它的点放到右边，然后再对两边的数组进行同样的递归操作。这样最终可以得到一棵平衡二叉树。

查找的时候，如果是查距离某个点最近的k个点，先将这个点和当前区间的中间点求个距离，然后扔到优先队列里面，保证优先队列中只有k个元素，然后求这个点和中间点在当前划分维度（通过之前建树的时候所选取的中间点来记录划分维度）上的相对位置，如果小于就在左儿子找，如果大于就在右儿子找，另外还得求下查找点和中间点在划分维度上的距离，如果优先队列中的距离有比这个还大的，那就还得在另一个儿子中找，我是这样理解的，主要是因为如果当前优先队列里面维护的距离超过了它们在当前维度上的距离，那么就可以以查找点为圆心，以优先队列里那个距离为半径画个圆，这个圆和左右两个儿子表示的区间都有交集，所以两个儿子中的点都可能比优先队列中的更短，都得搜一下。

对于查找一个圆（或者球，这里就讨论这两种吧。。。）包含哪些点。。下面的解法是我自己YY的。。。

求圆心（或者球心）和中心点在当前划分维度上的距离，如果这个距离比半径小那就两个子区间都查询（因为和两个子区间都有交集），否则小于中心点只查左儿子，大于查右儿子。

注意上面这三种数据结构都是用来对动态查询进行剪枝的。。。不要想着复杂度能多优越。。。