DataStructure--Tree

1.Tree–Basic

参考链接

2.Binary Tree

参考链接
二叉树是有序树。

简单地理解，满足以下两个条件的树就是二叉树：
1. 本身是有序树；
2. 树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；
1
2
3

2.1 满二叉树

如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树

2.2 完全二叉树

如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。

2.3 Binary Tree–Implementation

2.3.1 顺序存储结构

利用数组实现。

2.3.2 链式存储结构

利用链表实现。

2.4 Binary Tree–Traversal

遍历有两种实现方式
1.递归
2.利用栈模拟递归思想实现

2.4.1 Preorder Traversal

参考链接

2.4.1.1 概念

	先序遍历得到的序列为：
	1 2 4 5 3 6 7
1
2

2.4.1.2 实现–递归

```c
void PreOrderTraverse(Tree * t)
{
	if(t == NULL)
		return;
	
	printf("%c",t->data);
	PreOrderTraverse(t->lchild);
	PreOrderTraverse(t->rchild);
}
```
1
2
3
4
5
6
7
8
9
10
11

2.4.1.3 实现–栈

2.4.2 Inorder Traversal

参考链接

2.4.2.1 概念

	中序遍历得到的序列为：
	4 2 5 1 6 3 7
1
2

2.4.2.2 实现–递归

void InOrderTraverse(Tree * t)
{
	if(t == NULL)
		return;
	
	InOrderTraverse(t->lchild);
	printf("%c",t->data);
	InOrderTraverse(t->rchild);
}
1
2
3
4
5
6
7
8
9

2.4.2.3 实现–栈

2.4.3 Postorder Traversal

参考链接

2.4.3.1 概念

	后序遍历的结果为：
	4 5 2 6 7 3 1
1
2

2.4.3.2 实现–递归

```c
void PostOrderTraverse(Tree * t)
{
	if(t == NULL)
		return;
	
	PostOrderTraverse(t->lchild);
	PostOrderTraverse(t->rchild);
	printf("%c",t->data);
}
```
1
2
3
4
5
6
7
8
9
10
11

2.4.3.3 实现–栈

2.4.4 Hierarchical Traversal

2.4.4.1 概念

	层次遍历结果为：
	1 2 3 4 5 6 7
1
2

2.4.4.2 利用队列实现

参考链接

3. Binary Search Tree

3.1 概念

参考资料

又称 二叉排序树（Binary Sort Tree）。

二叉搜索树的基本性质：满足二叉树性质的同时，左子树<=根<=右子树，
平均查找时间复杂度为 O(log(n))。

最好情况下的算法时间复杂度为O(1)，最坏情况下的算法时间复杂度为O(n)。

BST 是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

针对优化查找效率衍生出众多 自平衡二叉查找树。
其中包括：

··Size Balanced Tree，节点大小平衡树（Size Balanced Tree），简称SBT。 2007
··高度平衡树，简称 AVL树。 		1962
··红黑树（Red Black Tree）。	1978
1
2
3

以上所有自平衡二叉树 都会利用旋转 保持自身平衡。

3.2 实现

实现一般包括插入删除。
插入的算法有两种（类似前序遍历的思想）：
1. 递归
2. 利用栈。
1
2
3
4

参考资料

4. Size Balanced Tree

4.1 概念

参考资料
参考资料

Size Balanced Tree（SBT）是一种通过大小（Size）域来保持平衡的二叉搜索树，它也因此得名。
相比红黑树、AVL树等自平衡二叉查找树，SBT更易于实现。

Size的概念：对于树上某个节点而言，它的Size指的是以它为树根的子树当中节点的数量。
SBT的平衡条件：对于SBT的每个节点，每棵子树的 Size 大小不小于其兄弟的子树 Size 大小。
1
2

性质：
它总是满足：

4.2 保证自平衡方法–旋转调整

旋转的命名参考资料
旋转分别为 左旋 (RR型) 和 右旋 (LL型)，两者过程是相反的。
如下图示例针对 x 的左旋和右旋。

至于 LR型（先左旋后右旋）和 RL型（先右后左），不需要再写额外的代码，只需要调用两次 左旋转或者右旋转。

假设A节点需要进行LR型的旋转，则只需A.left = 左旋转一次，再A= 右旋转一次。
假设B节点需要进行RL型的旋转，则只需B.right = 右旋转一次，再B = 左旋转一次。
1
2

4.3 何时触发自平衡调整

只有在添加节点时才会出现平衡调整，因为删除后调整平衡与不调整平衡，都不影响后续的操作。
为了达到优化，在delete中，不进行平衡性的调整。而是把平衡性的调整，放在了add方法里。

Maintain方法，就是SBT树，最核心的地方。

触发旋转的条件是：

T1的size > 二叔的size	LL型
T2的size > 二叔的size	LR型
T3的size > 大叔的size	RL型
T4的size > 大叔的size	RR型
1
2
3
4

旋转操作之后，还需要递归调用Maintain方法。
递归调用的对象，就是：

哪个节点的子树被换了，则需要调用这个Maintain（新子树）；
举个例子：
		原先A节点的右子树是T2，旋转操作之后，A节点的右子树变为了T3，
	那么就需要递归调用Maintain（T3）。
1
2
3
4

4.4 删除节点

为了达到优化，在delete中，不进行平衡性的调整。而是把平衡性的调整，放在了add方法里。
特别需要注意的是：
就是被删除节点的左右子树都不为null时，需要找一个节点来替换当前被删除的节点。一般都是在被删除节点的右子树上，查找最小（最左）的节点进行替换。这一点，也是搜索二叉树的删除操作，最容易出错的一个点，值得重点关注。

4.5 实现

mygitee

5.Balanced Binary Tree（BBT，简称 AVL 树）

参考链接

5.1 概念

AVL树本质上是一颗二叉查找树，但是它又具有以下特点：

1.它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，
2.左右两个子树 也都是一棵平衡二叉树。
1
2

平衡因子（Balance Factor，简写为bf）：结点的 左子树的深度 减去 右子树的深度。

 结点的平衡因子 = 左子树的高度 - 右子树的高度 
1

在 AVL树中，所有节点的平衡因子都必须满足： -1<=bf<=1;

5.2 保证自平衡方法–旋转调整

和上面 BST 性质差不多，都分为左旋（RR型）和右旋（LL型）。
左旋和右旋都针对的是 哪个节点发现了不平衡，就以哪个节点进行旋转。

5.2.1 LL插入–右旋

如上图，此时添加为 LL 型，T发现不平衡，故需以 T 右旋调整：

5.2.2 RR插入–左旋

如上图，此时添加为 RR 型，T发现不平衡，故需以 T 左旋调整：

5.2.3 LR插入–先左旋再右旋

LR 插入，需要进行两次调整：

5.2.4 RL插入–先右旋再左旋

5.2.5 总结

故由上可知，根据插入节点的位置，触发某种平衡调整：

5.3 实现

5.3.1 分析–插入

插入最重要的是怎样更新 bf，以及何时触发旋转。

插入是一个迭代的过程，每次更新 bf 的值要从插入位置开始向上迭代。因为只有插入位置的 bf 值 是知道的，其他节点的 bf 值在插入后都要变化。

插入分两种：
1.向左子树插入temp
可能的情况有如下图 4 种：

是否触发旋转，要根据各个节点（ a x z ）的 bf 值来判断决定。

1 可能触发 x 的 右旋（LL）。
2 可能触发 双旋（RL），x 先右旋（LL），z 再左旋（RL）。
3 可能触发 双旋（RL），A 先右旋（LL），x 再左旋（RL）。
4 可能触发 双旋（RL），A 先右旋（LL），x 再左旋（RL）。
1
2
3
4

2.向右子树插入temp

是否触发旋转，要根据各个节点（ a x z ）的 bf 值来判断决定。

1 可能触发 z 的右旋（LL）。
2 可能触发 双旋（LR），先对 A 左旋（RR），再对 x 右旋（LL）。
3 可能触发 x 的左旋（RR）
	也可能触发 z 的左旋（RR）
4 可能触发 x 的左旋（RR）
	也可能触发 双旋（RL），先对 x 左旋（RR），再对 z 右旋（LL）。 
1
2
3
4
5
6

总结：

当插入节点在某颗树的 右子树 时，只会发生 左旋（RR） 或 双旋（RL）。
当插入节点在某颗树的 左子树 时，只会发生 右旋（LL） 或 双旋（LR）。
	
故可以根据，这个性质去写代码。
1
2
3
4

5.3.2 实例–插入

以先序插入：
70,90,50,40,60,55,45,48,49,75,57
实际插入流程如下：

每次插入都要向上遍历，遍历包含更新 bf 以及 根据 父节点 bf 的值调整子树平衡。

分析，这里只举一个例子，详细的拿着代码看。
示例1，如上图 add 48

	add 48后，首先更新父节点45 bf = -1，
	上例中 原始父父节点40 bf = -1，故此次添加是RR型，应左旋调整。
	延伸：
		若 父父节点40 bf = 0，则 更新父父节点40 bf = -1，此时这颗子树满足平衡，无需调整。
		若 父父节点40 bf = 1，则更新父父节点40 bf = 0，此时这颗子树满足平衡，无需调整。
1
2
3
4
5

5.3.3 分析–删除

删除，最重要的删除后如何触发旋转调整。
前提：
	无论  BST(二叉搜索树)， SBT（域二叉树） 还是 BBT（平衡二叉树），
	删除节点都是拿 右子树最小节点（右子树最左节点）替换 被删除节点。

同样可以理解为，左子树 增加节点。

和插入节点的思路一样。每次删除成功后，根据 父节点 bf 的值 进行 判断 是否旋转调整子树。
1
2
3
4
5
6
7
8

5.3.4 实例实现–插入、删除

实现最重要的一点就是要知道怎样更新 bf 的值，以及何时进行旋转调整平衡。

实现代码实现分两种，第一种是无论何时都获取树的高度，第二种是无论何时每个节点都保存 bf 值。

第二种详细代码实现

6. Red Black Tree（RBT）

6.1 概念

1. 每个结点是红的或者黑的
	
2. 根结点是黑的
	
3. 每个叶子结点是黑的
	
4. 如果一个结点是红的，则它的两个儿子都是黑的
	
5. 对每个结点，从该结点到其子孙结点的所有路径上的包含相同数目的黑结点
1
2
3
4
5
6
7
8
9

6.1 保持自平衡方法-旋转调整

6.2 实现

6.2.1 分析-插入

总结：

为了更好的实现插入，将默认生成的节点颜色设置为红色，因此经分析得出：
	只有当插入位置（cur）的父节点（p）为 红色时 才会出现 旋转及变色调整（此时违背性质 4），
		需要发生调整又会根据 叔父节点（u）的颜色而出现 调整 的区别。（详见上图 情况 3.1.1 至 3.1.6）
			
当插入位置的父节点为 黑色时，直接插入即可。
	
实现代码时（详见 6.3）多看看上面的分析和总结。	
1
2
3
4
5
6
7

6.2.2 分析-删除

7. B Tree/ B-Tree

• B Tree 就是 B-Tree，“-” 是个连字符号，不是减号。

• B Tree 是在多叉树的基础上加上一些限制条件来的，多叉的好处非常明显，有效的降低了 B-树的高度。

7.1 B Tree 性质

• 一颗 M 阶 （M阶，指多叉树有多少个叉）B 树 T，满足以下条件

  1. 每个节点至多拥有 M 棵子树
  2. 根节点至少拥有两颗子树
  3. 除了根节点以外，其余每个分支节点至少拥有 M/2 棵子树
  4. 所有叶节点都在同一层上（这个概念就能看出 B tree 相比 平衡类二叉树 降层高）
  5. 有 k 棵子树的分支节点则存在 k-1 个关键字，关键字按照递增顺序进行排序
  6. 关键字数量满足 ceil(M/2) - 1 = n <= M-1

• B Tree 每个节点都包含 索引值 Key 和 对应数据 Data（区别于 B+ 树）。
  - 因为每个节点包含 键值，故在该树全集内做一次查找,性能逼近二分查找；

7.2 B Tree 和 磁盘关系

• B Tree 的作用
  - 树是专门为外部存储器设计的，如磁盘，它对于读取和写入大块数据有良好的性能，所以一般被用在文件系统及数据库中。

• 为什么会出现 B-树 这类数据结构
  传统用来搜索的平衡二叉树有很多，如 AVL 树，红黑树等。这些树在一般情况下查询性能非常好，但当数据非常大的时候它们就无能为力了。
  原因当数据量非常大时，内存不够用，大部分数据只能存放在磁盘上，只有需要的数据才加载到内存中。一般而言内存访问的时间约为 50 ns，而磁盘在 10 ms 左右。速度相差了近 5 个数量级，磁盘读取时间远远超过了数据在内存中比较的时间。这说明程序大部分时间会阻塞在磁盘 IO 上。
  那么我们如何提高程序性能？减少磁盘 IO 次数，像 AVL 树，红黑树这类平衡二叉树从设计上无法“迎合”磁盘。

• 从“迎合”磁盘的角度来看看B-树的设计
  索引的效率依赖与磁盘 IO 的次数，快速索引需要有效的减少磁盘 IO 次数，如何快速索引呢？
  - 索引的原理其实是不断的缩小查找范围，就如我们平时用字典查单词一样，先找首字母缩小范围，再第二个字母等等。平衡二叉树是每次将范围分割为两个区间。
  - 为了更快，B-树 每次将范围分割为多个区间，区间越多，定位数据越快越精确。那么如果节点为区间范围，每个节点就较大了。
  - 所以新建节点时，直接申请页大小的空间（磁盘存储单位是按 block 分的，一般为 512 Byte。
  磁盘 IO 一次读取若干个 block，我们称为一页，具体大小和操作系统有关，一般为 4 k，8 k或 16 k），计算机内存分配是按页对齐的，这样就实现了一个节点只需要一次 IO。

• B-Tree 的查找
  一般而言，根节点都在内存中，B-Tree 以每个节点为一次磁盘 IO.
  比如下图中，若搜索 key 为 25 节点的 data，首先在根节点进行二分查找（因为 keys 有序，二分最快），判断 key 25 小于 key 50，所以定位到最左侧的节点，此时进行一次磁盘 IO，将该节点从磁盘读入内存，接着继续进行上述过程，直到找到该 key 为止。

7.2 B Tree 的实现

• 添加

  1. 添加的时候只有分裂
  2. 添加情况两种
     • 普通插入，即插入的节点不满
     • 插入后要裂变，即 插入后大于 M 。
       （特别注意）裂变发生时机发生在，下一次插入 大于 M 时，而不是 插入后 等于 M 时。

• 删除

  1. 删除的时候只有合并
  2. 删除情况四种
     • 删除key，不是叶子结点，且 key值
       1. 前面节点大于 degree - 1
       2. 后面节点大于 degree - 1
       3. 前面节点等于 degree - 1 ，后面节点等于 degree - 1
     • 删除key，在叶子结点
       直接把 key 值删除。

8. ​ B+ Tree

B+ tree 是 B tree 的一种变形。

文件系统及数据库系统普遍采用 B-/+Tree 作为索引结构.

8.1 性质

• 一棵 M 阶 B+ 树（如下图），必须满足如下条件：
  1. 每个结点最多有 M 棵子树
  2. 如果根不是终端结点，则根结点至少有 1 个关键字，即至少有 2 棵子树。（根的关键字取值范围是[1，m-1]）
  3. 每个关键字对应一棵子树（与 B Tree 的不同），具有 k 个子树的非叶结点包含 k 个键。
  4. 每个非叶子结点（除了根）具有至少 m/2 子树，即最少有 m/2 个关键字。
  5. （特别注意）终端结点包含全部关键字及相应记录的指针，叶结点中将关键字按大小顺序排序，并且相邻叶结点按大小顺序相互链接起来。
  6. 所有分支结点（可以视为索引的索引）中金包含他的各个子节点（即下一级的索引块）中关键字最大值，及指向其子结点的指针。

• 特别注意
  1. B+ Tree 中所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data)相当于叶子节点的索引，叶子节点携带真正的 data。
     因此一般 B+ Tree 的叶节点和内节点大小不同，而 B-Tree 的每个节点大小一般是相同的，为一页。
  2. B+ Tree 中 叶子结点有一个链指针（上面性质 5）
  3. B+ Tree 做索引优点

     1. 因为 B+ Tree 叶子结点有链指针，可大大增加区间访问性，可使用在范围查询等，而 B-Tree 每个节点 key 和 data 在一起，则无法区间查找。

     2. 根据空间局部性原理：如果一个存储器的某个位置被访问，那么将它附近的位置也会被访问。
        B+ Tree 可以很好的利用局部性原理, 可以利用磁盘预读原理提前将这些数据读入内存，减少了磁盘 IO 的次数。

     3. B+ Tree 更适合外部存储。由于内节点无 data 域，每个节点能索引的范围更大更精确。

        • 原因：
          前面说过磁盘是分 block 的，一次磁盘 IO 会读取若干个 block，具体和操作系统有关，那么由于磁盘 IO 数据大小是固定的，在一次 IO 中，单个元素越小，量就越大。这就意味着 B+Tree 单次磁盘 IO 的信息量大于 B-Tree，从这点来看 B+Tree 相对 B-Tree 磁盘 IO 次数少。