查找算法
https://www.cnblogs.com/soul-stone/p/8051695.html
顺序/链表查找(无序)
二分查找(顺序表)
/**
* 递归方法实现二分查找
* @param data 已排序数组(这里假设是从小到大排序)
* @param from 起始位置
* @param to 终止位置
* @param target 要查找的值
* @return 要查找的值在数组中的位置，如果没找到则返回-1
*/
private static int binarySearch1(int[] data, int from, int to, int target) {
if (from <= to) {
int mid = from + (to - from) / 2;//中间位置，为了防止溢出使用这种方式求中间位置
if (data[mid] < target) {//中间的值比目标值小，则在左半边继续查找
return binarySearch1(data, mid + 1, to, target);
}else if(data[mid] > target){//中间的值比目标值大，则在右半边继续查找
return binarySearch1(data, from, mid - 1, target);
}else {//找到了，把找到的情况放在最后是因为多数情况下中间值不是大于就是小于，这样做可以节省操作
return mid;
}
}
return -1;
}
/**
* 非递归方法实现二分查找
* @param data 已排序数组(这里假设是从小到大排序)
* @param from 起始位置
* @param to 终止位置
* @param target 要查找的值
* @return 要查找的值在数组中的位置，如果没找到则返回-1
*/
private static int binarySearch2(int[] data, int from, int to, int target) {
while(from <= to) {
int mid = from + (to - from) / 2;
if (data[mid] < target) {
from = mid + 1;
}else if(data[mid] > target) {
to = mid - 1;
}else {//找到了，把找到的情况放在最后是因为多数情况下中间值不是大于就是小于，这样做可以节省操作
return mid;
}
}
return -1;
}
作者：JxYoung
链接：https://www.jianshu.com/p/b07c69a91535
插值查找
在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？
打个比方，在英文字典里面查“apple”，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。<
同样的，比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5， 我们自然会考虑从数组下标较小的开始查找。
经过以上分析，折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下：
mid=(low+high)/2, 即mid=low+1/2*(high-low);
通过类比，我们可以将查找的点改进为如下：
mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，
也就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。
基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。
注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。
复杂度分析：查找成功或者失败的时间复杂度均为O(log2(log2n))。
//插值查找
int InsertionSearch(int a[], int value, int low, int high)
{
int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
if(a[mid]==value)
return mid;
if(a[mid]>value)
return InsertionSearch(a, value, low, mid-1);
if(a[mid]<value)
return InsertionSearch(a, value, mid+1, high);
}
二叉树查找, 2-3树查找, 红黑树查找, B树, B+树查找
B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。
B+ 树的优点在于：
由于B+树在内部节点上不好含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。
B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。
分块查找
Hash表查找
单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)（注意，在查找之前我们需要构建相应的Hash表）。
树
AVL树，红黑树，B树，B+树，Trie树都分别应用在哪些现实场景中？
https://www.zhihu.com/question/30527705
从B树、B+树、B*树谈到R 树
http://blog.csdn.net/v_JULY_v/article/details/6530142/
B树、B-树、B+树、B*树 定义
https://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html
AVL树：
https://zh.wikipedia.org/wiki/AVL%E6%A0%91
特点
在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的o(n)复杂度。
旋转
以下图表以四列表示四种情况，每行表示在该种情况下要进行的操作。在左左和右右的情况下，只需要进行一次旋转操作；在左右和右左的情况下，需要进行两次旋转操作。
image.png
点数计算
image.png
伸展树Splay：
https://blog.csdn.net/u014634338/article/details/49586689
http://www.cnblogs.com/skywang12345/p/3604286.html
https://www.cnblogs.com/kuangbin/archive/2012/10/07/2714068.html
背景和特点
考虑到局部性原理（刚被访问的内容下次可能仍会被访问，查找次数多的内容可能下一次会被访问），为了使整个查找时间更小，被查频率高的那些节点应当经常处于靠近树根的位置。这样，很容易得想到以下这个方案：每次查找节点之后对树进行重构，把被查找的节点搬移到树根，这种自调整形式的二叉查找树就是伸展树。每次对伸展树进行操作后，它均会通过旋转的方法把被访问节点旋转到树根的位置。
特点是不会保证树一直是平衡的，被访问节点旋转到树根，我们通常将节点自底向上旋转，直至该节点成为树根为止。“旋转”的巧妙之处就是在不打乱数列中数据大小关系（指中序遍历结果是全序的）情况下，所有基本操作的平摊复杂度仍为O（log n）
旋转思路参考
https://blog.csdn.net/u014634338/article/details/49586689
效率对比
伸展树(splay tree)，它对于m次连续搜索操作有很好的效率。伸展树会在一次搜索后，对树进行一些特殊的操作。这些操作的理念与AVL树有些类似，即通过旋转，来改变树节点的分布，并减小树的深度。但伸展树并没有AVL的平衡要求，任意节点的左右子树可以相差任意深度。与二叉搜索树类似，伸展树的单次搜索也可能需要n次操作。但伸展树可以保证，m次的连续搜索操作的复杂度为mlog(n)的量级，而不是mn量级。
https://www.cnblogs.com/wxgblogs/p/5506234.html
- 优势
可靠的性能——它的平均效率不输于其他[平衡树]
存储所需的内存少——伸展树无需记录额外的什么值来维护树的信息，相对于其他平衡树，内存占用要小。
由于Splay Tree仅仅是不断调整，并没有引入额外的标记，因而树结构与标准红黑树没有任何不同，从空间角度来看，它比Treap、SBT、AVL要高效得多。因为结构不变，因此只要是通过左旋和右旋进行的操作对Splay Tree性质都没有丝毫影响，因而它也提供了BST中最丰富的功能，包括快速的拆分和合并，并且实现极为便捷。这一点是其它结构较难实现的。其时间效率也相当稳定，和Treap基本相当，常数较高。 - 缺点
伸展树最显著的缺点是它有可能会变成一条。这种情况可能发生在以非降顺序访问n个元素之后。然而均摊的最坏情况是对数级的——O(logn)
treap树
https://blog.csdn.net/chen_tr/article/details/50924073
https://blog.csdn.net/u014634338/article/details/49612159
https://blog.csdn.net/yang_yulei/article/details/46005845
特点和背景
Treap，顾名思义就是Tree+Heap。这么命名的原因就是它使用了二叉堆的性质来保持二叉树的平衡。
我们知道，一个二叉（大根）堆满足这样的性质：一个节点的两个儿子的值都小于节点本身的值。如果一个二叉查找树满足这样的性质，那么它就被称作Treap。 Treap并不是二叉堆，二叉堆必须是完全二叉树，而Treap可以并不一定是。
但是等等，这样的设定似乎和二叉查找树矛盾啊。一个要求节点值小于右儿子的值，一个要求节点值大于右儿子的值，这显然是不可能做到的。
只有一种方法能够解决，就是让每个节点有2个值，其中一个满足二叉查找树的性质，一个满足大根堆的性质。为方便起见，下面把满足二叉查找树性质的值称作key，把满足大根堆性质的值称作prio（priority的简称）。
每个节点的key我们是无法改变了，为了保证Treap的平衡性，我们需要在prio上做一点文章。其实也没有什么复杂的，就是让每个节点的prio都取一个随机值，这样我们就可以保证这棵树“基本平衡”。
旋转
分类：左旋转和右旋转
方法：一般先按照二叉查找方法，找到对应节点的位置，随机选取一个prio值，如果此时不满足堆得特性，那么就进行旋转
SBTree树
http://www.cnblogs.com/gtarcoder/p/4724288.html
https://blog.csdn.net/murmured/article/details/17029131
https://www.cnblogs.com/zgmf_x20a/archive/2008/11/14/1333205.html
特点
Size Balanced Tree(SBT)是目前速度最快的平衡二叉搜索树，且能够进行多种搜索操作，区间操作；和AVL、红黑树、伸展树、Treap类似，SBT也是通过对节点的旋转来维持树的平衡，而相比其他平衡树，SBT维持平衡所需要的额外数据很少，只需要维持以当前节点为根的子树的大小；且SBT的编写复杂度低。因此具有空间优势、速度优势、编写优势。
RBTree 红黑树
http://www.cnblogs.com/Lynn-Zhang/p/5653943.html
https://tech.meituan.com/redblack-tree.html
https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md
http://www.cnblogs.com/skywang12345/p/3245399.html
特点
黑树的查找、插入、删除的时间复杂度最坏为O(log n)
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。
image.png
旋转和着色变换
基本操作是左旋转和右旋转。
http://www.cnblogs.com/Lynn-Zhang/p/5653943.html
算法复杂度证明
- 证明：一棵有 n 个内部节点的红黑树的高度至多为 2lg(n+1)
- 最长路径至多是最短路径的两倍
- 内部节点最多，内部节点最少
参考：https://blog.csdn.net/lanchunhui/article/details/75905478
B+树 R树
AVL树，红黑树，B树，B+树，Trie树都分别应用在哪些现实场景中？
https://www.zhihu.com/question/30527705
从B树、B+树、B树谈到R 树
http://blog.csdn.net/v_JULY_v/article/details/6530142/
B树、B-树、B+树、B树 定义
https://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html
区间树
二叉堆
大根堆，小根堆
Trie树
前缀树，后缀树
网友评论