0 从“树”到“搜索树”

前面所说的都是线性表，基于数组实现或者基于链表实现都有优缺点，数组做查找元素快，链表做插入删除元素快。

树是半线性结构（semi-linear structure），结合了二者特点。

本书约定，仅含单个节点的树高度为0，空树高度为-1。

特别地，约定根节点的深度depth(r) = 0，故属于第0层。

特别地，不含一度节点的二叉树称作真二叉树（proper binary tree）。

有序多叉树 = 二叉树 ，在全遍历中就能看出能相互转化。

二叉树表达能力和多叉数一样的，而且得益于其定义的简洁性以及结构的规范性，所以都用二叉树。

树是怎么做到高效率的动态修改和高效率的静态查找？答案是用一些搜索树和高级搜索树。

1 二叉搜索树（binary search tree）

二叉搜索树的实现与分析，search()、insert()和remove()等主要接口的运行时间，均线性正比于二叉搜索树的高度。

将二分搜索树与常规二叉树分开的属性是

• 左子树的所有节点均小于根节点

• 右子树的所有节点均大于根节点

• 每个节点的两个子树也是BST，即它们具有以上两个属性

查找、插入和删除操作 操作：

查找：从根节点出发，比较左孩子和右孩子，从而判断进入左子树递归还是进入右子数递归。（分而治之）

插入：利用查找返回大于数值一点的节点。然后把数值作为左孩子，最后更新祖先高度。

删除：利用查找找到位置后，单分支和双分支处理不一样。

2 平衡搜索树-AVL树

通过合理设定适度平衡的标准，并借助以上等价变换，AVL树（AVL tree）可以实现近乎理想的平衡。在渐进意义下，AVL树可始终将其高度控制在O(logn)以内，从而保证每次查找、插入或删除操作，均可在O(logn)的时间内完成。

任一节点v的平衡因子（balance factor）定义为“其左、右子树的高度差”，即balFac(v) = height(lc(v)) - height(rc(v))

插入或者删除会造成树不平衡，此时通过一些旋转操作让树重新平衡，满足AVL特点。

3 伸展树splay tree

[一个很好的介绍伸展树的博客点我]

伸展树也是一种平衡搜索树。

我们评估算法结构用的随机的最坏的，但实际应用场合有一定规律，如果我们适应这种规律设计算法结构，可以使得数据结构这个应用中得到更高效率。伸展树就是这么想的。

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

4 B树

B树

B-树结构非常适宜于在相对更小的内存中，实现对大规模数据的高效操作。

所谓m阶B-树（B-tree），即m路平衡搜索树（m >= 2），其宏观结构如图8.11所示。

下面来具体介绍一下B-树（Balance Tree），一个m阶的B树具有如下几个特征：

1.根结点至少有两个子女。

2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m

3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m

4.所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

[读一下这里介绍B数和B+数的，生动形象。点我]

数据库存储或者磁盘存储，读取数据还需要考虑到I/O时间，一次读取1一个数据和10个数据所花费的时间相当，但使用10次读取每次读取1个数据却是很耗时间，所以考虑使用m路平衡搜索树。

B树 查找、插入、删除操作。B树主要用于文件系统以及部分数据库索引（比如非关系型数据库MongoDB）。

大部分关系型数据库使用B+树作为索引。

5 B+树

大神的漫画比看书快，多看几遍后再去看书。

还是看这里，点我

6 红黑树

平衡二叉搜索树的形式多样，且各具特色。比如，8.1节的伸展树实现简便、无需修改节点

结构、分摊复杂度低，但可惜最坏情况下的单次操作需要(n)时间，故难以适用于核电站、医

院等对可靠性和稳定性要求极高的场合。反之，7.4节的AVL树尽管可以保证最坏情况下的单次

操作速度，但需在节点中嵌入平衡因子等标识；更重要的是，删除操作之后的重平衡可能需做多

达(logn)次旋转，从而频繁地导致全树整体拓扑结构的大幅度变化。

红黑树即是针对后一不足的改进。通过为节点指定颜色，并巧妙地动态调整，红黑树可保证：

在每次插入或删除操作之后的重平衡过程中，全树拓扑结构的更新仅涉及常数个节点。尽管最坏

情况下需对多达(logn)个节点重染色，但就分摊意义而言仅为O(1)个（习题[8-14]）。

当然，为此首先需在AVL树“适度平衡”标准的基础上，进一步放宽条件。实际上，红黑树 所采用的“适度平衡”标准，可大致表述为：

任一节点左、右子树的高度，相差不得超过两倍。

大神的漫画比看书快，多看几遍后再去看书。

还是看这里，点我