前言

首先，请务必自己尽全力尝试实现题目，直接看成品代码，思维就被拘束了，也很容易被查重。

这里只是思路解析的博客，代码仓库在 JLU_Data_Structures_Record

希望你能在这里找到你想要的:)

第三次上机

A 手撕BST

分数 50
作者朱允刚
单位吉林大学
对一棵初始为空的二叉查找树（Binary Search Tree, BST）进行若干插入或删除操作，请输出最后的二叉查找树。

bst.png

输入格式:
输入第一行为一个整数 T，表示操作数目。随后 T 行，每行为Insert K（表示插入关键词为K的结点，若树中已有关键词为K的结点，则不插入）或Remove K（表示删除关键词为K的结点，若树中无关键词为K的结点，则不删除），其中K为整数。 T 不超过2×10^{5，树高不超过10}4。

输出格式:
输出经上述操作后得到的二叉查找树的中根序列和先根序列，序列中每个整数后一个空格，两个序列之间用空行间隔。

输入样例:
16
Insert 17
Insert 31
Insert 13
Insert 11
Insert 20
Insert 35
Insert 25
Insert 8
Insert 4
Insert 11
Insert 24
Insert 40
Insert 27
Insert 9
Remove 17
Remove 13

输出样例:
4 8 9 11 20 24 25 27 31 35 40

20 11 8 4 9 31 25 24 27 35 40

代码长度限制
16 KB
时间限制
500 ms
内存限制
64 MB
栈限制
8192 KB

二叉查找树的插入和查找都不算难，但删除需要注意的是，如果要删的节点有两个子节点，则将该节点的右子树中最小的节点与之交换，并执行从右子树中删除该最小点的任务。其余与普通的二叉树一样操作。

B 手撕AVL树（基础版）

分数 50
作者朱允刚
单位吉林大学
对一棵初始为空的高度平衡树（AVL树）进行若干插入或删除操作，请输出最后得到的AVL树。

备注：
（1）当有多种旋转方案时，优先选择旋转次数少的方案。
（2）70%的测试点只包含插入操作，如果你只实现插入操作，也能获得70%的分数。

输入格式:
输入第一行为一个整数 T，表示操作数目。随后 T 行，每行为Insert K（表示插入关键词为K的结点，若树中已有关键词为K的结点，则不插入）或Remove K（表示删除关键词为K的结点，若树中无关键词为K的结点，则不删除），其中K为整数。 T 不超过2×10
5
。

输出格式:
输出经上述操作后得到的高度平衡树的中根序列和先根序列，序列中每个整数后一个空格，两个序列之间用空行间隔。

输入样例:
16
Insert 17
Insert 31
Insert 13
Insert 11
Insert 20
Insert 35
Insert 25
Insert 8
Insert 4
Insert 11
Insert 24
Insert 40
Insert 27
Insert 9
Remove 17
Remove 13
输出样例:
4 8 9 11 20 24 25 27 31 35 40

20 8 4 11 9 31 25 24 27 35 40
代码长度限制
16 KB
时间限制
100 ms
内存限制
64 MB
栈限制
8192 KB

二叉平衡树的插入和删除也是思维不复杂，但实现很麻烦的东西，我只能说，为了使程序的逻辑尽可能清晰，尽量把功能打包成函数，比如一个节点的高度什么的

C 手撕红黑树

分数 50
作者朱允刚
单位吉林大学
对一棵初始为空的红黑树（Red-Black Tree, RBT）进行若干插入或删除操作，请输出最后的红黑树。

rbt.png

备注：
（1）当有多种旋转方案时，优先选择旋转次数少的方案。
（2）70%的测试点只包含插入操作，如果你只实现插入操作，也能获得70%的分数。

输出格式:
输出经上述操作后得到的红黑树的中根序列和先根序列，序列中对于每个结点输出其关键词和颜色（红色用R表示，黑色用B表示），每个元素后一个空格，两个序列之间用空行间隔。

输入样例:
5
Insert 8
Insert 9
Insert 3
Insert 4
Insert 5

输出样例:
3 R 4 B 5 R 8 B 9 B

8 B 4 B 3 R 5 R 9 B

代码长度限制
16 KB
时间限制
100 ms
内存限制
64 MB
栈限制
8192 KB

红黑树这题，也差一个点没过，故不作思路解析

第四次上机

A 手撕STL sort（进阶版）

分数 100
作者朱允刚
单位吉林大学
事实上，STL的sort函数在上一题（基础版）的基础上，还采用了下列优化手段，以进一步提升快速排序算法的效率。

（3）“三数取中”选基准元素。不是选取第一个元素作为基准元素，而是在当前子数组中选取3个元素，取中间大的那个元素作为基准元素。从而保证选出的基准元素不是子数组的最小元素，也不是最大元素，避免Partition分到子数组最边上，以降低最坏情况发生的概率。
为确保本题答案唯一，本算法的实现请以教材为准，即普林斯顿大学Sedgewick教授给出的方法：若当前子数组是R[m]…R[n]，选取R[m]、R[(m+n)/2]和R[n]的中位数作为基准元素。先将R[(m+n)/2]与R[m+1]交换；若R[m+1]比R[n]大，交换二者；若R[m]比R[n]大，交换二者；若R[m+1]比R[m]大，交换二者。

（4）尾递归转为循环。即将传统快速排序代码

void QuickSort(int R[],int m,int n){
   if(n - m + 1 > threshold){
        int j = Partition(R, m, n); 
        QuickSort(R, m, j-1);  //递归处理左区间
        QuickSort(R, j+1, n);  //递归处理右区间，尾递归
     }
}

转换为

void QuickSort(int R[],int m,int n){
   while(n - m + 1 > threshold){    //注意此处不是if，而是while
        int j = Partition(R, m, n); 
        QuickSort(R, m, j-1);  //递归处理左区间
        m = j+1;  //通过while循环处理右区间，从而消除尾递归
     }
}

即先递归处理左区间，后循环处理右区间，从而消除一个尾递归，以减少递归调用带来的时空消耗。
这里需注意，尾递归转循环后，转入堆排序的时机不仅仅是递归深度达到2logn，而是递归深度和while循环迭代的次数加一起达到2logn时转入堆排序。

（5）优先处理短区间。在上述策略（4）的基础上进一步改进，不是按固定次序处理左右子区间（每次都先处理左区间、后处理右区间），而是先（通过递归）处理左右两个子区间中“较短的那个区间”，然后再（通过循环）处理两个子区间中“较长的那个区间”。从而使每次递归处理的子数组长度至少缩减一半，使最坏情况下递归深度（算法最坏情况空间复杂度）为logn。

（6）三路分划（3-Way Partition）。当重复元素很多时，传统快速排序效率较低。可修改Partition操作，不是把当前数组划分为两部分，而是三部分：小于基准元素K的元素放在左边，等于K的元素放在中间，大于K的元素在右边。接下来仅需对小于K的左半部分子数组和大于K的右半部分子数组进行排序。中间等于K的所有元素都已就位，无需处理。
为确保本题答案唯一，此处请采用如下做法：若当前子数组是R[m]…R[n]，可设置3个指针，前指针i，中指针j，后指针k。初始时i和j指向第一个元素，k指向最后一个元素；指针j从左往右扫描数组：

若R[j]小于基准元素，交换R[j]和R[i], i++, j++；
若R[j]大于基准元素，交换R[j]和R[k], k--；
若R[j]等于基准元素，j++；
通过指针j的遍历，使小于基准元素的元素换到当前子数组左侧，大于基准元素的元素换到右侧。当j扫描完当前子数组后，R[m]…R[i-1]即小于基准元素的元素，R[i]…R[k]即等于基准元素的元素，R[k+1]…R[n]即大于基准元素的元素。

在本题中，请你在之前实现的STL sort()初级版的基础上，进一步实现上述优化策略。

提示：本题只需把原来的Partition改为3-way Partition，并使用“三数取中”法选择基准元素。
在快速排序函数里，改为“尾递归转循环 + 先处理短区间”。你可以在Visual Studio里对sort函数右键点击“转到定义”，查看VS中STL的sort()实现细节
vstudio sort转到定义图片.jpg

函数接口定义：
void sort(int *R, int n);
功能为对整数R[1]…R[n]递增排序。

裁判测试程序样例：

#include<iostream>
#include<stdlib.h>
#include<math.h>
using namespace std;
int threshold;

// 请在这里补充你的代码，即你所实现的sort函数

int main()
{
    int n,i;
    int a[50010];
    scanf("%d %d", &n, &threshold);
    for (i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    
    sort(a,n);
    
    printf("Final:");
    for (i = 1; i <= n; i++)
        printf("%d ",a[i]);
    printf("\n");
    return 0;
}

备注：提交代码时，只需提交sort函数以及你自定义的其他函数，不用提交#include或者main函数等内容。

输入格式:
输入第一行为2个正整数n和threshold，n为待排序的元素个数，不超过50000，threshold为改用插入排序的阈值，不超过20，含义如上所述。第二行为n个空格间隔的整数。本题中读入数据的操作无需你来实现，而由框架程序完成。

输出格式:
输出第一行为以depth_limit:开头的整数，表示转为堆排序的递归深度，即⌊2log
2n⌋。从第二行开始，输出对某子数组转为堆排序后，该子数组初始建堆的结果，每个元素后一个空格，每个堆占一行，以Heap:开头。注意，可能不止一个堆。接下来下一行，输出n个整数，每个整数后一个空格，为快速排序所有递归退出后，插入排序执行前的数组元素，以Intermediate:开头。最后一行为n整数，每个整数后一个空格，表示排序后的数组，以Final:开头（最后一行由框架程序完成，无需你来输出）。

输入样例1：
10 2
10 9 8 7 6 5 4 3 2 1

输出样例1：
depth_limit:6
Intermediate:1 2 3 5 4 6 7 8 9 10
Final:1 2 3 4 5 6 7 8 9 10

输入样例2：
60 2
66 61 92 22 50 80 39 2 25 60 49 17 37 19 24 57 40 82 11 52 45 0 33 78 32 25 19 42 92 50 39 87 74 87 56 79 63 63 80 83 50 3 87 2 91 77 87 10 59 23 25 6 49 85 9 95 60 16 28 1
输出样例2：
depth_limit:11
Intermediate:1 0 2 2 3 6 9 10 11 16 17 19 19 22 23 24 25 25 25 32 28 33 37 39 39 40 42 45 49 49 50 50 50 52 56 57 59 60 60 61 63 63 66 74 77 78 79 80 80 82 83 85 87 87 87 87 91 92 92 95
Final:0 1 2 2 3 6 9 10 11 16 17 19 19 22 23 24 25 25 25 28 32 33 37 39 39 40 42 45 49 49 50 50 50 52 56 57 59 60 60 61 63 63 66 74 77 78 79 80 80 82 83 85 87 87 87 87 91 92 92 95

代码长度限制
16 KB
时间限制
100 ms
内存限制
64 MB

此题基于课程设计第二次上机A题，而且改进方法都在题目里，是在不行，朱老师的ppt里有来着？

小结

好像又没啥可结的，总之就这样罢

标签：JLU,25,结点,递归,Insert,int,题解,元素,数据结构
From： https://www.cnblogs.com/luyaoqi/p/18283245

[JLU] 数据结构与算法上机题解思路分享-

前言