北京大学考研辅导班北大软微核算机考研专业课之数据规划考点
??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考研辅导班：北大软微cs研讨生招生简章解析及考研经历
发表评论