本文用来整理二叉树的各种知识点

二叉树性质

性质1 一棵非空二叉树的第i层上最多有2i-1个结点(i≥1)。
性质2 若规定空树的深度为0，则深度为k的二叉树最多有2k-1个结点(k≥0)。
性质3 具有n个结点的完全二叉树的深度k为log2n+1。
性质4 对于一棵非空二叉树，如果度为0的结点数目为n0，度为2的结点数目为n2，则有n0= n2+1。
性质5 对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对所有结点从1开始编号，则对于序号为i的结点，有：
（1）如果i>1，则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)；如果i=1，则该结点是根结点，无双亲结点。
（2）如果2i≤n，则该结点的左孩子结点的序号为2i；若2i>n，则该结点无左孩子。
（3）如果2i+1≤n，则该结点的右孩子结点的序号为2i+1；若2i+1>n，则该结点无右孩子。
性质6 给定N个节点，能构成h(N)种不同的二叉树。
h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)

满二叉树(Full Binary Tree)

如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

深度为k的满二叉树的结点个数为2^k-1

完全二叉树(Complete Binary Tree)

深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k，有n个结点的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。

完全二叉树的特点是叶子结点只可能出现在层次最大的两层上，并且某个结点的左分支下子孙的最大层次与右分支下子孙的最大层次相等或大1。

完全二叉树是由满二叉树引出来的，因此满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

哈弗曼树

哈弗曼树可以设计出总长度最短的二进制前缀编码
其构造方法是不断的构造新节点，取出权值最小的节点作为树的两个节点，并将新节点的权值设为两个节点的权值之和
WPL = 求和 ( 叶节点的权值 * 该叶节点到根节点的距离 )
WPL为带权路径长度，也是最终编码得到二进制编码的长度

二叉查找树(Binary Search Tree)

二叉查找树,也称二叉搜索树、有序二叉树（英语：ordered binary tree），排序二叉树（英语：sorted binary tree）.

是指一棵空树或者具有下列性质的二叉树

任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
任意节点的左、右子树也分别为二叉查找树；
没有键值相等的节点。

删除时要注意，如果删除的节点有左右子树，那么用左子树的最右节点(推荐)或者右子树的最左节点取代该删除节点

二叉查找树的时间复杂度不是严格的log(N)，在最坏的情况下会出现“链表”的形式，复杂度退化到O(N)
因此有了AVL树(利用平衡因子), RB Tree红黑树(利用颜色), Treap(树和堆的结合)等来优化BST的最坏情况

References:
Binary_search_tree

AVL树

在AVL树中任何节点的两个子树的高度最大差别为一
查找、插入和删除在平均和最坏情况下都是O(log n)
增加和删除可能需要通过一次或多次树旋转来重新平衡这个树

节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来

References:
AVL_tree

红黑树Red-Black Tree

在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。

红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。
在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

节点是红色或黑色。
根是黑色。
所有叶子都是黑色（叶子是NIL节点）。
每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高.

详细内容请看红黑树

Treap

树和堆的合体，在树中维护一个”优先级”，”优先级”采用随机数的方法，但是”优先级”必须满足根堆的性质
插入原理与AVL相似

References:
树堆
 Treap

伸展树(Splay Tree)

能在O(log n)内完成插入、查找和删除操作。

在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。
于是想到设计一个简单方法，在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。
伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。

它的优势在于不需要记录用于平衡树的冗余信息。
伸展树最显著的缺点是它有可能会变成一条链。这种情况可能发生在以非降顺序访问n个元素之后。然而均摊的最坏情况是对数级的——O(log n)

References:
伸展树
 Splay_tree

多向平衡查找树：B-树和B+树

B-树
1.定义任意非叶子结点最多只有M个儿子；且M>2；
2.根结点的儿子数为[2, M]；
3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5.非叶子结点的关键字个数=指向儿子的指针个数-1；
6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8.所有叶子结点位于同一层；

B+树
B+树是B-树的变体，也是一种多路搜索树：
1.其定义基本与B-树同，除了：
2.非叶子结点的子树指针与关键字个数相同；
3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
5.为所有叶子结点增加一个链指针；
6.所有关键字都在叶子结点出现；

B+树是B树的变形，它把所有的附属数据都放在叶子结点中，只将关键字和子女指针保存于内结点，内结点完全是索引的功能

查找过程

假如每个盘块可以正好存放一个B树的结点（正好存放2个文件名）。那么一个BTNODE结点就代表一个盘块，而子树指针就是存放另外一个盘块的地址。
下面，咱们来模拟下查找文件29的过程：

根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入内存。【磁盘IO操作1次】
此时内存中有两个文件名17、35和三个存储其他磁盘页面地址的数据。根据算法我们发现：17<29<35，因此我们找到指针p2。
根据p2指针，我们定位到磁盘块3，并将其中的信息导入内存。【磁盘IO操作 2次】
此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发现：26<29<30，因此我们找到指针p2。
根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。【磁盘IO操作 3次】
此时内存中有两个文件名28，29。根据算法我们查找到文件名29，并定位了该文件内存的磁盘地址。分析上面的过程，发现需要3 3次磁盘IO操作和次磁盘IO操作和3次内存查找次内存查找操作。关于内存中的文件名查找，由于是一个有序表结构，可以利用折半查找提高效率。至于IO操作是影响整个B树查找效率的决定因素。

B+树还有一个最大的好处，方便扫库，B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了，B+树支持range-query非常方便，而B树不支持。这是数据库选用B+树的最主要原因。
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分之一，因此为了提高效率，要尽量减少磁盘I/O。
为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。
这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。

http://www.ruanyifeng.com/blog/2014/07/database_implementation.html
http://blog.csdn.net/l_griselda/article/details/8266014

字典树

通常用于查找字符串，比如在搜索框中搜索会自动提示，或者lucene
常用操作有插入和查找, 删除

代码

习题 208. Implement Trie (Prefix Tree)

public static class TrieNode {
	char val;
	TrieNode[] children;
	boolean leaf;
	// Initialize your data structure here.
	public TrieNode() {
		this.children = new TrieNode[26];
		leaf = false;
	}
	public TrieNode(char c) {
		this.val = c;
		children = new TrieNode[26];
		leaf = false;
	}
}
public static class Trie {
	private TrieNode root;
	public Trie() {
		root = new TrieNode();
	}
	// Inserts a word into the trie.
	public void insert(String word) {
		TrieNode cur = root;
		for (int i = 0; i < word.length(); i++) {
			int index = word.charAt(i) - 'a';
			TrieNode tmp = cur.children[index];
			if (tmp == null) {
				tmp = new TrieNode(word.charAt(i));
				cur.children[index] = tmp;
			}
			if (i == word.length() - 1) {
				tmp.leaf = true;
			}
			cur = tmp;
		}
	}
	// Returns if the word is in the trie.
	public boolean search(String word) {
		TrieNode cur = root;
		for (int i = 0; i < word.length(); i++) {
			int index = word.charAt(i) - 'a';
			TrieNode tmp = cur.children[index];
			if (tmp != null) {
				if (i == word.length() - 1 && tmp.leaf) {
					return true;
				}
				cur = tmp;
			} else {
				// 无此节点
				return false;
			}
		}
		return false;
	}
	// Returns if there is any word in the trie
	// that starts with the given prefix.
	public boolean startsWith(String prefix) {
		TrieNode cur = root;
		for (int i = 0; i < prefix.length(); i++) {
			int index = prefix.charAt(i) - 'a';
			TrieNode tmp = cur.children[index];
			if (tmp != null) {
				cur = tmp;
			} else {
				// 无此节点
				return false;
			}
		}
		//prefix是该字符串也可以
		return true;
	}
}
// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");

布隆过滤器

字典树是一种空间换时间的数据结构，子节点存储着每一个可能的值，所以可能节点个数非常多
而布隆过滤器是一个大数据场景下的替换字典树的数据结构
其原理是当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。
检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数（O(k)）。
另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。
另外，一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

上图中，m=18，k=3；插入x是，三个hash函数分别得到蓝线对应的三个值，并将对应的位向量改为1，插入y，z时，类似的，分别将红线，紫线对应的位向量改为1。查找时，当查找x时，三个hash值对应的位向量都为1，因此判断x在此数据集中。y，z也是如此。但是查找w时，w有个hash值对应的位向量为0，因此可以判断不在此集合中。但是，假如w的最后那个hash值比上图中的大1，这是就会认为w在此集合中，而事实上，w可能不在此集合中，因此可能出现误报。显然的，插入数据越多，1的位数越多，误报的概率越大。

https://zh.wikipedia.org/wiki/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8
http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html

后缀树

堆

堆肯定是一棵平衡二叉树(×)
因堆是二叉树，但不是二叉排序树，平衡二叉树是二叉排序树

二叉树及其相关

2017-03-10