• 解法：父节点变为黑色，祖父节点变为红色，在祖父节点为支点右旋 （从情况1到情况3，终于调整完成）
二叉树的删除
• 二叉树插入一个结点
红黑树的删除 1/6
• 二叉树的删除
– 没有儿子，即为叶结点。直接把父结点的对应儿子指针设为NULL，删除儿子结点就OK了。 – 只有一个儿子。那么把父结点的相应儿子指针指向儿子的独生子，删除儿子结点也OK了。 – 有两个儿子
后缀树 1/4
• 以字符串S=XMADAMYX为例，它的长度为8，所以S[1..8], S[2..8], ... , S[8..8]都算S的后缀，我们一般还把空字串也算成后缀。这样，我们一共有 如下后缀（对于后缀S[i..n]，我们说这项后缀起始于i）： S[1..8], XMADAMYX， 也就是字符串本身，起始位置为1 S[2..8], MADAMYX，起始位置为2 S[3..8], ADAMYX，起始位置为3 S[4..8], DAMYX，起始位置为4 S[5..8], AMYX，起始位置为5 S[6..8], MYX，起始位置为6 S[7..8], YX，起始位置为7 S[8..8], X，起始位置为8 空字串，记为$
B树的删除示例 1/6 • 还是以5阶B树为例，依次删除H,T,R,E
– 树中最多含有m（m=5）个孩子，因此关键字数最小为ceil(m / 2)-1=2。 – 即关键字数小了（小于2个）就合并，大了（超过4个）就分裂
后缀树 2/4
把上面的后缀加入Trie后， 我们得到右边的结构：
后缀树 3/4
• 把这种没有分叉的路径压缩到一条边 • 并在叶节点上标注上每项后缀的起始位置
后缀树 4/4 • 在待处理的子串后加一个空字串
– 例如我们处理XMADAMYX前，先把XMADAMYX变为 XMADAMYX$， 于是就得到suffix tree--后缀树了
• 如果删除该元素后，首先判断该元素是否有左右孩子结点
– 如果有，则上移孩子结点中的某相近元素(“左孩子最右边的节点”或“右孩子 最左边的节点”)到父节点中，然后是移动之后的情况 – 如果没有，直接删除后，移动之后的情况。
• 删除元素，移动相应元素之后，如果某结点中元素数目（即关键字数）小于 ceil(m/2)-1，则需要看其某相邻兄弟结点是否丰满（结点中元素个数大于 ceil(m/2)-1）
Tire 树的应用
• tire树可以理解为一个N叉树，对于26个字母集的tire树即是一 个26叉树。对于10个阿拉伯数字即是一个10叉树。 • tire树的插入、查找、删除的时间复杂度都是o(N)
– N为待插入、查找、删除字符串的长度。
• tire树的使用场合：
– 求最近公共祖先，需要利用tire树作为数据结构 – 排序：前序遍历tire树，即可以得到一个按字母顺序的排序表 – 字符串检索：在搜索引擎中会用的，主要是已知一个字符串集合，对 这个集合进行预处理生成一个tire树，以后就维护这个tire树即可。
• (注：变化前，原本就未违反性质5，只是为了把问题转化为兄弟节点为黑色的情况)。
红黑树的删除 4/6
• 删除修复情况2：当前节点是黑加黑且兄弟是黑色且兄弟节点的两个子节点 全为黑色。
– 解法：把当前节点和兄弟节点中抽取一重黑色追加到父节点上，把父节点当成新 的当前节点，重新进入算法
• （此变换后性质5不变）
– ⑥插入Z时，最右的叶子结点空间满了，需要进行分裂操作，中间元素T上移到 父节点中，注意通过上移中间元素，树最终还是保持平衡，分裂结果的结点存在 2个关键字元素：
B树的插入示例 5/5
• CNGAHEKQMFWLTZDPRXYS
– ⑦插入D时，导致最左边的叶子结点被分裂，D恰好也是中间元素，上移到父节点中，然 后字母P,R,X,Y陆续插入不需要任何分裂操作（别忘了，树中至多5个孩子）：
• 不断插入多个元素的过程
2-3-4树一次完整的插入示例 1/2
• 接上，继续插入元素N、B、X
红黑树的5个性质
1. 2. 3. 4. 5. 每个结点要么是红的，要么是黑的。 根结点是黑的。 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。 如果一个结点是红的，那么它的俩个儿子都是黑的。 对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数 目的黑结点。
• 二叉空间分区（BSP）树
– 四叉树 八叉树 k树 融合树 区间树 PQ树 Range tree SPQR树 Van Emde Boas tree
• 空间数据分区树
– R树 R*树 R+树 X树 M树 线段树 希尔伯特R树 优先R树
• 其他树
– 堆 散列日历 散列树 Finger tree Order statistic tree Metric tree Cover tree BK树 Doubly chained tree iDistance Link-cut tree Fenwick tree Log-structured merge-tree 树状数组
– ⑧最后，当插入S时，含有N,P,Q,R的结点需要分裂，把中间元素Q上移到父节点中，但
是情况来了，父节点中空间已经满了，所以也要进行分裂，将父节点中的中间元素M上移 到新形成的根结点中，注意以前在父节点中的第三个指针在修改后包括D和G节点中。
B树的删除
• 首先查找B树中需删除的元素
– 如果该元素在B树中存在，则将该元素在其结点中进行删除
– 如果丰满，则向父节点借一个元素来满足条件； – 如果其相邻兄弟都刚脱贫，即借了之后其结点数目小于ceil(m/2)-1，则该结点与 其相邻的某一兄弟结点进行“合并”成一个结点，以此来满足条件。
• 提醒
– B树的第5个特性中的c点： c)除根结点之外的结点（包括叶子结点）的关键字的 个数n必须满足： （ceil(m / 2)-1）<= n <= m-1。m表示最多含有m个孩子，n表 示关键字数。在本小节中举的一颗B树的示例中，关键字数n满足：2<=n<=4
从2-3-4树开始谈起
2-3-4树的查找
2-3-4树的插入 1/3
2-3-4树的插入 2/3
2-3-4树的插入 3/3
• 最大：4-node
– 最多3 keys，4 children
2-3-4树的分裂
• 2-node 变成 3-node
• 3-node 变成 4-node
2-3-4树一次完整的插入示例 1/2
二叉树的插入
• 插入一个节点
红黑树的插入
•
插入一个元素后，需要修复，修复有两种手段
– 重新着色 – 旋转操作：左旋与右旋
红黑树的插入修复代码
• 3种插入修复情况
插入一个元素而后修复的几种情况 1/3
• 插入修复情况 [预处理]
– 插入的是根结点 • 原树是空树，此情况只会违反性质2 – 对策：直接把此结点涂为黑色。
红黑树的删除 5/6
• 删除修复情况3：当前节点颜色是黑+黑，兄弟节点是黑色，兄 弟的左子是红色，右子是黑色。
– 解法：把兄弟结点染红，兄弟左子节点染黑，之后再在兄弟节点为支点 解右旋，之后重新进入算法
• 此是把当前的情况转化为情况4，而性质5得以保持
红黑树的删除 6/6
• 删除修复情况4：当前节点颜色是黑-黑色，它的兄弟节点是黑色，但是兄弟 节点的右子是红色，兄弟节点左子的颜色任意
• 看过了二叉树的插入删除 • 看过了2-3-4树分裂 • 接下来，看另外一种新树
– 它与红黑树最大的区别在于，它的结点可以有许多子女，从几个 到几千个
B树 • 出现缘由
– 二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导 致查询效率低下
一棵B树的示例
• 查找文件29
– 一直往下，3次磁盘IO操作和3次内存查找
B树的插入示例 2/5
• 插入以下字符字母到一棵空的B 树中（非根结点关键字数小了（小于2个） 就合并，大了（超过4个）就分裂）： CNGAHEKQMFWLTZDPRXYS
– ①首先，结点空间足够，4个字母插入相同的结点中：
– ②当咱们试着插入H时，结点发现空间不够，以致将其分裂成2个结点，移动中 间元素G上移到新的根结点中，在实现过程中，咱们把A和C留在当前结点中， 而H和N放置新的其右邻居结点中：
• 选择左儿子中的最大元素或者右儿子中的最小元素放到待删除节点的位置，就可以保证结构的不变。
•
RB-Tree删除修复情况 [预处理]
– 当前节点是红+黑色
• 解法，直接把当前节点染成黑色，结束。
– 当前节点是黑+黑且是根节点
• 解法：什么都不做，结束
红黑树的删除修复代码 2/6
• 4种删除修复情况
B树的插入示例 1/5
• 一棵5阶（即树中任一结点至多含有4个关键字，5棵子树）B 树
– 根结点至少得有2个孩子
• one key，two children； • two key，three children； • three key，four children..
– 5阶，2- 4 个key，3-5 个children
[情况1变成了情况2] • 插入修复情况2：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子
– 对策：当前节点的父节点做为新的当前节点，以新当前节点为支点左旋（还没完，在情况3中继续）
插入一个元素而后修复的几种情况 3/3
[接情况2]
• 插入修复情况3：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左子
– 插入修复情况
• 插入的结点的父结点是黑色。
– 此不会违反性质2和性质4，红黑树没有被破坏。
– 对策：什么也不做。
插入一个元素而后修复的几种情况 2/3
•
插入修复情况1：当前结点的父结点是红色，且叔叔结点（祖父结点的另一个子结点）是红色