数据结构与算法之B树,红黑树

2017-07-05 本文已影响42人过期的薯条

1.引言

数据结构与算法这本书的树这张真的是本书的难点之一，很烧脑，看书看几遍都不懂。无奈只有看看博客，记下笔记理解下。B-树主要应用在数据库和文件系统的读写方面。一个程序的执行严重耗时的不是复杂的计算而是访问io的次数。平衡二叉树可以使时间复杂度低于log^n。这样就可以大大减少文件读写的

2.正题

B-树：多叉的平衡二叉树。

Paste_Image.png
平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

B-树的是这样定义的(假设阶数是M)：
1：树中每个结点最多含有m个子节点（m>=2）。
2：每个内节点至少 [ceil(m / 2)] 个子节点。内节点即非根节点非页子节点，也可以叫中间节点。
3: 关键字key的数量 [ceil(m / 2)-1]<= n <= m-1，关键字按递增排序。
4：每个叶节点具有相同的深度，即树的高度h，而且不包含关键字信息。

Paste_Image.png

B-树的作用：运用于大块数据的读写，常用于数据库和文件系统。

B-树的插入规则:B树的非根节点的关键字的个数K是：
M-1<=K<=2M-1。当节点的关键字==2M-1，表示插满了，此时再继续插的话就需要进行。分裂操作、

demo
阶数为3：那么每个节点的关键字K:1<=k<=2
下面我们来举例说明，首先假设这个B-树的阶为：3。树的初始化时如下：

这里写图片描述
首先，我需要插入一个关键字：30，可以得到如下的结果：

这里写图片描述
再插入26，得到如下的结果：

这里写图片描述
OK，此时如图所示，在插入的那个终端结点中，它的关键字数已经超过了m-1=2，所以我们需要对结点进分裂，所以我们先对关键字排序，得到：26 30 37 ，所以它的左部分为（不包括中间值）：26，中间值为：30，右部为：37，左部放在原来的结点，右部放入新的结点，而中间值则插入到父结点，并且父结点会产生一个新的指针，指向新的结点的位置，如下图所示：

这里写图片描述
OK，然后我们继续插入新的关键字：85，得到如下图结果：

这里写图片描述
正如图所示，我需要对刚才插入的那个结点进行“分裂”操作，操作方式和之前的一样，得到的结果如下：

这里写图片描述
哦，当我们分裂完后，突然发现之前的那个结点的父亲结点的度为4了，说明它的关键字数超过了m-1，所以需要对其父结点进行“分裂”操作，得到如下的结果：

这里写图片描述
好，我们继续插入一个新的关键字：7，得到如下结果：

这里写图片描述
同样，需要对新的结点进行分裂操作，得到如下的结果：

这里写图片描述到了这里，我就需要继续对我们的父亲结点进行分裂操作，因为它的关键字数超过了：m-1.

这里写图片描述
哦，终于遇到这种情况了，我们的根结点出现了关键子数量超过m-1的情况了，这个时候我们需要对父亲结点进行分列操作，但是根结点没父亲啊，所以我们需要重新创建根结点了。

这里写图片描述
好了，到了这里我们也知道怎么进行B-树的插入操作。

3.红黑树

参考文献：红黑树(一)之原理和算法详细介绍

应用：
红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。

红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

图红黑树：