图-最小生成树

Prim 算法示例算法思想:代码import java.util.Scanner; public class main { static int Vnum=9; static int Map[][]=new int[Vnum][Vnum]; static int MAX=Integer.MAX_VALUE; public static void main(String[] args) { Scanner scanner=new Scanner(System.in); //初始化 for(int i=0;i<Vnum;i++) { for(int j=0;j<Vnum;j++) { if(i==j) { Map[i][j]=0; //(i,j)=0 } else { M...

红黑树学习笔记

红黑树特性(1)每个结点或者是黑色,或者是红色。(2)根结点是黑色。(3)每个叶子结点(NIL)是黑色。 (这里的NIL结点非空 结点,是一个实实在在的结点 用于删除的方便)(4)如果一个结点是红色的,则它的子结点必须是黑色的。(5)从一个结点到该节点的子孙节点的所有路径上包含相同数目的黑结点。简易说明:红黑树由黑高来和旋转操作置底向上来维护的。阅读建议:​ 1、读者储备二分搜索树的增删改和树的旋转知识。​ 2、更多细节希望去读《算法导论》此文章仅作为参考笔记。统一名称:​ PP: 为祖父结点​ P:为父结点​ Y:为叔结点​ Z:当前结点INSERT红黑树插入结点会影响到他的结构特性,所以分成三种情况来处理。情况1(P和Y结点为红色)当D插入了就违法了第4个特性,就需要把P结点和Y结点变黑色...

阅读jdk1.7的HashMap源码

首先一开头作者们已经注释了HashMap多线程执行是不安全的是不同步的,如果非要用线程去操作HashMap而且确保同步需要线程加锁或者Map m = Collections.synchronizedMap(new HashMap(...));HashMap底层是数组+链表,实例化不并不会马上去初始化数组,而是有添加数据时才会初始化为2次幂大小容量的数组。详见PUT函数的代码public static int highestOneBit(int i) { // HD, Figure 3-1 i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); return i - (i >>> 1); }Integer.highestOneBit 用于找一个接近n又小于等于n的二次幂数字 原理很简单,把二进制的低位都填充1 然后用高位减去低位即可获得2次幂的数。...

线段树(区间树)

什么是线段树线段树也称区间树,更多的用于查询数据区间的值。线段树和二分搜索树相似也是二叉树,但具体的现实是不一样的。线段树对于需要频繁动态更新和查询的数据是比普通算法是更有利。(当然lazy我暂时留个坑有空再填)时间复杂度查询修改普通算法O(1)O(n)线段树O(logn)O(logn)下方图以数值区间求和为例,每个节点的数值的和都平坦到子节点上。所以查询的时候只需要访问到区间节点就好了,而不需要每个值都访问。例如:数组A[0,1,2,3,4,5,6,7] 查询0到3的区间值,只需要访问到根节点的右子节点就可以拿到区间值。当然线段树不只是可以拿来做区间求和也可以拿来比较最大值或最小值等操作。线段树的构建样例图:用数组实现线段树用数组实现线段树需要用把它当作满二叉树存储。对于满二叉树h层一共有2^h-1个节点。最后一层(h-1) 有2^(h-1)个节点。如果n=2^k 只需要2n的空间,但是最坏的情况为n=2^k+1 所以需要开4n的空间 (右边高度比左边高度多1层)例子:计算区间值的和构建算法大概为从中间分开 为左右子节点。(同时计算或比较等操作)左子节点:父节点下标*2+1右子...

AVL树主要代码清单

/*返回树的高度*/ int GetHeight(SubTree T) { if (!T) return 0; else return T->height; } int Max(int a, int b) { return (a > b) ? a : b; } /*左子树的左边就要 往右转*/ SubTree LLRotate(SubTree T) { SubTree Tmp; Tmp = T; T = T->left; Tmp->left = T->right; T->right = Tmp; /*维护高度*/ Tmp->height = Max(GetHeight(Tmp->left), GetHeight(Tmp->right)) + 1; T->height = Max(GetHeight(T->left), GetHeight(T->right)) + 1; ret...