并查集：
第六章：图 第一部分 图的表示 邻接矩阵
邻接表：每个顶点有一个链表，链表储存了他的相邻接点（出度）
也可用数组的方式来表示，一个数组A[]表示点，A[1]表示A的第一个相邻接点，一个数组B[]表示A[]中每个点的临界点个数，比如B[N]表示A[N]的临界点个数，然后提取A[N]相邻接点信息时可以这样做： IF (B[I++] != -1) A[B[I]] ......
第二部分：BFS广度优先搜索
用一个队列来维护，与二叉树层次遍历相似，先入队的先出队操作，对其进行相邻边搜索，并且对未标记的邻接点标记。
*BFS搜索从S->A点的路径是最短路径（等权图下）
第三部分：DFS深度优先搜索
任意找一个点，随机找一个邻接点然后访问，随后递归地进行访问（即随机访问目前点的下一个相邻点），知道访问不能（没有相邻点或者所有相邻点都已被访问，做了标记），然后一步一步退回，直到当前节点还有其他相邻点未被访问，那么继续向内扩展。
第七章：二叉搜索树 (BST)
优点：既是列表的列表（二叉树），又体现了向量的优点。
循关键码访问：对数据项的访问通过关键码，关键码之间可以比较大小(将词条中比较操作重载）。
有序性：对一个节点，左子树每个节点都不比他关键码大，对称地，右边子树每个元素不都比他的关键码小。
对BST做中序遍历，必然是单调非降序列。 只需要考察所有节点的垂直投影：
只要垂直投影单调非降，则满足BST
接口：可以直接从bintree派生而来 只需要派生查找、插入、删除三个接口。
BST的查找：
查找类似于二分查找，对于关键码，如果大于则走右孩子，小于则走左孩子，直到找到或者没找到。此时返回一个节点，并且将此节点的父节点也存起来，方便后面的插入操作。o(logn)
BST的插入：
BST的删除：
1.最简单的情况：没有左子树或者右子树
此时可以直接将左节点或者右结点与要删除的节点交换，对于没有左右结点的节点，可以通过配置哨兵的方式来同样以此实现。
2.复杂的情况：双结点
对于双节点，可以先找到这个节点的直接后继（即按照中序遍历向后第一个节点），它的直接后继一定是比它大的最小元素，因此可以与之进行交换，交换后待删除结点一定是没有节点或者只有右结点的情况，就可以转到情况1 进行操作。
反思：注意不同结构、不同思路之间的融会贯通以及转换。
反思2: 任何复杂的问题都是由简到繁进行解答的，而且繁琐的方面一般都是由简单的解法组合变换而成的。因此要从简单入手，逐步解决。
平衡性与等价性测量：
对于n个互异的数，一共有catelan(N)种情况，其高度平均为根号N
如何达到理想平衡（高度最低）？ 兄弟子树高度越接近，高度越低。
引理：由n个结点组成的二叉树，其高度不低于log2N（理想平衡）
高度渐进地不超过logn——适度平衡，渐进意义上的理想高度——平衡二叉搜索树（BBST）。
等价BST：不同的二叉搜索树可以对应相同的中序遍历序列。 如何等价？两个原则：上下可变，左右不乱。
等价变换：
第一类：ZIG （顺时针）