DataStructure

Posted on Edited on

书写规范

先搞两个空的class：

1
2
class illegalSize {};
class outOfBound {};

然后每次申请空间时，如果失败就throw illegalSize()，如果发现越界，就throw outOfBound()。

比如说：

1
2
3
4
5
6
7
8
9
10
11
12
13
template<class elemType>
void seqList<elemType>::doubleSpace() {
    elemType* tmp = new elemType[2 * maxSize];
    if (!tmp) throw illigalSize();
    for (int i = 1; i <= len; ++i) {
        // len是有效数据长度
        tmp[i] = elem[i];
    }   
    delete[] elem;
    elem = tmp;
    maxSize = 2 * maxSize - 1;
    // 这里要-1，因为maxSize不算头节点
}

和

1
if (i < 1 || i > len) throw outOfBound();

线性表

定义：仅由元素相对位置关系确定元素间关系的数据结。

顺序表

  • elem: 数组名称
  • len: 元素个数（去掉哨兵位）
  • maxSize: 最大空间数（去掉哨兵位）

注意这个find函数喜欢从后往前，然后待查元素放a[0]。

完整代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#pragma once // seqList.hpp
#include "errorCode.hpp"

#define INITSIZE 128

template<class elemType>
class seqList {
private:
    elemType* elem;
    int len;
    int maxSize;
    void doubleSpace();
public:
    seqList(int size = INITSIZE);
    bool isEmpty() const;
    bool isFull() const;
    int length() const;
    elemType get(int i) const;
    int find(const elemType& e) const;
    void insert(int i, const elemType& e);
    void remove(int i, elemType& e);
    void clear();
    ~seqList();
};

// 模板实现必须在头文件中
template<class elemType>
void seqList<elemType>::doubleSpace() {
    int size = (maxSize + 1) * 2;
    elemType* tmp = new elemType[size];
    if (!tmp) throw illegalSize();
    for (int i = 1; i <= len; ++i) tmp[i] = elem[i];
    maxSize = size - 1;
    delete[] elem;
    elem = tmp;
}

template<class elemType>
seqList<elemType>::seqList(int size) {
    elem = new elemType[size];
    if (!elem) throw illegalSize();
    len = 0;
    maxSize = size - 1;
}

template<class elemType>
void seqList<elemType>::clear() {
    len = 0;
}

template<class elemType>
seqList<elemType>::~seqList() {
    delete[] elem;
}

template<class elemType>
int seqList<elemType>::find(const elemType& e) const {
    elem[0] = e;
    int i = len;
    for ( ; elem[i] != e; --i);
    return i;
}

template<class elemType>
elemType seqList<elemType>::get(int i) const {
    if (i > len || i < 1) throw outOfBound();
    return elem[i];
}

template<class elemType>
void seqList<elemType>::insert(int i, const elemType& e) {
    if (i < 1 || i > len + 1) throw outOfBound();
    if (isFull()) doubleSpace();
    ++len;
    for (int j = len; j > i; --j) elem[j] = elem[j - 1];
    elem[i] = e;
}

template<class elemType>
bool seqList<elemType>::isEmpty() const {
    return len == 0;
}

template<class elemType>
bool seqList<elemType>::isFull() const {
    return len == maxSize;
}

template<class elemType>
int seqList<elemType>::length() const {
    return len;
}

template<class elemType>
void seqList<elemType>::remove(int i, elemType& e) {
    if (i > len || i < 1) return;
    e = elem[i];
    for (; i < len; ++i) elem[i] = elem[i + 1];
    --len;
}

链表

单链表

会预留一个头节点，没有储存数据，而首节点指第一个节点。

一般来讲会搞一个叫做node的class，写两个构造函数，一个返回一个指向空节点的头节点，另一个返回一个指向某值，值为v的节点。

兄弟协同法：搞p和q两个节点，每次q指向p的下一个，然后把p删除，实现clear操作。

首席插入法：建一个空链表，每次把一个链表的首节点删了，插到另个链表的头上，实现逆序。

认为插入和删除单链表快，随机读取顺序表快。

完整代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#pragma once // linkList
#include "errorCode.hpp"

template <class elemType>
class linkList;
// 前向声明

template <class elemType>
class node {
    friend class linkList<elemType>;
private:
    elemType data;
    node* next;
public:
    node() : next(nullptr) {};
    node(const elemType& e, node* N = nullptr) {
        data = e;
        next = N;
    }
};

template <class elemType>
class linkList {
private:
    node<elemType>* head;
public:
    linkList();
    bool isEmpty() const;
    bool isFull() const;
    int length() const;
    elemType get(int i) const;
    int find(const elemType& e) const;
    void insert(int i, const elemType& e);
    void remove(int i, elemType& e);
    void reverse();
    void clear();
    ~linkList();
};

template<class elemType>
linkList<elemType>::linkList() : head(new node<elemType>()) {}

template<class elemType>
linkList<elemType>::~linkList() {
    clear(); delete head;
}

template<class elemType>
bool linkList<elemType>::isEmpty() const {
    return head->next == nullptr;
}

template<class elemType>
bool linkList<elemType>::isFull() const { return false; }

template<class elemType>
int linkList<elemType>::length() const {
    int cnt = 0;
    for (node<elemType>* p = head->next; p; p = p->next) ++cnt;
    return cnt;
}

template<class elemType>
elemType linkList<elemType>::get(int i) const {
    if (i < 1) throw outOfBound();
    node<elemType>* p;
    for (p = head; i > 0 && p; --i, p = p->next);
    if (!p) throw outOfBound();
    return p->data;
}

template<class elemType>
void linkList<elemType>::insert(int i, const elemType& e) {
    if (i < 1) throw outOfBound();
    node<elemType>* p = head;
    for (; i > 1 && p; --i, p = p->next);
    if (!p) throw outOfBound();
    p->next = new node<elemType>(e, p->next);
}

template<class elemType>
void linkList<elemType>::remove(int i, elemType& e) {
    if (i < 1) return;
    node<elemType>* p = head, *q = head->next;
    for (; i > 1 && q; --i, p = q, q = q->next);
    if (!q) return;
    p->next = q->next;
    e = q->data;
    delete q;
}

template<class elemType>
void linkList<elemType>::reverse() {
    node<elemType>* p = head->next;
    head->next = nullptr;
    while (p) {
        node<elemType>* q = p->next;
        p->next = head->next;
        head->next = p;
        p = q;
    }
}

template<class elemType>
void linkList<elemType>::clear() {
    while (head->next) {
        node<elemType>* p = head->next;
        head->next = p->next;
        delete p;
    }
}

template<class elemType>
int linkList<elemType>::find(const elemType& e) const {
    node<elemType>* p = head->next;
    for (int cnt = 1; p; p = p->next, ++cnt) {
        if (p->data == e) {
            return cnt;
        }
    }
    return 0;
}

循环链表

一般不带头节点。

空的单向循环链表，head指向空。

双向链表

一般会有头节点和尾节点，顺序为

1
头节点 <-> 首节点 <-> ... <-> 末节点 <-> 尾节点

指针名字一般叫做prior和next。

一元多项式

喜欢用单链表实现。

稀疏矩阵

会搞个这个结构体

1
2
3
4
struct triple {
    int row, col;
    int data;
}

栈和队列

栈

栈底（bottom）叫做栈的首部；

栈顶（top）叫做栈的尾部。

顺序栈

Bottom永远是00。

完整代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#pragma once // seqStack.hpp
#include "errorCode.hpp"

template<class elemType>
class seqStack {
private:
    elemType* array;
    int Top;
    int maxSize;
    void doubleSpace();
public:
    seqStack(int size = 100);
    bool isEmpty() const;
    bool isFull() const;
    elemType top() const;
    void push(const elemType& e);
    void pop();
    ~seqStack();
};

template<class elemType>
seqStack<elemType>::seqStack(int size) {
    array = new elemType[size];
    if (!array) throw illegalSize();
    Top = -1;
    maxSize = size;
}

template<class elemType>
seqStack<elemType>::~seqStack() {
    delete[] array;
}

template<class elemType>
bool seqStack<elemType>::isEmpty() const {
    return Top == -1;
}

template<class elemType>
bool seqStack<elemType>::isFull() const {
    return maxSize - 1 == Top;
}

template<class elemType>
void seqStack<elemType>::doubleSpace() {
    int size = maxSize * 2;
    elemType* tmp = new elemType[size];
    if (!tmp) throw illegalSize();
    for (int i = 0; i <= Top; ++i) tmp[i] = array[i];
    maxSize = size;
    delete[] array;
    array = tmp;
}

template<class elemType>
void seqStack<elemType>::push(const elemType& e) {
    if (isFull()) doubleSpace();
    array[++Top] = e;
}

template<class elemType>
void seqStack<elemType>::pop() {
    if (isEmpty()) throw outOfBound();
    --Top;
}

template<class elemType>
elemType seqStack<elemType>::top() const {
    if (isEmpty()) throw outOfBound();
    return array[Top];
}

链式栈

不需要头节点（因为不会在头上插入）。

定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template<class elemType>
class linkStack;

template<class elemType>
class Node {
friend class linkStack<elemType>;
private:
    elemType data;
    Node<elemType>* next;
public:
    Node() : next(nullptr) {};
    Node(const elemType& x, Node<elemType>* p = nullptr) : data(x), next(p) {}
};

template<class elemType>
class linkStack {
private:
    Node<elemType>* Top;
public:
    linkStack() : Top(nullptr) {}
    bool isEmpty() const { return !Top; }
    bool isFull() const { return false; }
    elemType top();
    void push(const elemType& e);
    void pop();
    ~linkStack();
};

实现懒得写了，和链表一样。

中缀式转后缀式

建一个栈，用于放操作符。

  • 如果读入数字，直接输出；
  • 如果读入操作符，如果栈非空且栈顶元素优先级≥\geq当前优先级（对于左结合运算符，如果像^这种右结合运算符则不取等），将栈顶元素出栈，重复，直到条件不满足，入栈。
  • 如果读入左括号，入栈；
  • 如果读入右括号，出栈直到左括号出栈。

转前缀式：先逆序，再后缀，再逆序。

队列

顺序队列

一开始Front = Rear = -1。

俺寻思Front = 0更方便，但是老师是这么写的。*

但是这样老师认为太浪费空间了，所以我们要用循环队列：

初始化：Front = Rear = 0。

如果发现元素太多了，就doubleSpace。

认为Front == Rear表示是空；

认为(Rear + 1) % maxSize == Front表示满（需要doubleSpace）。

主要操作：

1
2
3
void enQueue(const elemType& x);
void deQueue();
elemType front();

链式队列

一开始Front = Rear = NULL，不搞头尾节点。

如果!Rear那就要Front=Rear=...，否则Rear->next=..., Rear=Rea->next。

优先队列

用队列实现优先队列好像没什么卵用。

树

度：孩子节点个数；

层次：根节点为1；

二叉树

二叉树不是特别的树，是一个不同的结构，因为左右儿子是确定的。

满二叉树

节点数为2k−12^k - 1，其中kk为深度。

完全二叉树

节点数为[2k−1,2k−1][2^{k - 1}, 2^k - 1]，其中kk为深度。

二叉树的性质

n0=n2+1n_0 = n_2 + 1

证明：假设现在有一棵二叉树满足这个性质，那么作以下几种操作：

  1. 任取度为00的节点，给他插一个儿子，n0←n0n_0\leftarrow n_0, n1←n1+1n_1\leftarrow n_1 + 1, n2←n2n_2\leftarrow n_2，关系不变；
  2. 任取度为11的节点，插一个儿子：n0←n0+1n_0\leftarrow n_0 + 1, n1←n1−1n_1\leftarrow n_1 - 1, n2←n2+1n_2\leftarrow n_2 + 1，关系不变。

而一个节点的二叉树满足n0=n2+1n_0 = n_2 + 1，任意一个二叉树都可以使用以上两个步骤得到，所以命题成立。

nn个节点的完全二叉树高度为⌊log⁡n⌋+1\lfloor\log n\rfloor + 1.

二叉树存储

  1. 顺序存储：a[0]空着，根节点在11。
  2. 链式存储：左右儿子。

二叉树遍历

需要掌握非递归

二叉线索树

一般是中序，没有左/右儿子就连前驱/后继。

树和森林

用孩子兄弟表示法

树的遍历

先根遍历：先遍历根节点，再从左到右遍历所有子树；
中根遍历：由于存在多个孩子，不能规定根的顺序，不存在；
后根遍历：先遍历所有子树，再遍历根节点。

观察孩子兄弟表示法，发现先根遍历对应了前序遍历；后根遍历对应了中序遍历。

知道这两个遍历可以唯一确定一棵树。

森林的遍历

森林的先序遍历：先根遍历第一个根节点，再第二个。。。；
森林的中序遍历：后根遍历第一个根节点，再第二个。。。；

森林的先序遍历是前序遍历，中序遍历是中序遍历。

优先级队列

堆

最优二叉树

哈夫曼算法：每次找到最小的两个合并。

储存：用顺序储存，但是有parent数组（实际上就是链式储存），预留n−1n-1个空间，a[1-n-1]放合并节点，a[n-2n-1]放原始节点。

表达式树

根节点为数，其他为运算符。

等价关系

并查集

union(si, sj)：合并si和sj；
find(x): 找到x所属的不相交集。

图

存储

邻接矩阵

1可达0不可达

邻接表

next指向下一条边；

多重邻接表

无向图，一个边用一个节点，指向两个点。

有ver1, ver2表示边连的两个点；link1，link2表示，ver1和ver2的下一条边。

十字链表

把邻接表和逆邻接表搞在一起，

有v1,v2，表示来的点和去的点；
out指向v1出发的下一条边，in指向到v1的下一条反边。边表也要开两个，存第一条反边和正边。

遍历

深度优先遍历和广度优先遍历。都要求非递归（煞笔）。

连通性

无向图

遍历

有向图

强连通分量的kosaraju法：

遍历1. 先深度优先后序遍历所有节点，给每个节点一个编号（先出栈先编号）；
遍历2. 再建反图，在反图上从编号大的往编号小的遍历。此时一次遍历能到达的所有点都构成强连通分量。

证明：考虑遍历2的搜索树，假设节点xx为搜索树的根节点，则根据算法有v(x)>v(y), ∀y∈TREE(x)v(x) > v(y),\,\forall y\in\text{TREE}(x)，其中vv表示节点的编号。且此时，所有yy都可以到达xx，现在来证明所有xx也可以到达yy。

假设xx不可以到达yy，但是yy可以到达xx，所以在遍历1一定是先遍历了xx再遍历了yy（两次不同遍历），那么一定有v(y)>v(x)v(y)>v(x)，矛盾，所以xx一定可以到达yy。

对于遍历2的第一次遍历，xx一定可以找到所有能到达自己的yy，所以这是一个极大强连通分量；对于后续的遍历，由于极大强连通分量不能相交，所以也是极大的。

欧拉回路

记得走完把边删掉

AOE和AOV

AOV：顶点表示活动，边表示活动之间的先修关系；
AOE：边表示活动，节点表示某一个状态。

AOV用拓扑排序；
AOE一般有起点和终点，从起点开始按拓扑序遍历，

节点的最早发生时间：前序边都完成的最晚时间；
节点的最晚发生时间：最晚的且不影响终点发生时间的发生时间。

第一次遍历可以求出最早发生时间，第二次倒着遍历就可以求出所有的最晚发生时间。

边的最早时间是发出点的最早时间，最晚时间是到达点的最晚时间减去边权。

最小代价生成树

prim和kruscal

最短路径

dijkstra和floyd

查找

静态查找

顺序查找

折半查找

二分

插值查找

均匀分布，直接算

分块查找

块中无序，块间有序

动态查找

二叉查找树

非递归

插入：搜索到空节点，直接插；
删除：搜索到指定节点，如果只有一个儿子，直接删掉，把儿子拿上来；否则需要到左儿子，然后一直往右找（找到前驱），把前驱提到自己位置，然后把前驱删了。

顺序统计

在二叉查找树找第kk大

平衡二叉查找树

AVL：两个字节点高度差为0或1.

放一个之前写的，重点看什么时候怎么转。

删除也是一样，需要找一个前驱，然后把前驱删了，删了之后从被删的节点往上maintainBalance。

Show More 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
#include <cstdlib>
#include <algorithm>
#include <iostream>

class AVL_Tree {
private:
    const static int INF = 1e7 + 1;
    struct Node {
        int val;
        int cnt;
        int sum;
        int h;
        Node* ls;
        Node* rs;
        static Node& emptyNode() {
            static Node empty_node;
            return empty_node;
        }
        Node(int _val) : val(_val), cnt(1), sum(1), h(1), ls(&emptyNode()), rs(&emptyNode()) {}
        Node() : val(0), cnt(0), sum(0), h(0) {ls=this, rs=this;}
        bool empty() {
            return h == 0;
        }
    };
    Node* root;
    void maintain(Node*& u) {
        if (u->empty()) return;
        u->h = std::max(u->ls->h, u->rs->h) + 1;
        u->sum = u->ls->sum + u->rs->sum + u->cnt;
    }
    void rotateRight(Node*& u) {
        if (u->ls->empty()) return;
        Node* s = u->ls;
        u->ls = s->rs;
        s->rs = u;
        maintain(u);
        maintain(s);
        u = s;
    }/*
        u          s
       / \        / \
      s   c  ->  a   u
     / \            / \  
    a   b          b   c
    */
    void rotateLeft(Node*& u) {
        if (u->rs->empty()) return;
        Node* s = u->rs;
        u->rs = s->ls;
        s->ls = u;
        maintain(u);
        maintain(s);
        u = s;
    }
    void maintainBalance(Node*& u) {
        if (u->empty()) return;
        if (u->ls->h - u->rs->h == 2) {
            if (u->ls->ls->h > u->ls->rs->h) {
                rotateRight(u);
            } else {
                rotateLeft(u->ls);
                rotateRight(u);
            }
        } else if (u->rs->h - u->ls->h == 2) {
            if (u->rs->rs->h > u->rs->ls->h) {
                rotateLeft(u);
            } else {
                rotateRight(u->rs);
                rotateLeft(u);
            }
        }
    }
    void add(Node*& u, int x) {
        u->cnt += x;
        u->sum += x;
    }
    void Insert(Node*& u, int val) {
        if (u->empty()) return u = new Node(val), void();
        if (val == u->val) {
            ++u->cnt;
        } else if (val < u->val) {
            Insert(u->ls, val);
        } else {
            Insert(u->rs, val);
        }
        maintain(u);
        maintainBalance(u);
        // printf("Insert::u->val = %d, u->ls = %d, u->rs = %d\n", u->val, u->ls->val, u->rs->val);
    }
    void Delete(Node*& u, int val) {
        if (u->empty()) return;
        if (val == u->val) {
            if (u->cnt > 1) {
                --u->cnt;
            } else if (u->ls->empty()) {
                u = u->rs;
            } else if (u->rs->empty()) {
                u = u->ls;
            } else {
                Node* s = u->rs;
                while (!s->ls->empty()) {
                    s = s->ls;
                }
                u->cnt = s->cnt;
                u->val = s->val;
                s->cnt = 1;
                Delete(u->rs, s->val);
            }
        } else if (val < u->val) {
            Delete(u->ls, val);
        } else {
            Delete(u->rs, val);
        }
        maintain(u);
        maintainBalance(u);
    }
    int Rank(Node*& u, int val) {
        if (u->empty()) return 1;
        if (val == u->val) {
            return u->ls->sum + 1;
        } else if (val < u->val) {
            return Rank(u->ls, val);
        } else {
            return u->ls->sum + u->cnt + Rank(u->rs, val);
        }
    }
    int Findk(Node*& u, int k) {
        if (u->empty()) return -1;
        if (k >= u->ls->sum + 1 && k <= u->ls->sum + u->cnt) {
            return u->val;
        } else if (k < u->ls->sum + 1) {
            return Findk(u->ls, k);
        } else {
            return Findk(u->rs, k - u->ls->sum - u->cnt);
        }
    }
    int Pre(Node*& u, int val) {
        if (u->empty()) return -INF;
        if (val <= u->val) {
            return Pre(u->ls, val);
        } else {
            return std::max(Pre(u->rs, val), u->val);
        }
    }
    int Post(Node*& u, int val) {
        if (u->empty()) return INF;
        if (val >= u->val) {
            return Post(u->rs, val);
        } else {
            return std::min(Post(u->ls, val), u->val);
        }
    }
    void PrintTree(Node*& u) {
        if (u->empty()) return;
        printf("u->val = %d, u->sum = %d, u->cnt = %d, u->h = %d, ls = %d, rs = %d\n", u->val, u->sum, u->cnt, u->h, u->ls->val, u->rs->val);
        PrintTree(u->ls);
        PrintTree(u->rs);
    }
public:
    AVL_Tree() : root(&Node::emptyNode()) {}
    void Insert(int val) {
        Insert(root, val);
    }
    void Delete(int val) {
        Delete(root, val);
    }
    int Rank(int val) {
        return Rank(root, val);
    }
    int Findk(int k) {
        return Findk(root, k);
    }
    int Pre(int val) {
        return Pre(root, val);
    }
    int Post(int val) {
        return Post(root, val);
    }
    void PrintTree() {
        PrintTree(root);
    }
};

int main() {
    AVL_Tree t;
    int n; std::cin >> n;
    int count = 0;
    for (int i = 1; i <= n; ++i) {
        int op, x; std::cin >> op >> x;
        if (op >= 3) ++count;
        if (op == 1) {
            t.Insert(x);
        } else if (op == 2) {
            t.Delete(x);
        } else if (op == 3) {
            std::cout << t.Rank(x) << std::endl;
        } else if (op == 4) {
            std::cout << t.Findk(x) << std::endl;
        } else if (op == 5) {
            std::cout << t.Pre(x) << std::endl;
        } else if (op == 6) {
            std::cout << t.Post(x) << std::endl;
        }
        // if (count == 7) t.PrintTree(), std::cerr << "COUNT = " << count << ", op = " << op << ", x = " << x << std::endl;
        // t.PrintTree();
    }
    return 0;
}/*
10
1 2
1 1
1 4
1 5
1 3
2 4
6 1
6 2
6 3
6 4
*/

红黑树

以后说

外部查找

B树和B+树

B树

平衡MM叉查找树

根节点至少2个儿子，至多MM个儿子；
非根非叶子结点至少⌈M/2⌉\lceil M/2\rceil个儿子，至多MM个儿子。

nn个关键字会对应n+1n+1个儿子（nn个小于号连接n+1n+1个数），所以MM阶B树最多MM个儿子、M−1M-1个关键字。

叶子节点没有任何信息，关键字就是答案。

每个叶子节点的深度相同。

插入方法

找到最后一层，插入，如果没有满，插入结束；

如果满了，也就是说这一层有了MM个关键字，把中间的关键字（第⌈M/2⌉\lceil M/2\rceil个）插入父节点，同时分裂成两个子树（每个子树的关键字数≥⌊(M−1)/2⌋≥⌈M/2⌉−1\geq\lfloor (M-1)/2\rfloor \geq \lceil M/2\rceil - 1，是合法的）继续到父节点判断。如果到根节点也炸了，就把中间关键字上提成为新的根节点。

删除方法：

最后一层：

  1. 如果够多，直接删；
  2. 如果不够了，兄弟有多的，借一个（转过来）；
  3. 如果都没多的，合并，把上层关键字也扯下来，继续在上一层判断；

不是最后一层：

找到前驱，交换，然后把前驱删了（使用最后一层的删除方法递归删除）。

如果删到根了：

把根丢了，儿子当根。

B+树

只有叶子储存信息。

叶子最多LL个数据，最少⌈L/2⌉\lceil L/2\rceil个数据。一般LL会比MM小。

有些B+树关键字和子节点数相同（小于等于某个关键字的去某个字节点）。

哈希

把nn个数据映射到0,1,⋯ ,m−10, 1, \cdots, m - 1这mm个数，负载因子δ=n/m\delta = n/m。

闭哈希表：全部存在hash表里面；

开哈希表：可能额外开空间。

线性探测法：如果xx位置不行，就x+1,x+2⋯x+1, x+2\cdots；

二次探测法：如果xx位置不行，就x+12,x+22⋯x+1^2, x+2^2\cdots；

这些方法时，hash需要标识某个位置的状态：

  1. 没有数据
  2. 有数据
  3. 曾经有，但是删掉了

有2的原因是删掉了之后你查找还是得跨过去，否则就找不到了。

定期整理：把状态为11的重新搞一遍，彻底消除状态为22的。

链地址法：开哈希表

排序

内排序

冒泡

冒泡儿，，稳定。

插入

从后往前遍历，如果大就往后挪，如果小就break，插入。稳定。

希尔

从stepsize = n/2开始，每次stepsize/2，每一轮要做以下事情：

假设当前stepsize=t，那么

  1. 从0,1,⋯ ,t−10, 1, \cdots, t-1开始，构成t−1t-1个不同的子序列。
  2. 对这些子序列进行插入排序。

stepsize=1时终止。此时应该可以排好。

不稳定。

选择

每次把最小值和当前位置交换。

不稳定。因为有可能交换时把本身在前面的数放到后面去。

如果一个一个往后挪就稳定了。

堆

不稳定。

归并

稳定。

快速

把第一个元素a1取出来，并把hole设为start。目标是最后的hole左边都是小于a1的，右边都是大于等于a1的。

i指向hole的下一个，j指向end，每次先动j，只要找到一个小于a1的元素，就和hole交换，然后动i。这样最后就一定是hole在中间，左右是对的。

不稳定。

基数排序

从低优先级到高优先级进行桶排序。稳定。

外排序

kk路归并

kk路归并的意思是，kk个磁带上都写有很多段有序序列，要最终归并成一段有序序列。

比如说有A,B,CA, B, C三个磁带，写到D,E,FD, E, F上，那么会把A,B,CA,B,C的第一段归并好写到DD上，第二段归并好写到EE上。。。第四段再写到DD上，以此类推，然后再反过来用D,E,FD,E,F归并到A,B,CA,B,C。

多阶段归并

假设只有k+1k+1个磁带，第k+1k+1个为空，那么可以先kk路合并到k+1k+1个上直到前kk个中某一个为空，此时就可以往那个空的里面继续kk路合并…

按照斐波那契分布归并序列数量最优。

置换选择

假设你的内存只能存m个，那么你就存m个，每次要爆了把最小值输出来（用堆维护）；如果来了个比最小值还小的就清空内存。

最佳归并树

小的优先（和哈夫曼策略相同）。