数据结构学习记录2021.4.9_除留余数法

书接上回。
上回我们说到了二叉排序树的基本特性，那么根据二叉排序树的基本特性，可以容易得出其查找算法：若待查元素大于结点，则在其右子树上继续查找，反之，则在左子树上继续查找，知道找到或者结点的左（右）结点为空。
在二叉排序树中插入新结点，只要保证插入后仍符合二叉排序树的定义即可。二叉树的插入过程为：若二叉排序树为空，则将元素插入为新的根结点，否则继续在其左子树或右子树上查找，直至某个结点的左子树或右子树为空为止，元素作为该结点的左孩子或右孩子插入。
那么，和插入相反的是，删除是在查找成功之后才进行的，要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性，也就是说，在二叉排序树中删除一个结点相当于删除有序序列中的一个结点。
删除有三种情况：
1、被删除的结点是叶子结点：直接删除
2、被删除的结点只有左子树或右子树：将该结点删除并将其子树连接在其父节点上
3、被删除的结点既有左子树又有右子树：查找该结点的前驱或后继结点，将待删除结点应用前驱或后继结点覆盖，然后删除其前驱或后继结点。
就平均性能而言，二叉排序树上的查找和折半查找相差不大，并且二叉排序树上的插入和删除结点十分方便，无需移动大量结点。因此，对于经常需要做插入、删除和查找运算的序列，宜采用二叉排序树结构。由此，二叉排序树也称二叉查找树。

针对于二叉树来说，有树的高度和深度。
树的深度：从根结点开始（根结点深度为0）自顶向下逐层累加的
树的高度：从叶子结点开始（叶子节点高度为0）自底向上逐层累加的。在计算高度的时候，根结点要计算最大的高度。

二叉平衡树或者是一棵空树，或者是具有如下特性的二叉树：

• 它必须是一棵二叉排序树，它的左、右子树都必须是平衡二叉树
• 它的左、右子树的高度只差的绝对值小于等于1。也就是说，平衡因子（左、右子树的高度只差）只能有三种取值：1、0、-1
  【平衡因子的计算方法是：平衡因子=左子树高度-右子树高度；即左子树最长叶子结点到该节点的高度（从0开始计算）减去右子树最长叶子结点到该结点的高度（从0开始计算）】

插入某一结点后，可能会造成树的部分失衡，因此就引出了最小不平衡子树的概念。最小不平衡子树就是指：以距离插入结点最近的、且平衡因子的绝对值大于1的结点为根的子树。
对不平衡子树的调整方法有四种：LL、RR、LR、RL
LL型：将不平衡结点和它的后继结点（造成不平衡的结点）顺时针的方向旋转，且将造成不平衡结点的右孩子作为自己的左孩子。
RR型：将不平衡结点和它的右子树逆时针旋转，并将右子树的左孩子作为自己的右孩子
LR型：先将造成不平衡的两结点逆时针旋转，再和不平衡结点顺时针旋转
RL型：先将造成不平衡的两结点逆时针旋转，再和不平衡结点逆时针旋转

为了方便记忆，我们不妨假设L代表逆时针旋转，R代表顺时针旋转。那么LL则为顺时针旋转（负负得正，逆逆为顺），RR为逆时针。LR为先逆时针，再顺时针。RL为先顺时针，再逆时针。

那么，如何构造一棵平衡二叉树呢？构造平衡二叉树的过程就是从空的二叉树开始，不断执行插入操作，当某结点插入平衡二叉树时引起不平衡，则进行相应的调整。

散列技术：在元素和关键码之间建立一个确定的对应关系H，使得每个关键码key和唯一的一个存储位置（即散列值）H（key）对应。采用散列技术将记录存储在一块连续的存储空间中，就是散列表。这种对应关系就叫做散列函数。
从理论上来讲，散列查找是查找速度最快的查找方法。

散列函数设计
散列函数的设计方法主要有以下几种方法：
1、直接定址法：H（key） = a * key + b
这种方法计算简单，没有冲突，适合于关键码分布比较连续的情况，否则空间浪费较多。
2、除留余数法：H（key） = key % p （p <= m）
除留余数法的基本思想是：选择某个适当的正整数p，以关键码除以p的余数作为散列地址。其中m为散列表的长度，p为小于或等于散列表长度m的某个最大素数。（p的选取要避免key值的冲突）
3、数字分析法：假设关键码集合中的每个关键码都是由S位数字组成（u1，u2，…，us），分析每位数字的分布情况，从中提取分布均匀的若干位或它们的组合作为地址。这种方法适合于所有关键码已知，并对每一位的取值分布有所分析的情况。
4、平方取中法
5、折叠法

上面基本上就把查找的内容整理完了。
接下来讲一讲排序。

排序的主要目的是便于查找。排序算法 基本上基于顺序表而设计的。
1、插入排序。
基本方法是寻找一个指定元素在待排序元素中的位置，然后插入。最简单的插入算法是直接插入排序。

1. 直接插入排序
   基本思想：每次将一个待排序的元素按其关键码的大小插入到一个已经排序好的有序序列中，直到全部元素排序好。
   由于待排序记录采用顺序存储结构，当找到插入点并将待插入记录插入到该位置后，还需要将这个位置之后的元素后移一个位置，才能算完成一趟排序。因此，为了提高时间效率，我们采用在顺序查找过程中边查找边后移的策略来完成一趟插入。
   直接插入排序是一种稳定的排序算法，特别适合于待排序集合基本有序的情况。
2. 希尔排序
   希尔排序又称为"缩小增量排序"，是对直接插入排序的一种改进。其基本思想为：将待排序的元素分为多个子集，分别对这些子集进行直接插入排序，待整个序列基本有序时，再对元素进行一次直接插入排序。
   总结起来希尔排序的原理就是：首先将原序列分解为d = n / 2个子序列（其中d为子序列的个数，n为原序列的元素个数），对每个子序列进行直接插入排序。然后缩小间隔d，取d = d / 2 ，对分出来的子序列继续进行直接插入排序。直到最后取d = 1，将所有对象放在同一序列中排序为止。

2、交换排序（元素交换一次，相当于移动三次）
交换排序的基本方法是 在待排序元素中选择两个元素，将它们的关键码进行比较，如果反序列则交换它们的位置，知道没有反序列为止。

1. 冒泡排序
   基本思想：两两比较相邻的元素，如果反序则交换位置，直到没有反序的元素位置。
2. 快速排序
   快速排序是冒泡排序的改进算法，由于冒泡排序的元素比较和移动是在相邻位置进行，需要比较移动多次才能到最终的位置，而快速排序元素的比较和移动是从两端向中间进行的，元素移动的距离较远。由于每次元素的移动，都会非常接近该元素最后排好序的位置，因此，快速排序算法的效率很高。
   基本思想：在分区中选择一个元素作为轴值，将待排序元素划分为两个分区，使得左侧元素的关键码小于或等于轴值，右侧的关键码大于或等于轴值，然后分别对这两个分区重复上述过程，直到整个序列有序。

根据上面的描述，我们可以知道快速排序需要解决三个问题：

1. 轴值的选择：可选第一个元素、中间元素、末尾元素。建议直接选择第一个元素。
2. 分区的实现：分区的算法要求使大于轴值的元素右移，小于元素的轴值左移，可按以下方式实现。
   首先是初始化：取第一个元素作为轴值，并保存到任意的位置；然后设计两个标记i和j，分别指示待排序区间的左值和右值，即 i = 1 为左侧第一个待查的元素， j = n为右侧第一个待比较元素。
   然后是右侧扫描：从后往前找到第一个比基准小的元素，移至位置i。
   最后是左侧扫描：从前往后找到第一个比基准大的元素，移至位置j。
   反复执行以上两个过程，直到 i 与 j 相等，将保存的轴值移至位置 r[i] ，一趟快速排序结束。
   每一次分区，可以将一个元素，即轴值，移动到最终的位置。
3. 结束的判定
   当分区不断缩小至只有一个元素时，快速排序结束。