DataStructure

前言

学一些拓展内容，中道崩殂…

时间复杂度主定理

对于递归问题的时间复杂度计算，有主定理可以解决以下问题有

线性表

不想打字，学堆应该不难理解

栈

共享栈

计算式：

遇到第一个运算符时如果栈为空则直接进栈，如果栈不为空只有当当前运算符优先级高于栈顶运算符的优先级才直接进栈，否则依次出栈进入后缀表达式中，直到栈顶运算符优先级小于当前运算符优先级，然后入栈，遍历完后依次出栈进入后缀表达式中

若带有括号，左括号直接进栈，遇见右括号则出栈直到栈顶为左括号

迷宫：

。。。

队列

。。。

串

模式匹配

brute-force算法

暴力匹配，平均时间复杂度为O(nm)

KMP算法

。。。

图

树

有向递归结构

度(m)：节点的度为该节点子节点的个数，树的度为有最多子节点的节点的字节的个数，称为（树的度）次树
叶子：度为0
路径长度：经过分支数目
直接相连的：孩子，双亲，间接相连的：兄弟，一群的：子孙（直到叶子）、祖先（直到根节点）
层次：根节点为第一层
高度/深度(h)：最高层
有序/无序：兄弟节点是否有序
森林：无根节点的树
节点数(n)
“满”前缀：叶子集中在最高层

二叉树：度不大于2的树，严格区分左右子树

完全二叉树：满二叉树可以依次删去最高层最右侧的叶子

理论式

$节点数所有节点度数$

$层节点数$

$总节点数$

遍历顺序

先根：根、左节点、右节点
后根：左节点、右节点、根
层序：从上到下、从左到右

关系存储结构

双亲：根节点指向-1/?，其他节点指向其双亲节点，适于从下向上搜索
孩子：节点存储指向所有孩子节点的“指针”，适于从上向下搜素
孩子兄弟：节点存储指向该层的兄弟节点和下一层的孩子节点，适于将多次树转化为二叉树

查找

顺序查找

无哨兵是为 n

时间复杂度 O(n)

折半查找（有序表）

画为树计算，成功的用已有项，失败的用补充项，补充原则为已有项都要有两个孩子项其中 h(i) 代表已有项的层数， h(j) 代表补充项的层数

时间复杂度 O(log_2(n))

索引存储和分块查找

索引存储利用关键字排序快速查找，分块查找类似多级页表

分块查找中的顺序查找，选用分块最佳折半查找介于顺序查找和折半查找之间

二叉排列树

其平均查找长度随着树形态的不同而不同

处于 O(n) 与 O(log_2(n)) 之间

其计算方法与折半查找的相同

插入：比较递归

创建：建根节点并每个插入

查找：折半查找

删除一个节点：叶子直接删除，单孩子脱链，双孩子取左子树的最大叶子代替（复制数据）（右子树的最小叶子）；详细地说先查找对应点，使用双指针，一个指向节点一个指向其父节点，双孩子使用三指针

平衡二叉树

平衡因子：左子树高与右子树高之差，需要绝对值不大于 1

插入调整失衡：从新插入的节点向根节点查找第一个平衡因子不满足要求的节点A，失衡的原因是在 A 的左（右）子树 B 的左（右）子树 C 上插入节点，分为 LL/RR/LR/RL 调整，对于 LL/RR 调整，将节点 B 替换 A，A 作为 B 的右/左孩子，B 的右/左孩子作为 A 的左/右孩子；对于 LR/RL 调整，将 C 作为根节点，B/A 作为左孩子，A/B 作为右孩子，C 的左孩子作为 B/A 的右孩子，C 的右孩子作为 A/B 的左孩子

删除调整失衡：查找得到节点 x 的左（右）子树为空，则用右（左）孩子替换，然后删除 x，否则查找左右子树较高树，左子树高则取左子树最大节点 q 的数据赋值给 x，右子树高则取右子树最小节点 q 的数据赋值给 x，删除 q，无论是哪种情况，都删除了一个节点，记删除的节点为 q，然后从 q 向上遍历到根节点，判断所经过的节点是否都平衡，若不平衡则需调整，找到第一个失衡的节点 p ，若 q 在 p 的左子树中，则判断，p 的右子树高则做 RR 调整，左子树高则做 RL 调整，相等两种调整都可以，若 q 在 p 的右子树中，则判断，p 的右子树高则做 LR 调整，左子树高则做 LL 调整，相等两种调整都可以

查找的时间复杂度为 O(log_2(n))

红黑树

二叉排列树+外部节点，节点带有颜色属性，之羽红色和黑色两种属性

满足性质：

根节点和外部节点为黑色
红节点的孩子节点都是黑色节点
对于每个节点，由该节点到其子孙节点中的某个外部节点的所有路径上包含的黑色节点个数相同

插入、查找、删除的平均时间复杂度为O(log_2(n))

其左旋/右旋操作类似于RR/LL调整

其插入算法于二叉排列树相同，唯一需要添加的为颜色属性，插入前设置为红色，若插入到根节点则调整为黑色，若其父节点为红色，则有讨论

其叔叔节点为红色，则将祖父节点修改为红色，父节点和叔叔节点修改为黑色
插入到父节点的右节点，则取代父节点，将父节点改为自己的左孩子，变为情形3
插入到父节点的左节点，右旋（LL调整），此时的祖父节点（原来的父节点）变为黑色，此时的父节点和叔叔节点（原来的子节点和祖父节点）变为黑色，此时的字节点（原来的叔叔节点）不变（保持黑色）

B树

多叉树，根节点若不是叶子节点至少有两子树，每个最多含有 m 棵子树，最少含有棵子树，所有外部节点都在一层，外部节点也要计算层数

类似于二叉树，只不过在节点中不是简单的大于等于小于而是分类讨论

其查找的平均时间复杂度为 o(log_m(n))

插入：向节点的恰当位置中添加一个关键字，超过关键字最大个数则分裂，给回父节点，左右两侧分裂成新的两个子树，父节点也超过了则类似操作

删除：查找，若不是叶子层的，则取该关键字所在节点的子树中的小于并最靠近的关键字取代要删除的关键字的位置，删除子树中的关键字，依次操作，转换为删除叶子节点，删除后若能满足最小关键字限制，则直接删除，否则取右兄弟的最小节点独代父节点的一个关键字位置，将父节点的这个关键字移向该叶子，类似于左旋或者向左兄弟操作，如果两个兄弟都不可操作，则与右兄弟和父节点的一个关键字合并为一个大子树，这样操作若对父节点不满足要求，则一直向根节点操作直到符合要求（可能会使树的高度减少一层）

B+树

对于B树，n个关键字的节点有n+1个子树，对于B+树，n个关键字的节点有n个子树

B+树的非叶子节点只是一个索引结构，两个指针，一个指向根节点，一个指向叶子链的最小关键字，所有叶子链接成一个链表

B+树的关键字记录子树的最大关键字

操作与B树类似，删除时无需借节点和合并时无需调整父节点的索引

哈希表

哈希函数和哈希冲突

哈希性能：装填因子（0.6~0.9），哈希函数，解决哈希冲突

哈希函数构造：

直接定址法（加减常数）、除留余数法（求余，不大于哈希地址空间的素数效果较好）、数字分析法

哈希冲突解决：

开放地址法：后插入的元素查找剩余的空闲位置插入

线性探测法：向后挨个查找空闲位置（堆积现象）
平方探测法：加减整数平方查找

拉链法：同义词使用链表连接

线性探测法：结构加入探测次数域

线性探测法性能分析：其中 n 代表哈希表元素个数， m 代表哈希地址空间长度，cnt 指各个元素的探测次数，x 需要计算整个哈希地址空间长度，空闲的为 1，有元素的为 offsetto(null)+1

拉链法性能分析：

拉链法：结构加入指针域

其中 n 代表哈希表元素个数， m 代表哈希地址空间长度，ptridx 指各个元素在链中的位置，x 需要计算整个哈希地址空间的头节点链上元素节点个数

假设哈希函数是均匀的，有

	成功查找	不成功查找
线性探测法
平方探测法
拉链法

排序

这里指的“开头”“末尾”是泛指

稳定的：相同关键字经过排序后不改变相对次序
基于比较的排序算法最好的平均时间复杂度为

直接插入排序：分成有序/无序区，用无序区的开头元素挨个比较有序区元素查找插入位置后插入有序区

稳定，就地排序，正序、反序、平均

折半插入排序：分成有序/无序区，用无序区的开头元素折半查找插入位置后插入有序区

稳定，就地排序，（优于直接插入）平均

希尔排序：从开头向末尾遍历，向d个组轮流分发元素，对R[d]~R[n-1]进行各组内直接插入排序，然后减小d直到d=0

不稳定，就地排序，平均

冒泡排序：分成有序/无序区，用无序区的开头元素和有序区末尾元素进行关键字比较判断是否交换位置，交换则交换后再次先前比较，否则取无序区下一个元素比较

稳定，就地排序，（劣于直接插入）正序、反序、平均

快速排序：取待排序区域的一个元素进行排序（关键字大于的放于一侧，小于的放于一侧），然后分为两个区域递归进行直到没有元素或元素数为1

不稳定，就地排序，栈空间最优/最差/平均，时间复杂度最优/最差/平均（最差是有序的）排序算法描述如下：取开头元素存入临时变量作为基准，设置头尾指示器指向元素头和元素尾，从后向前遍历直到两指示器重合或找到比基准小的元素，将该元素赋值给头指示器指向的元素，然后自增头指示器，接着从前到后遍历直到两指示器重合或找到比基准大的元素，将该元素赋值给尾指示器指向的元素，然后自减尾指示器，重复直到两个指示器重合，然后将基准元素赋值给已经重合的两指示器指向的元素，返回指示器值

int sort(int R[], int s, int t){
	int temp = R[s];
	int i = s, j = t;
	while(i < j){
		while(i < j && temp <= R[j]){
			j--;
		}
		if(i < j){
			R[i] = R[j];
			i++;
		}
		while(i < j && temp >= R[i]){
			R[j] = R[i];
			j--;
		}
	}
	R[i] = temp;
	return i;
}

简单选择排序：从无序区两两比较选出一个关键字最小的排到有序区末尾