第二章 初出茅庐——初级篇：数据结构与图论

本章涉及的两个主题都与结构化有着莫大联系。

加工并存储数据的数据结构

作者给出的定义非常贴切：
数据结构是存储数据的方式，按照不同的方式存储数据，可以对数据做不同的高效操作。
下面按照二叉搜索树、满二叉堆和并查集的顺序对各结构和相关习题进行介绍，由于我数据结构掌握地相对好一些，就不做较为初级的科普了

二叉搜索树

“二叉树”是大学课程中继“链表”后会学习的第二个数据结构，它和链表都是一类递归的结构，即节点本身包含节点的指针：

struct node {
	int val;
	node *lch, *rch;
};

另外二叉树与图结构中的树不一样，它有利于高效地进行查找；为了防止随着特殊数据的插入导致结构“链化”，查找效率降低，在此基础上还衍生出了各类自平衡二叉树结构：红黑树、Splay树、Treap树和替罪羊树等等；这些结构能通过旋转或者其他骚操作让二叉树的查找插入删除维持在\(O(logn)\)的复杂度内

书中给出的就是普通二叉树实现一个无重复元素的集合的例子，重点放在insert、find和remove操作的实现上；

1. 查找操作：从根节点开始对比当前节点的值\(val\)和要查找的值\(x\)，\(x < val\)时向当前节点的\(lch\)查找，\(x > val\)时向当前节点的\(rch\)查找；可用循环或递归实现，重复以上操作直到遇到一个节点的\(val = x\)，或转移到一个\(NULL\)为止；
2. 插入操作：与查找操作类似，只不过我们需要额外维护当前位置的父节点，在找到\(x\)在树中所处的位置(一个不存在的虚拟节点)后，新建一个节点存入值\(x\)，并在回溯的时候添加到其父节点上；
3. 删除操作：删除的前提是\(x\)存在，因此删除操作包含了查找操作；当把对应位置的节点\(p\)删除后，根据剩下结构需要分类讨论：1)如果\(p\)没有儿子(即\(p\)是个叶子结点)则直接返回；2)如果\(p\)只有一个儿子，则把这个儿子提到\(p\)的位置；3)如果\(p\)有两个儿子，则剩下三部分，我们需要找到一个节点\(o\)满足大于左子树所有节点的值，小于右子树所有节点的值；这个值只有两个，分别是左子树的最大值和右子树的最小值，这两个值对应的一定是叶子节点，因此摘除后不需要另考虑连接的逻辑，将这个节点提到对应p的位置即可；

bool find(node *p, int x) {
	if(p == NULL) return false;
	else if(x == p->val) return true;
	else if(x < p->val) return find(p->lch, x);
	else return find(p->rch, x);
}

node* insert(node *p, int x) {
	if(p == NULL) {
		node *q = new node;
		q->val = x;
		q->lch = q->rch = NULL;
		return q;
	}
	if(p->val == x) return p;
	else if(x < p->val) p->lch = insert(p->lch, x);
	else p->rch = insert(p->rch, x);
	return p;
}

node* remove(node *p, int x) {
	if(p == NULL) return NULL;
	else if(x < p->val) p->lch = remove(p->lch, x);
	else if(x > p->val) p->rch = remove(p->rch, x);
	else if(p->lch == NULL) {
		node *q = p->rch;
		delete p;
		return q;
	} else if(p->lch->rch == NULL) {
		node *q = p->lch;
		q->rch = p->rch;
		delete p;
		return q;
	} else {
		node *q;
		for(q = p->lch; q->rch->rch != NULL; q = q->rch);
		node *r = q->rch;
		q->rch = r->lch;
		r->lch = p->lch;
		r->rch = p->rch;
		delete p;
		return r;
	}
	return p;
}

满二叉堆和优先队列

并查集