1、平衡二叉树的调整
平衡二叉树的定义：
任意的左右子树高度差的绝对值不超过1，将这样的二叉树称为平衡二叉树，二叉平衡树前提是一个二叉排序树。
平衡二叉树的插入：
二叉平衡树在插入或删除一个结点时，先检查该操作是否导致了树的不平衡，若是，则在该路径上查找最小的不平衡树，调节其平衡。
4种平衡调整如下(结点的数字仅作标记作用)：
①LL：右单旋转
②RR：左单旋转
③LR平衡旋转：先左后右
④RL平衡旋转：先右后左
平衡二叉树查找：平衡二叉树查找过程等同于二叉排序树相同，因此平衡二叉树查找长度不超过数的长度，及其平均查找长度为O(log2n)。
2、克鲁斯卡尔算法(Kruskal算法)求最小生成树
克鲁斯卡尔算法，从边的角度求网的最小生成树，时间复杂度为O(eloge)。和普里姆算法恰恰相反，更适合于求边稀疏的网的最小生成树。对于任意一个连通网的最小生成树来说，在要求总的权值最小的情况下，最直接的想法就是将连wh09608通网中的所有边按照权值大小进行升序排序，从小到大依次选择。由于最小生成树本身是一棵生成树，所以需要时刻满足以下两点：
生成树中任意顶点之间有且仅有一条通路，也就是说，生成树中不能存在回路；
对于具有 n 个顶点的连通网，其生成树中只能有 n-1 条边，这 n-1 条边连通着 n 个顶点。
连接 n 个顶点在不产生回路的情况下，只需要 n-1 条边。所以克鲁斯卡尔算法的具体思路是：将所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为：如果这个wh09608边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。
判断是否会产生回路的方法为：在初始状态下给每个顶点赋予不同的标记，对于遍历过程的每条边，其都有两个顶点，判断这两个顶点的标记是否一致，如果一致，说明它们本身就wh09608处在一棵树中，如果继续连接就会产生回路；如果不一致，说明它们之间还没有任何关系，可以连接。
假设遍历到一条由顶点 A 和 B 构成的边，而顶点 A 和顶点 B 标记不同，此时不仅需要将顶点 A 的标记更新为顶点 B 的标记，还需要更改所有和顶点 A 标记相同的顶点的标记，全部改为顶点 B 的标记。
图 1 连通网
例如，使用克鲁斯卡尔算法找图 1 的最小生成树的过程为：首先，在初始状态下，对各顶wh09608点赋予不同的标记(用颜色区别)，如下图所示：
(1)
对所有边按照权值的大小进行排序，按照从小到大的顺序进行判断，首先是(1，3)，由于顶点 1 和顶点 3 标记不同，所以可以构成生wh09608成树的一部分，遍历所有顶点，将与顶点 3 标记相同的全部更改为顶点 1 的标记，如(2)所示：
(2)
其次是(4，6)边，两顶点标记不同，所以可以构成生成树的一部分，更新所有顶点的标记为：
(3)
其次是(2，5)边，两顶点标记不同，可以构成生成树的一部分，更新所有顶点的标记为：
(4)
然后最小的是(3，6)边，两者标记不同，可以连接，遍历所有顶点，将与顶点 6 标记相同的所有顶点的标记更改为顶点 1 的标记：
(5)
继续选择权值最小的边，此时会发现，权值为 5 的边有 3 个，其中(1，4)和(3，4)各自两顶点的标记一样，如果连接会产wh09608生回路，所以舍去，而(2，3)标记不一样，可以选择，将所有与顶点 2 标记相同的顶点的标记全部改为同顶点 3 相同的标记：
(6)
当选取的边的数量相比与顶点的数量小 1 时，说明最小生成树已经生成。所以最终采用克鲁斯卡尔算法得到的最小生成树为(6)所示。
关注A研路考研考博工作室微博
定期更新考研资讯
北大考研辅导班：北大软微cs研究生招生简章解析及考研经验
举报/反馈
北大计算机考研辅导班 北京大学考研辅导班：北大软微计算机考研专业课之数据结构考点...
