数据结构 树
时间：2017-03-05 09:29:23
参考：
- 数据结构与算法分析（Java语言描述）第三版
- Merkle Patricia Tree (梅克尔帕特里夏树) 详解
二叉树概念#
-
二叉树：：每个节点的子节点数量都不多于两个。
-
二叉查找树（binary search tree）：对于二叉树中的任意一个节点，满足左子树的所有节点值小于当前节点，右子树的所有节点的值大于当前节点。
- 删除节点： 如果节点只有一个子节点，则用子节点替换当前节点。如果有两个子节点则用右子树的最小节点替换，然后删除右子树的最小节点。
-
带有平衡条件的二叉查找树 AVL：对于二叉查找树的每一个节点，满足左子树和有字数的高度差不大于
1。 -
伸展树（splay tree）
- 每个节点的儿子都不多于两个。
- 且左子节点的值小于父节点的值，右节点的值大于父节点的值。
- 当一个节点被访问之后，这个节点要经过一系列旋转变成根节点。
- 一字型：左右互换
- 之字形：双旋转
-
B树（B+树）
M阶B树： * 数据存储在树叶上。 * 非页节点存储M-1个关键字以指示搜索的方向；关键字i代表子树i+1中的最小的关键字。 * 树的根或者是一片树叶，或者其儿子数在2到M之间。 * 除根节点外，所有非树叶节点的儿子数在[M/2]到M之间。 * 所有的树叶都在相同的深度上并有[L/2]和[L]之间个数据项。L可以根据实际情况确定。
-
红黑树
- 每一个节点要么是红色，要么是黑色。
- 根是黑色的。
- 如果一个节点是红色，那么他的子节点必须是黑色的。
- 从一个节点到一个null引用的每一条路径必须包含相同数目的黑色节点。
-
优先级树
- 每个节点的儿子都不多于两个。
- 且左子节点的值小于父节点的值，右节点的值大于父节点的值。
- 任意节点的优先级至少要和父节点一样大。
-
前缀树（字典树）：用字母前缀构造树。
-
默克尔树：比特币中使用的数据结构，叶子节点存储数据，其余节点存储子节点的哈希。
-
线段树。用于固定长度数组求和，可以用数组实现（类似于二叉堆）。
树的应用#
B+ 树#
应用：MySQL B+ 树索引。
LSM树#
Log-Sturctured Merge Tree。 放弃部分读性能，优化写入性能。
应用：LevelDB。