二叉搜索树，平衡树，B，b-，b+,b*,红黑树
二叉搜索树
1.所有非叶子结点至多拥有两个儿子（Left和Right）；
2.所有结点存储一个关键字；
3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；
如：
img
二叉树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；
否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入
右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；
如果二叉树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么二叉树
的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变二叉树结构
（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；
如：
img
但二叉树在经过多次插入与删除后，有可能导致不同的结构：
img
右边也是一个二叉树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的
树结构索引；所以，使用二叉树还要考虑尽可能让二叉树保持左图的结构，和避免右图的结构，也就
是所谓的“平衡”问题；
实际使用的二叉树都是在原二叉树的基础上加上平衡算法，即“平衡二叉树”；如何保持二叉树
结点分布均匀的平衡算法是平衡二叉树的关键；
平衡二叉树
AVL-自平衡二叉查找树
平衡二叉搜索树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。常用算法有红黑树、AVL、Treap、伸展树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O（log2n），大大降低了操作的时间复杂度。
调整平衡的基本思想：
当在二叉排序树中插入一个节点时，首先检查是否因插入而破坏了平衡，若破坏，则找出其中的最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡子树中节点之间的关系，以达到新的平衡。
所谓最小不平衡子树，指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。
先插入指定节点，记录下当前节点的信息，LH，EH或者RH。
\1. 若左子树高LH，查看其左子树根节点的信息，若是LH，则一次右旋；若是RH，则一次左旋+一次右旋
\2. 若右子树高RH，查看右子树根节点的信息，若是RH，则一次左旋；若是LH，则一次右旋+一次左旋
\3. 调整改变的节点信息
追求绝对的高度平衡，随着树的高度的增加，动态插入和删除的代价也随之增加。
具体旋转策略见http://blog.csdn.net/liyong199012/article/details/29219261
B树
1、根结点至少有两个子女；
2、每个非根节点所包含的关键字个数 j 满足：m/2 - 1 <= j <= m - 1；
3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：m/2<= k <= m ；
4、所有的叶子结点都位于同一层。
这里写图片描述
B-树
B-树
这里写图片描述
1、关键字集合分布在整棵树中；
2、任何一个关键字出现且只出现在一个结点中；
3、搜索有可能在非叶子结点结束；
4、其搜索性能等价于在关键字全集内做一次二分查找；
5、自动层次控制；
m阶B-树
- 树中每个结点至多有m个孩子；
- 除根结点和叶子结点外，其它每个结点至少有[m/2]个孩子；
- 若根结点不是叶子结点，则至少有2个孩子；
- 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；
- 每个非终端结点中包含有n个关键字信息： (n，A0，K1，A1，K2，A2，……，Kn，An)。其中，
a) Ki (i=1…n)为关键字，且关键字按顺序排序Ki < K(i-1)。
b) Ai为指向子树根的接点，且指针A(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。
c) 关键字的个数n必须满足： [m/2]-1 <= n <= m-1
建立
由于B~树结点中的关键字个数必须>=[m/2]-1。因此和平衡二叉树不同，每一次插入一个关键字并不是在树中添加一个结点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过m-1，则插入完成。否则，要产生结点的”分裂” 。
外存
我们现在把整棵树构造在磁盘中，假如每个盘块可以正好存放一个B~树的结点（正好存放2个文件名）。那么一个BTNode结点就代表一个盘块，而子树指针就是存放另外一个盘块 （详细见《外部存储器—磁盘 》）的地址。
现在我们模拟查找文件29的过程：
(1) 根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入内存。【磁盘IO操作1次】
(2) 此时内存中有两个文件名17，35和三个存储其他磁盘页面地址的数据。根据算法我们发现17<29<35，因此我们找到指针p2。
(3) 根据p2指针，我们定位到磁盘块3，并将其中的信息导入内存。【磁盘IO操作2次】
(4) 此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发现26<29<30，因此我们找到指针p2。
(5) 根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。【磁盘IO操作3次】
(6) 此时内存中有两个文件名28，29。根据算法我们查找到文件29，并定位了该文件内存的磁盘地址。
分析一下上面的过程，我们发现需要3次磁盘IO操作和3次内存查找操作。关于内存中的文件名查找，由于是一个有序表结构，可以利用折半查找提高效率。至于3次磁盘IO操作时影响整个B~树查找效率的决定因素。
当然，如果我们使用平衡二叉树的磁盘存储结构来进行查找，磁盘IO操作最少4次，最多5次。而且文件越多，B~树比平衡二叉树所用的磁盘IO操作次数将越少，效率也越高。
B+树
B+ 树是一种树数据结构，是一个n叉树，每个节点通常有多个孩子，一颗B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。
B+ 树通常用于数据库和操作系统的文件系统中。
NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系统都在使用B+树作为元数据索引。
B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。
B+ 树元素自底向上插入。
这里写图片描述
所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。(而B 树的叶子节点并没有包括全部需要查找的信息)
所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。(而B 树的非终节点也包含需要查找的有效信息)
1) 有n棵子树的结点中含有n个关键字； (B~树是n棵子树有n+1个关键字)
2) 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (B~树的叶子节点并没有包括全部需要查找的信息)
3) 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (B~树的非终节点也包含需要查找的有效信息)
B+树的有效内容均在叶子节点，B-树的有效内容不全在叶子节点上
B+树的头指针有两个，一个指向根节点，另一个指向关键字最小的元素，因此B+树有两种遍历的方式：
1.从根节点开始随机查询
2.从最小关键词顺序查询
B*树
这里写图片描述
在非根节点和叶子节点，增加了指向兄弟节点的指针。
B树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3
（代替B+树的1/2）；
B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据
复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父
结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分
数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字
（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之
间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；
所以，B*树分配新结点的概率比B+树要低，空间使用率更高；
红黑树
红黑树（Red Black Tree） 是一种自平衡二叉查找树
红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
二叉平衡树的严格平衡策略以牺牲建立查找结构(插入，删除操作)的代价，换来了稳定的O(logN) 的查找时间复杂度
它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。12345
RBT 的操作代价分析：
(1) 查找代价：由于红黑树的性质(最长路径长度不超过最短路径长度的2倍)，可以说明红黑树虽然不像AVL一样是严格平衡的，但平衡性能还是要比BST要好。其查找代价基本维持在O(logN)左右，但在最差情况下(最长路径是最短路径的2倍少1)，比AVL要略逊色一点。
(2) 插入代价：RBT插入结点时，需要旋转操作和变色操作。但由于只需要保证RBT基本平衡就可以了。因此插入结点最多只需要2次旋转，这一点和AVL的插入操作一样。虽然变色操作需要O(logN)，但是变色操作十分简单，代价很小。
(3) 删除代价：RBT的删除操作代价要比AVL要好的多，删除一个结点最多只需要3次旋转操作。
RBT 效率总结 : 查找 效率最好情况下时间复杂度为O(logN)，但在最坏情况下比AVL要差一些，但也远远好于BST。
插入和删除操作改变树的平衡性的概率要远远小于AVL（RBT不是高度平衡的）。因此需要的旋转操作的可能性要小，而且一旦需要旋转，插入一个结点最多只需要旋转2次，删除最多只需要旋转3次(小于AVL的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在O(logN)，但是实际上，这种操作由于简单所需要的代价很小。
红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。此外,任何不平衡都会在3次旋转之内解决。这一点是AVL所不具备的。
插入操作：
1.插入根节点（不需要操作）
2.父节点为黑色(不需要操作)
3.父节点和兄弟节点为红色，祖父节点为黑色，只需要变色，将祖父节点递归检查（原本检查自己）
4.父节点为红色，兄弟节点为黑色，祖父节点为红色，先两次旋转再调整颜色（左旋+右旋）12345
删除操作：
1.删除只有一个新的根节点（直接删除）
2.父节点为黑色，兄弟节点为红色（先旋转成左左，再删除）
3.父节点为黑色，兄弟节点为黑色（先将兄弟节点换成红色，变成情况2）
4.父节点为红色，自己和兄弟节点为黑色（将父节点变成黑色，兄弟节点变成红色，变成情况2）
5.兄弟节点为黑色，兄弟节点左子树根节点为红色（交换颜色，旋转成为左左）
6.情况2和情况5，调整性质5（将N删掉，用子节点顶替，若子节点为红色，则重绘为黑色）1234567
这里写图片描述
实现：http://www.cnblogs.com/skywang12345/p/3624343.html
应用
AVL树：平衡二叉树，一般是用平衡因子差值决定并通过旋转来实现，左右子树树高差不超过1，那么和红黑树比较它是严格的平衡二叉树，平衡条件非常严格（树高差只有1），只要插入或删除不满足上面的条件就要通过旋转来保持平衡。由于旋转是非常耗费时间的。我们可以推出AVL树适合用于插入删除次数比较少，但查找多的情况。
应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树。
红黑树：平衡二叉树，通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束，确保没有一条路径会比其他路径长2倍，因而是近似平衡的。所以相对于严格要求平衡的AVL树来说，它的旋转保持平衡次数较少。用于搜索时，插入删除次数多的情况下我们就用红黑树来取代AVL。
红黑树应用比较广泛：
· 广泛用在C++的STL中。map和set都是用红黑树实现的。
· 著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块。
· epoll在内核中的实现，用红黑树管理事件块
· nginx中，用红黑树管理timer等
· Java的TreeMap实现
B树，B+树：它们特点是一样的，是多路查找树，一般用于数据库中做索引，因为它们分支多层数少，因为磁盘IO是非常耗时的，而像大量数据存储在磁盘中所以我们要有效的减少磁盘IO次数避免磁盘频繁的查找。
B+树是B树的变种树，有n棵子树的节点中含有n个关键字，每个关键字不保存数据，只用来索引，数据都保存在叶子节点。是为文件系统而生的。
B+树相对B树磁盘读写代价更低：因为B+树非叶子结点只存储键值，单个节点占空间小，索引块能够存储更多的节点，从磁盘读索引时所需的索引块更少，所以索引查找时I/O次数较B-Tree索引少，效率更高。而且B+Tree在叶子节点存放的记录以链表的形式链接，范围查找或遍历效率更高。Mysql InnoDB用的就是B+Tree索引。
Trie树：
又名单词查找树，一种树形结构，常用来操作字符串。它是不同字符串的相同前缀只保存一份。
相对直接保存字符串肯定是节省空间的，但是它保存大量字符串时会很耗费内存（是内存）。
类似的有：前缀树(prefix tree)，后缀树(suffix tree)，radix tree(patricia tree, compactprefix tree)，crit-bit tree（解决耗费内存问题），以及前面说的double array trie。
前缀树：字符串快速检索，字符串排序，最长公共前缀，自动匹配前缀显示后缀。
后缀树：查找字符串s1在s2中，字符串s1在s2中出现的次数，字符串s1,s2最长公共部分，最长回文串。
trie 树的一个典型应用是前缀匹配，比如下面这个很常见的场景，在我们输入时，搜索引擎会给予提示。
img
还有比如IP选路，也是前缀匹配，一定程度会用到trie。
网友评论