408第二轮复习 数据结构 第七章查找

平衡二叉树

平衡二叉树的定义
任意结点的左右子树的高度差的绝对值不超过1的二叉树称为平衡二叉树，也称AVL树
平衡二叉树的插入

• LL（RR）平衡旋转：由于在结点A的左(右）孩子L的左（右）子树插入新结点，A的平衡因子由1变为2，导致以A为根子树失去平衡，需要一次向右的旋转操作。
• LR（RL）平衡旋转：由于在结点A的左(右）孩子L的左（右）子树插入新结点，A的平衡因子由1变为2，导致以A为根子树失去平衡，需要两次旋转，先左后右的旋转操作。
  平衡二叉树的删除

1. 用二叉排序树的方法对结点w执行删除操作
2. 若导致不平衡，则从结点w开始向上回溯，找到第一个不平衡的点z；y为结点z的高度最高的孩子结点；x是结点y的高度最高的孩子结点
3. 平衡的调整与插入调整相同，不同在于，插入操作仅需对以z为根的子树进行平衡操作，而删除操作不一样，先对z为根的子树进行平衡操作，若调整后子树高度-1，则需要对z的祖先进行平衡调整，甚至回溯到根结点

红黑树

为了保持AVL树的平衡性，在插入和删除操作后，会频繁调整全树整体拓扑结构，代价较大，引入了红黑树的结构

• 每个结点是红的或者是黑的
• 根结点是黑色的
• 叶结点（虚构的外部结点）都是黑色的
• 不存在两个相邻的红结点（红结点的父结点和孩子结点都是黑色的）
• 对每个结点该结点到任意一个叶结点的简单路径上黑结点的数量相同

红黑树的插入

设结点z作为新插入的结点

• 用二叉查找插入，并将结点z为新插入的结点，若结点z的父亲是黑色，无须任何调整
• 若z是根结点，则将z着为黑色
• 若结点z不是根结点，z的父亲结点是红色的，则分为三种情况，区别在于z的叔结点的颜色不同和位置不同（这里只破坏了性质3（不存在两个相邻的红结点）
  • 情况1 ：z是爷爷的左孩子的右孩子（叔结点是黑色的），左旋+右旋，并交换原父亲结点和原爷爷结点的颜色
  • 情况2: z是爷爷的左儿子的左儿子（叔结点是黑色的），右旋并交换原父亲结点和原爷爷结点的颜色
  • 情况3:叔叔结点是红色的，黑色下方，递归更新

B树和B+树

B树

所谓m阶B树是所有结点的平衡因子均等于0的m路平衡查找树

一颗m阶B树或为空树，或为满足如下特性的m叉树：

1. 树中每个结点至多有m棵子树，即最多有m-1个关键字
2. 若根结点不是叶结点，则最少有2棵子树即至少有1个关键字
3. 除根结点的所有非叶结点至少有 m / 2（向上取整）棵子树
4. 所有的叶结点都出现在同一层次上，并且不带信息
5. Ki为结点的关键字，且满足K1 < k2 < … <Kn；Pi为指向子树根结点的指针Pi-1所指子树中所有结点的关键字均小于Ki，Pi所指向所有结点的关键字均大于Ki；

B树的查找
B树的查找与二叉排序很相似，只是每个结点都是多个关键字的有序表。B树的查找包含两个基于操作：1.在B树中找结点 2.在结点内找关键字。由于B树常存储在磁盘上进行的，而后一查找操作是在内存中进行的，即在磁盘上找到目标结点后，先将结点信息读入内存，然后采用顺序查找或折半查找法
B树的高度
如何计算B树的高度

• 若让每个关键字达多最多可以通过（m-1）(1 + m + m ^2 + …m ^ h) 计算最低高度
• 若让每个关键字达到最小可以通过叶结点数目进行计算 如果关键字的数目为n 则叶结点为n + 1 = ⌈m/2⌉^ h -1最高高度

B树的插入
将关键字Key插入B树的过程如下：

1. 定位 利用查找算法，找出插入关键字的终端结点
2. 插入 每个非根结点的关键字都在[⌈m/2⌉- 1,m- 1] 。若结点插入后的关键字小于m，可以直接插入；如插入后的关键字为m，必须将结点进行分裂

分裂的方法是：取一个新结点，在插入key后的原结点，从中间位置⌈m/2⌉将其中的关键词分为两部分，左部分的关键字放在原结点中，右部分包含的关键字放在新结点中，中间位置的结点插入原结点的父结点中

B树的删除
当被删关键字k不在终端结点中时，可以用k的前驱k’，（即k的左侧子树中最右下的元素来代替）k，这样就转换成在终端结点删除
删除结点有三种情形：

1. 直接删除关键字。若被删除关键字所在结点删除前的关键字个数>= ⌈m/2⌉，表明删除该关键字后仍然满足B树的定义，则直接删去该关键字
2. 兄弟够借 若被删除关键字删除前已经是⌈m/2⌉ - 1，且兄弟结点 >= ⌈m/2⌉，则需要调整该结点、以达到新的平衡（父子换位法）
3. 兄弟不够借 。被删除关键字删除前已经是⌈m/2⌉ - 1，且兄弟结点= ⌈m/2⌉ - 1,则将关键字删除后与兄弟结点以及双亲结点进行合并，若合并后
   仍不满足要求，继续合并。

B+树

一个B+树应该满足以下条件：

1. 每个分支结点最多有m棵子树
2. 非叶根结点至少有两棵子树，其他每个⌈m/2⌉ 棵子树
3. 结点的子树个数与关键字个数相等
4. 所有叶结点包含全部关键字以及指向相应记录的指针，
5. 所有分支结点中仅包含它的各个子结点中关键字最大以及指向各个子结点中关键字的最大值以及指向其子结点的指针

散列表

处理冲突的方法

• 开放地址法
  • 线性探测
  • 平方探测，散列表长度必须是一个4k + 3的素数
  • 双散列表， 需要两个散列函数当第一个散列表发生冲突的时候，利用第二个散列函数计算地址增量
• 拉链法