数据结构5、二叉排序树5.1、插入操作5.2、删除操作5.3、查找操作5.4、用Java实现二叉排序树6、红黑树6.1、红黑树的特性6.2、红黑树的左旋6.3、红黑树的右旋6.4、红黑树的添加6.5、红黑树的删除7、图7.1、无向图和有向图7.2、图的存储结构邻接矩阵7.2.1、无向图的邻接矩阵7.2.2、有向图的邻接矩阵7.2.3、带权重图的邻接矩阵7.3、图的存储结构邻接表7.3.1、无向图的邻接表结构7.3.2、带权值的网图连接表结构7.4、图的遍历7.4.1、广度优先遍历7.4.2、深度优先遍历8、位图8.1、位图的数据结构8.2、位图的Java实现8.2.1、数据结构的定义8.2.2、查询方法的实现8.2.3、修改方法的实现5、二叉排序树二叉排序树Binary Sort Tree又称二叉查找树Binary Search Tree或二叉搜索树。二叉排序树为满足以下条件的树若左子树不空则左子树上所有节点的值均小于它的根节点的值若右子树不空则右子树上所有节点的值均大于或等于它的根节点的值左、右子树也分别为二叉排序树。如图4-10所示便是一个二叉排序树。5.1、插入操作在二叉排序树中进行插入操作时只需找到待插入的父节点将数据插入即可具体流程如下。1将待插入的新节点与当前节点进行比较如果两个节点的值相同则表示新节点已经存在于二叉排序树中直接返回false。2将待插入的新节点与当前节点进行比较如果待插入的新节点的值小于当前节点的值则在当前节点的左子树中寻找直到左子树为空则当前节点为要找的父节点将新节点插入当前节点的左子树即可。3将待插入的新节点与当前节点进行比较如果待插入的新节点的值大于当前节点的值则在当前节点的右子树中寻找直到右子树为空则当前节点为要找的父节点将新节点插入当前节点的右子树即可。具体的插入流程如图所示。5.2、删除操作二叉排序树的删除操作主要分为三种情况待删除的节点没有子节点待删除的节点只有一个子节点待删除的节点有两个子节点。具体情况如下。1在待删除的节点没有子节点时直接删除该节点即在其父节点中将其对应的子节点置空即可。如图所示要删除的节点14没有子节点则直接将其删除即可。2在待删除的节点只有一个子节点时使用子节点替换当前节点然后删除该节点即可。如图所示要删除的节点5有一个子节点8则使用子节点8替换需要删除的节点5然后删除节点5的数据即可。3在待删除的节点有两个子节点时首先查找该节点的替换节点替换节点为左子树中的最大节点或者右子树中的最小节点然后替换待删除的节点为替换节点最后删除替换节点。如图所示要删除的节点4有两个子节点其左子树最小的节点为2其右子树最小的节点为5因此有两种结果。5.3、查找操作二叉排序树的查找方式和效率接近二分查找法因此可以很容易获取最大最右最深子节点值和最小最左最深子节点值具体的查找流程为将要查找的数据与根节点的值进行比较如果相等就返回如果小于就到左子树中递归查找如果大于就到右子树中递归查找。5.4、用Java实现二叉排序树1定义二叉排序树的数据结构publicclassNode{privateintvalue;privateNodeleft;privateNoderight;publicNode(){}publicNode(Nodeleft,Noderight,intvalue){this.leftleft;this.rightright;this.valuevalue;}publicNode(intvalue){this(null,null,value);}publicNodegetLeft(){returnthis.left;}publicvoidsetLeft(Nodeleft){this.leftleft;}publicNodegetRight(){returnthis.right;}publicvoidsetRight(Noderight){this.rightright;}publicintgetValue(){returnthis.value;}publicvoidsetValue(intvalue){this.valuevalue;}}如上代码定义了二叉排序树的数据结构Node在Node中包含的value、left、right分别表示二叉排序树的值、左子节点、右子节点。2定义二叉排序树的插入方法/向二叉排序树中插入节点/publicvoidinsertBST(intkey){Nodeproot;/记录查找节点的前一个节点/Nodeprevnull;/一直查找下去直到到达满足条件的节点位置/while(p!null){prevp;if(keyp.getValue())pp.getLeft();elseif(keyp.getValue())pp.getRight();elsereturn;}/prev是待插入节点的父节点根据节点值的大小被插入相应的位置/if(rootnull)rootnewNode(key);elseif(keyprev.getValue())prev.setLeft(newNode(key));elseprev.setRight(newNode(key));}如上代码定义了insertBST()来向二叉排序树中插入节点具体操作分4步①循环查找需要插入的节点prev; ②如果二叉树的根节点为null则说明二叉树是空树直接将该节点设置为根节点③如果待插入的数据小于该节点的值则将其插入该节点的左节点④如果待插入的数据大于该节点的值则将其插入该节点的右节点。3定义二叉排序树的删除方法/ 删除二叉排序树中的节点 分为三种情况删除节点为p 其父节点为f 1要删除的p节点是叶子节点只需要修改它的双亲节点的指针为空 2若p只有左子树或者只有右子树则直接让左子树或右子树代替p 3若p既有左子树又有右子树 则用p左子树中最大的值即最右端S代替P删除s重接其左子树 /publicvoiddeleteBST(intkey){deleteBST(root,key);}privatebooleandeleteBST(Nodenode,intkey){if(nodenull)returnfalse;else{if(keynode.getValue()){returndelete(node);}elseif(keynode.getValue()){returndeleteBST(node.getLeft(),key);}else{returndeleteBST(node.getRight(),key);}}}privatebooleandelete(Nodenode){Nodetempnull;/右子树空只需要重接它的左子树 如果是叶子节点则在这里也把叶子节点删除了 /if(node.getRight()null){tempnode;nodenode.getLeft();}/左子树空 重接它的右子树/elseif(node.getLeft()null){tempnode;nodenode.getRight();}/左右子树均不为空/else{tempnode;Nodesnode;/转向左子树然后向右走到“尽头”/ss.getLeft();while(s.getRight()!null){temps;ss.getRight();}node.setValue(s.getValue());if(temp!node){temp.setRight(s.getLeft());}else{temp.setLeft(s.getLeft());}}returntrue;}以上代码通过三种方法实现了二叉树的删除deleteBST(int key)是提供给用户的删除方法会调用deleteBST(Node node, int key)其中Node参数为根节点表示从根节点开始递归查找和删除deleteBST(Node node, int key)通过递归查找找到要删除的节点。查找要删除的节点的具体做法如下。如果key和当前节点的值相等则说明找到了需要删除的节点。如果key小于当前节点的值则在左子树中查找。如果key大于当前节点的值则在右子树中查找。在找到要删除的节点后调用delete(Node node)删除该节点这里的删除分3种情况。如果右子树为空则只需将它的左子树接到该节点。如果右子树为空则只需将它的右子树接到该节点。如果左右子树均不为空则需要在左子树中寻找最小的节点并将左子树中最小的节点接到当前节点。4定义二叉排序树的查询方法/查找在二叉排序树中是否有key值/publicbooleansearchBST(intkey){Nodecurrentroot;while(current!null){//等于当前值则查找成功返回if(keycurrent.getValue())returntrue;//比当前值小进入左子树中查找elseif(keycurrent.getValue())currentcurrent.getLeft();else//比当前值大进入右子树中查找currentcurrent.getRight();}returnfalse;}以上代码定义了searchBST()用于查询二叉排序树具体做法如下。如果key和当前节点的值相等则说明找到了该节点。如果key小于当前节点的值则在左子树中查找。如果key大于当前节点的值则在右子树中查找。6、红黑树红黑树Red-Black Tree, R-B Tree是一种自平衡的二叉查找树。在红黑树的每个节点上都多出一个存储位表示节点的颜色颜色只能是红Red或者黑Black。6.1、红黑树的特性红黑树的特性如下。每个节点或者是黑色的或者是红色的。根节点是黑色的。每个叶子节点NIL都是黑色的。如果一个节点是红色的则它的子节点必须是黑色的。从一个节点到该节点的子孙节点的所有路径上都包含相同数量的黑色节点。具体的数据结构如图所示。6.2、红黑树的左旋对a节点进行左旋指将a节点的右子节点设为a节点的父节点即将a节点变成一个左节点。因此左旋意味着被旋转的节点将变成一个左节点具体流程如图所示。6.3、红黑树的右旋对b节点进行右旋指将b节点的左子节点设为b节点的父节点即将b节点设为一个右节点。因此右旋意味着被旋转的节点将变成一个右节点具体流程如图所示。6.4、红黑树的添加红黑树的添加分为3步①将红黑树看作一颗二叉查找树并以二叉树的插入规则插入新节点②将插入的节点涂为“红色”或“黑色”; ③通过左旋、右旋或着色操作使之重新成为一颗红黑树。根据被插入的节点的父节点的情况可以将具体的插入分为3种情况来处理。如果被插入的节点是根节点则直接把此节点涂为黑色的。如果被插入的节点的父节点是黑色的则什么也不需要做在节点插入后仍然是红黑树。如果被插入的节点的父节点是红色的则在被插入节点的父节点是红色的时被插入节点一定存在非空祖父节点即被插入节点也一定存在叔叔节点即使叔叔节点叔叔节点指当前节点的祖父节点的另一个子节点为空我们也视之为存在空节点本身就是黑色节点。然后根据叔叔节点的颜色在被插入节点的父节点是红色的时进一步分为3种情况来处理。如果当前节点的父节点是红色的当前节点的叔叔节点是红色的则将父节点设为黑色的将叔叔节点设为黑色的将祖父节点设为红色的将祖父节点设为当前节点。如果当前节点的父节点是红色的当前节点的叔叔节点是黑色的且当前节点是右节点则将父节点设为当前节点以新节点为支点左旋。如果当前节点的父节点是红色的当前节点的叔叔节点是黑色的且当前节点是左节点则将父节点设为黑色的将祖父节点设为红色的以祖父节点为支点右旋。6.5、红黑树的删除红黑树的删除分为两步①将红黑树看作一颗二叉查找树根据二叉查找树的删除规则删除节点②通过左旋、旋转、重新着色操作进行树修正使之重新成为一棵红黑树具体操作如下。将红黑树看作一颗二叉查找树将节点删除。如果被删除的节点没有子节点那么直接将该节点删除。如果被删除的节点只有一个子节点那么直接删除该节点并用该节点的唯一子节点替换该节点的位置。如果被删除的节点有两个子节点那么先找出该节点的替换节点然后把替换节点的数据复制给该节点的数据之后删除替换节点。通过左旋、旋转、重新着色操作进行树修正使之重新成为一棵红黑树因为红黑树在删除节点后可能会违背红黑树的特性所以需要通过旋转和重新着色来修正该树使之重新成为一棵红黑树①如果当前节点的子节点是“红黑”节点则直接把该节点设为黑色的②如果当前节点的子节点是“黑黑”节点且当前节点是根节点则什么都不做③如果当前节点的子节点是“黑黑”节点且当前节点不是根节点则又可以分为以下几种情况进行处理。如果当前节点的子节点是“黑黑”节点且当前节点的兄弟节点是红色的则将当前节点的兄弟节点设置为黑色的将父节点设置为红色的对父节点进行左旋重新设置当前节点的兄弟节点。如果当前节点的子节点是“黑黑”节点且当前节点的兄弟节点是黑色的兄弟节点的两个子节点也都是黑色的则将当前节点的兄弟节点设置为红色的设置当前节点的父节点为新节点。如果当前节点的子节点是“黑黑”节点且当前节点的兄弟节点是黑色的兄弟节点的左子节点是红色的且右子节点是黑色的则将当前节点的左子节点设置为黑色的将兄弟节点设置为红色的对兄弟节点进行右旋重新设置当前节点的兄弟节点。如果当前节点的子节点是“黑黑”节点且当前节点的兄弟节点是黑色的兄弟节点的右子节点是红色的且左子节点是任意颜色的则将当前节点的父节点的颜色赋值给兄弟基点将父节点设置为黑色的将兄弟节点的右子节点设置为黑色的对父节点进行左旋设置当前节点为根节点。7、图图是由有穷非空集合的顶点和顶点之间的边组成的集合通常表示为G(V, E)其中G表示一个图V是图G中顶点的集合E是图G中边的集合。在线性结构中每个元素都只有一个直接前驱和直接后继主要用来表示一对一的数据结构在树形结构中数据之间有着明显的父子关系每个数据和其子节点的多个数据相关主要用来表示一对多的数据结构在图形结构中数据之间具有任意关系图中任意两个数据元素之间都可能相关可用来表示多对多的数据结构。图根据边的属性可分为无向图和有向图。7.1、无向图和有向图若从顶点Vi到Vj的边没有方向则称这条边为无向边。顶点和无向边组成的图为无向图用无序对(Vi, Vj)来表示无向边。如图所示G(V1, {E1})其中顶点集合V1{A, B, C, D}边集合E1{ (A, B), (A, C), (A, D), (B, D), (C,D) }。若从顶点Vi到Vj的边有方向则称这条边为有向边也叫作弧用有序偶Vi, Vj来表示有向边Vi叫作弧尾Vj叫作弧头。由顶点和有向边组成的图叫作有向图。如图所示G(V2, {E2})其中顶点集合V2{A, B, C, D}弧集合E2{A, D, B, A, C, A, B, C}。连接顶点A到D的有向边就是弧A是弧尾D是弧头A, D表示弧注意弧是有方向的不能写成D, A。7.2、图的存储结构邻接矩阵图的邻接矩阵的存储方式是基于两个数组来表示图的数据结构并存储图中的数据。一个一维数组存储图中的顶点信息一个二维数组叫作邻接矩阵存储图中的边或弧的信息。设图G有n个顶点则邻接矩阵是一个n×n的方阵如图所示。7.2.1、无向图的邻接矩阵在无向图的邻接矩阵中如果Vi, Vj的交点为1则表示两个顶点连通为0则不连通。在无向图的邻接矩阵中主对角元素都为0也就是说顶点自身没有连通关系如图所示。7.2.2、有向图的邻接矩阵在有向图的邻接矩阵中如果Vi, Vj的交点为1则表示从Vi到Vj存在弧但从Vj到Vi是否存在弧不确定为0则表示从Vi到Vj不存在弧同样在有向图的邻接矩阵中主对角元素都为0也就是说从顶点到自身没有弧。需要注意的是有向图的连接是有方向的V1的出度为2从V1出发的边有两条表示从V1顶点出发的边有两条V3的出度为0表示没有从V3出发的边。有向图的邻接矩阵如图所示。7.2.3、带权重图的邻接矩阵有些图的每条边上都带有权重如果要将这些权值保存下来则可以采用权值代替矩阵中的0、1在权值不存在的元素之间用∞表示带权重图的邻接矩阵如图所示。7.3、图的存储结构邻接表数组与链表相结合的存储方法叫作邻接表。邻接表是图的一种链式存储结构主要用于解决邻接矩阵中顶点多边少时空间浪费的问题。具体的处理方法如下。1将图中的顶点信息存储在一个一维数组中同时在顶点信息中存储用于指向第1个邻接点的指针以便查找该顶点的边信息。2图中每个顶点Vi的所有邻接点构成一个线性表由于邻接点的个数不定所以用单向链表存储如果是无向图则称链表为顶点Vi的边表如果是有向图则称链表为以顶点Vi为弧尾的出边表。7.3.1、无向图的邻接表结构从图可以知道顶点是通过一个头节点类型的一维数组保存的其中每个头节点的第1个弧都指向第1条依附在该顶点上的边的信息邻接域表示该边的另一个顶点在顶点数组中的下标下一个弧指向下一条依附在该顶点上的边的信息。有向图的邻接表和无向图类似这里不再详细讲解。7.3.2、带权值的网图连接表结构对于带权值的图在节点定义中再增加一个权重值weight的数据域存储权值信息即可如图所示。7.4、图的遍历图的遍历指从图中某一顶点出发访遍图中的每个顶点且使每一个顶点仅被访问一次。图的遍历分为广度优先遍历和深度优先遍历且对无向图和有向图都适用。7.4.1、广度优先遍历广度优先遍历也叫作广度优先搜索Breadth FirstSearch类似于树的分层遍历算法其定义为假设从图中某个顶点V出发在访问了V之后依次访问V的各个未曾访问过的邻接点然后分别从这些邻接点出发依次访问它们的邻接点并使先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问直到图中所有已被访问的顶点的邻接点都被访问若此时图中尚有顶点未被访问则另选图中未曾被访问的一个顶点作为起始点重复上述过程直至图中所有顶点均被访问。如图所示的图广度优先遍历顺序为假设从起始点V1开始遍历首先访问V1和V1的邻接点V2和V3然后依次访问V2的邻接点V4和V5及V3的邻接点V6和V7最后访问V4的邻接点V8于是得到节点的线性遍历顺序为 V1→V2→V3→V4→V5→V6→V7→V8。7.4.2、深度优先遍历图的深度优先遍历也叫作深度优先搜索Depth FirstSearch类似于树的先根遍历先访问树的根节点。其定义如下假设从图中的某个顶点V出发在访问V节点后依次从V未被访问的邻接点出发以深度优先的原则遍历图直到图中所有和V节点路径连通的顶点都被访问若此时图中尚有顶点未被访问则另选一个未曾访问的顶点作为起始点重 复上述过程直至图中所有节点都被访问。如图所示的深度优先遍历顺序为假设从起始点V1开始遍历在访问了V1后选择其邻接点V2。因为V2未曾被访问所以从V2出发进行深度优先遍历。依此类推接着从V4、V8、V5出发进行遍历。在访问了V5后由于V5的邻接点都被访问过则遍历回退到V8。同理继续回退到V4、V2直至V1此时V1的另一个邻接点V3未被访问则遍历操作又从V1到V3继续进行下去得到节点的线性顺序为V1→V2→V4→V8→V5→V3→V6→V7。8、位图位图Bitmap通常基于数组实现我们可以将数组中的每个元素都看作一系列二进制数所有元素一起组成更大的二进制集合这样就可以大大节省空间。位图通常是用来判断某个数据存不存在的常用于在Bloom Filter中判断数据是否存在还可用于无重复整数的排序等在大数据行业中使用广泛。8.1、位图的数据结构位图在内部维护了一个M×N维的数组char[M][N]在这个数组里面每个字节占8位因此可以存储M×N×8个数据。假如要存储的数据范围为015则只需使用M1,N2的数据进行存储具体的数据结构如图所示。在我们要存储的数据为{1,3,6,10,15}时只需将有数据的位设置为1表示该位存在数据将其他位设置为0具体的数据结构如图所示。8.2、位图的Java实现在Java中使用byte[]字节数组来存储bit,1Byte 8bit。对于bit中的第i位该bit为1则表示true即数据存在为0则表示false即数据不存在。其具体实现分为数据结构的定义、查询方法的实现和修改方法的实现。8.2.1、数据结构的定义在如下代码中定义了一个名为Bitmap的类用于位图数据结构的存储其中byte[]数组用于存储具体的数据length用于记录数据的长度//以bit为存储单位的数据结构对于给定的第i位1表示true,0表示falsepublicclassBitmap{privatebyte[]bytes;//length为位图的长度实际可操作的下标为[0, length)privateintlength;publicBitmap(intlength){this.lengthlength;bytesnewbyte[length%80?length/8:length/81];}}8.2.2、查询方法的实现位图的查询操作为在拿到目标bit所在的Byte后将其向右位移并将高位置0使目标bit在第1位这样结果值就是目标bit值方法如下。通过byte[index 3]等价于byte[index/8]取到目标bit所在的Byte。令i index7等价于index%8得到目标bit在该Byte中的位置。为了将目标bit前面的高位置0这样位移后的值才等于目标bit本身需要构建到目标bit为止的低位掩码即01111111 (7 - i)再与原Byte做运算。将结果向右位移i位使目标bit处于第1位结果值即为所求。具体的查询位图的Java代码实现如下//获取指定位的值publicbooleanget(intindex){intiindex7;//构建到index结束的低位掩码并做运算为了将高位置0然后将结果一直右移直到目标位index位移到第1位然后根据其值返回结果if((bytes[index3](01111111(7-i)))i0)returnfalse;elsereturntrue;}8.2.3、修改方法的实现对位图的修改操作根据设定值true或false的不同分为两种情况。如果value为true则表示数据存在将目标位与1做或运算需要构建目标位为1、其他位为0的操作数。如果value为false则表示数据不存在将目标位与0做与运算需要构建目标位为0、其他位为1的操作数。构建目标位为1且其他位为0的操作数的做法为1(index 7)。修改位图的Java代码实现如下//设置指定位的值publicvoidset(intindex,booleanvalue){if(value)//通过给定位index先定位到对应的Byte并根据value值进行不同位的操作//1如果value为true则目标位应该做或运算构建“目标位为1//其他位为0”的操作数为了只合理操作目标位而不影响其他位//2如果value为false则目标位应该做与运算构建“目标位为0//其他位为1”的操作数bytes[index3]|1(index7);//bytes[index/8] bytes[index/8] | (0b0001 (index%8))elsebytes[index3](1(index7));}
Java面试——数据结构（二）
数据结构5、二叉排序树5.1、插入操作5.2、删除操作5.3、查找操作5.4、用Java实现二叉排序树6、红黑树6.1、红黑树的特性6.2、红黑树的左旋6.3、红黑树的右旋6.4、红黑树的添加6.5、红黑树的删除7、图7.1、无向图和有向图7.2、图的存储结构邻接矩阵7.2.1、无向图的邻接矩阵7.2.2、有向图的邻接矩阵7.2.3、带权重图的邻接矩阵7.3、图的存储结构邻接表7.3.1、无向图的邻接表结构7.3.2、带权值的网图连接表结构7.4、图的遍历7.4.1、广度优先遍历7.4.2、深度优先遍历8、位图8.1、位图的数据结构8.2、位图的Java实现8.2.1、数据结构的定义8.2.2、查询方法的实现8.2.3、修改方法的实现5、二叉排序树二叉排序树Binary Sort Tree又称二叉查找树Binary Search Tree或二叉搜索树。二叉排序树为满足以下条件的树若左子树不空则左子树上所有节点的值均小于它的根节点的值若右子树不空则右子树上所有节点的值均大于或等于它的根节点的值左、右子树也分别为二叉排序树。如图4-10所示便是一个二叉排序树。5.1、插入操作在二叉排序树中进行插入操作时只需找到待插入的父节点将数据插入即可具体流程如下。1将待插入的新节点与当前节点进行比较如果两个节点的值相同则表示新节点已经存在于二叉排序树中直接返回false。2将待插入的新节点与当前节点进行比较如果待插入的新节点的值小于当前节点的值则在当前节点的左子树中寻找直到左子树为空则当前节点为要找的父节点将新节点插入当前节点的左子树即可。3将待插入的新节点与当前节点进行比较如果待插入的新节点的值大于当前节点的值则在当前节点的右子树中寻找直到右子树为空则当前节点为要找的父节点将新节点插入当前节点的右子树即可。具体的插入流程如图所示。5.2、删除操作二叉排序树的删除操作主要分为三种情况待删除的节点没有子节点待删除的节点只有一个子节点待删除的节点有两个子节点。具体情况如下。1在待删除的节点没有子节点时直接删除该节点即在其父节点中将其对应的子节点置空即可。如图所示要删除的节点14没有子节点则直接将其删除即可。2在待删除的节点只有一个子节点时使用子节点替换当前节点然后删除该节点即可。如图所示要删除的节点5有一个子节点8则使用子节点8替换需要删除的节点5然后删除节点5的数据即可。3在待删除的节点有两个子节点时首先查找该节点的替换节点替换节点为左子树中的最大节点或者右子树中的最小节点然后替换待删除的节点为替换节点最后删除替换节点。如图所示要删除的节点4有两个子节点其左子树最小的节点为2其右子树最小的节点为5因此有两种结果。5.3、查找操作二叉排序树的查找方式和效率接近二分查找法因此可以很容易获取最大最右最深子节点值和最小最左最深子节点值具体的查找流程为将要查找的数据与根节点的值进行比较如果相等就返回如果小于就到左子树中递归查找如果大于就到右子树中递归查找。5.4、用Java实现二叉排序树1定义二叉排序树的数据结构publicclassNode{privateintvalue;privateNodeleft;privateNoderight;publicNode(){}publicNode(Nodeleft,Noderight,intvalue){this.leftleft;this.rightright;this.valuevalue;}publicNode(intvalue){this(null,null,value);}publicNodegetLeft(){returnthis.left;}publicvoidsetLeft(Nodeleft){this.leftleft;}publicNodegetRight(){returnthis.right;}publicvoidsetRight(Noderight){this.rightright;}publicintgetValue(){returnthis.value;}publicvoidsetValue(intvalue){this.valuevalue;}}如上代码定义了二叉排序树的数据结构Node在Node中包含的value、left、right分别表示二叉排序树的值、左子节点、右子节点。2定义二叉排序树的插入方法/向二叉排序树中插入节点/publicvoidinsertBST(intkey){Nodeproot;/记录查找节点的前一个节点/Nodeprevnull;/一直查找下去直到到达满足条件的节点位置/while(p!null){prevp;if(keyp.getValue())pp.getLeft();elseif(keyp.getValue())pp.getRight();elsereturn;}/prev是待插入节点的父节点根据节点值的大小被插入相应的位置/if(rootnull)rootnewNode(key);elseif(keyprev.getValue())prev.setLeft(newNode(key));elseprev.setRight(newNode(key));}如上代码定义了insertBST()来向二叉排序树中插入节点具体操作分4步①循环查找需要插入的节点prev; ②如果二叉树的根节点为null则说明二叉树是空树直接将该节点设置为根节点③如果待插入的数据小于该节点的值则将其插入该节点的左节点④如果待插入的数据大于该节点的值则将其插入该节点的右节点。3定义二叉排序树的删除方法/ 删除二叉排序树中的节点 分为三种情况删除节点为p 其父节点为f 1要删除的p节点是叶子节点只需要修改它的双亲节点的指针为空 2若p只有左子树或者只有右子树则直接让左子树或右子树代替p 3若p既有左子树又有右子树 则用p左子树中最大的值即最右端S代替P删除s重接其左子树 /publicvoiddeleteBST(intkey){deleteBST(root,key);}privatebooleandeleteBST(Nodenode,intkey){if(nodenull)returnfalse;else{if(keynode.getValue()){returndelete(node);}elseif(keynode.getValue()){returndeleteBST(node.getLeft(),key);}else{returndeleteBST(node.getRight(),key);}}}privatebooleandelete(Nodenode){Nodetempnull;/右子树空只需要重接它的左子树 如果是叶子节点则在这里也把叶子节点删除了 /if(node.getRight()null){tempnode;nodenode.getLeft();}/左子树空 重接它的右子树/elseif(node.getLeft()null){tempnode;nodenode.getRight();}/左右子树均不为空/else{tempnode;Nodesnode;/转向左子树然后向右走到“尽头”/ss.getLeft();while(s.getRight()!null){temps;ss.getRight();}node.setValue(s.getValue());if(temp!node){temp.setRight(s.getLeft());}else{temp.setLeft(s.getLeft());}}returntrue;}以上代码通过三种方法实现了二叉树的删除deleteBST(int key)是提供给用户的删除方法会调用deleteBST(Node node, int key)其中Node参数为根节点表示从根节点开始递归查找和删除deleteBST(Node node, int key)通过递归查找找到要删除的节点。查找要删除的节点的具体做法如下。如果key和当前节点的值相等则说明找到了需要删除的节点。如果key小于当前节点的值则在左子树中查找。如果key大于当前节点的值则在右子树中查找。在找到要删除的节点后调用delete(Node node)删除该节点这里的删除分3种情况。如果右子树为空则只需将它的左子树接到该节点。如果右子树为空则只需将它的右子树接到该节点。如果左右子树均不为空则需要在左子树中寻找最小的节点并将左子树中最小的节点接到当前节点。4定义二叉排序树的查询方法/查找在二叉排序树中是否有key值/publicbooleansearchBST(intkey){Nodecurrentroot;while(current!null){//等于当前值则查找成功返回if(keycurrent.getValue())returntrue;//比当前值小进入左子树中查找elseif(keycurrent.getValue())currentcurrent.getLeft();else//比当前值大进入右子树中查找currentcurrent.getRight();}returnfalse;}以上代码定义了searchBST()用于查询二叉排序树具体做法如下。如果key和当前节点的值相等则说明找到了该节点。如果key小于当前节点的值则在左子树中查找。如果key大于当前节点的值则在右子树中查找。6、红黑树红黑树Red-Black Tree, R-B Tree是一种自平衡的二叉查找树。在红黑树的每个节点上都多出一个存储位表示节点的颜色颜色只能是红Red或者黑Black。6.1、红黑树的特性红黑树的特性如下。每个节点或者是黑色的或者是红色的。根节点是黑色的。每个叶子节点NIL都是黑色的。如果一个节点是红色的则它的子节点必须是黑色的。从一个节点到该节点的子孙节点的所有路径上都包含相同数量的黑色节点。具体的数据结构如图所示。6.2、红黑树的左旋对a节点进行左旋指将a节点的右子节点设为a节点的父节点即将a节点变成一个左节点。因此左旋意味着被旋转的节点将变成一个左节点具体流程如图所示。6.3、红黑树的右旋对b节点进行右旋指将b节点的左子节点设为b节点的父节点即将b节点设为一个右节点。因此右旋意味着被旋转的节点将变成一个右节点具体流程如图所示。6.4、红黑树的添加红黑树的添加分为3步①将红黑树看作一颗二叉查找树并以二叉树的插入规则插入新节点②将插入的节点涂为“红色”或“黑色”; ③通过左旋、右旋或着色操作使之重新成为一颗红黑树。根据被插入的节点的父节点的情况可以将具体的插入分为3种情况来处理。如果被插入的节点是根节点则直接把此节点涂为黑色的。如果被插入的节点的父节点是黑色的则什么也不需要做在节点插入后仍然是红黑树。如果被插入的节点的父节点是红色的则在被插入节点的父节点是红色的时被插入节点一定存在非空祖父节点即被插入节点也一定存在叔叔节点即使叔叔节点叔叔节点指当前节点的祖父节点的另一个子节点为空我们也视之为存在空节点本身就是黑色节点。然后根据叔叔节点的颜色在被插入节点的父节点是红色的时进一步分为3种情况来处理。如果当前节点的父节点是红色的当前节点的叔叔节点是红色的则将父节点设为黑色的将叔叔节点设为黑色的将祖父节点设为红色的将祖父节点设为当前节点。如果当前节点的父节点是红色的当前节点的叔叔节点是黑色的且当前节点是右节点则将父节点设为当前节点以新节点为支点左旋。如果当前节点的父节点是红色的当前节点的叔叔节点是黑色的且当前节点是左节点则将父节点设为黑色的将祖父节点设为红色的以祖父节点为支点右旋。6.5、红黑树的删除红黑树的删除分为两步①将红黑树看作一颗二叉查找树根据二叉查找树的删除规则删除节点②通过左旋、旋转、重新着色操作进行树修正使之重新成为一棵红黑树具体操作如下。将红黑树看作一颗二叉查找树将节点删除。如果被删除的节点没有子节点那么直接将该节点删除。如果被删除的节点只有一个子节点那么直接删除该节点并用该节点的唯一子节点替换该节点的位置。如果被删除的节点有两个子节点那么先找出该节点的替换节点然后把替换节点的数据复制给该节点的数据之后删除替换节点。通过左旋、旋转、重新着色操作进行树修正使之重新成为一棵红黑树因为红黑树在删除节点后可能会违背红黑树的特性所以需要通过旋转和重新着色来修正该树使之重新成为一棵红黑树①如果当前节点的子节点是“红黑”节点则直接把该节点设为黑色的②如果当前节点的子节点是“黑黑”节点且当前节点是根节点则什么都不做③如果当前节点的子节点是“黑黑”节点且当前节点不是根节点则又可以分为以下几种情况进行处理。如果当前节点的子节点是“黑黑”节点且当前节点的兄弟节点是红色的则将当前节点的兄弟节点设置为黑色的将父节点设置为红色的对父节点进行左旋重新设置当前节点的兄弟节点。如果当前节点的子节点是“黑黑”节点且当前节点的兄弟节点是黑色的兄弟节点的两个子节点也都是黑色的则将当前节点的兄弟节点设置为红色的设置当前节点的父节点为新节点。如果当前节点的子节点是“黑黑”节点且当前节点的兄弟节点是黑色的兄弟节点的左子节点是红色的且右子节点是黑色的则将当前节点的左子节点设置为黑色的将兄弟节点设置为红色的对兄弟节点进行右旋重新设置当前节点的兄弟节点。如果当前节点的子节点是“黑黑”节点且当前节点的兄弟节点是黑色的兄弟节点的右子节点是红色的且左子节点是任意颜色的则将当前节点的父节点的颜色赋值给兄弟基点将父节点设置为黑色的将兄弟节点的右子节点设置为黑色的对父节点进行左旋设置当前节点为根节点。7、图图是由有穷非空集合的顶点和顶点之间的边组成的集合通常表示为G(V, E)其中G表示一个图V是图G中顶点的集合E是图G中边的集合。在线性结构中每个元素都只有一个直接前驱和直接后继主要用来表示一对一的数据结构在树形结构中数据之间有着明显的父子关系每个数据和其子节点的多个数据相关主要用来表示一对多的数据结构在图形结构中数据之间具有任意关系图中任意两个数据元素之间都可能相关可用来表示多对多的数据结构。图根据边的属性可分为无向图和有向图。7.1、无向图和有向图若从顶点Vi到Vj的边没有方向则称这条边为无向边。顶点和无向边组成的图为无向图用无序对(Vi, Vj)来表示无向边。如图所示G(V1, {E1})其中顶点集合V1{A, B, C, D}边集合E1{ (A, B), (A, C), (A, D), (B, D), (C,D) }。若从顶点Vi到Vj的边有方向则称这条边为有向边也叫作弧用有序偶Vi, Vj来表示有向边Vi叫作弧尾Vj叫作弧头。由顶点和有向边组成的图叫作有向图。如图所示G(V2, {E2})其中顶点集合V2{A, B, C, D}弧集合E2{A, D, B, A, C, A, B, C}。连接顶点A到D的有向边就是弧A是弧尾D是弧头A, D表示弧注意弧是有方向的不能写成D, A。7.2、图的存储结构邻接矩阵图的邻接矩阵的存储方式是基于两个数组来表示图的数据结构并存储图中的数据。一个一维数组存储图中的顶点信息一个二维数组叫作邻接矩阵存储图中的边或弧的信息。设图G有n个顶点则邻接矩阵是一个n×n的方阵如图所示。7.2.1、无向图的邻接矩阵在无向图的邻接矩阵中如果Vi, Vj的交点为1则表示两个顶点连通为0则不连通。在无向图的邻接矩阵中主对角元素都为0也就是说顶点自身没有连通关系如图所示。7.2.2、有向图的邻接矩阵在有向图的邻接矩阵中如果Vi, Vj的交点为1则表示从Vi到Vj存在弧但从Vj到Vi是否存在弧不确定为0则表示从Vi到Vj不存在弧同样在有向图的邻接矩阵中主对角元素都为0也就是说从顶点到自身没有弧。需要注意的是有向图的连接是有方向的V1的出度为2从V1出发的边有两条表示从V1顶点出发的边有两条V3的出度为0表示没有从V3出发的边。有向图的邻接矩阵如图所示。7.2.3、带权重图的邻接矩阵有些图的每条边上都带有权重如果要将这些权值保存下来则可以采用权值代替矩阵中的0、1在权值不存在的元素之间用∞表示带权重图的邻接矩阵如图所示。7.3、图的存储结构邻接表数组与链表相结合的存储方法叫作邻接表。邻接表是图的一种链式存储结构主要用于解决邻接矩阵中顶点多边少时空间浪费的问题。具体的处理方法如下。1将图中的顶点信息存储在一个一维数组中同时在顶点信息中存储用于指向第1个邻接点的指针以便查找该顶点的边信息。2图中每个顶点Vi的所有邻接点构成一个线性表由于邻接点的个数不定所以用单向链表存储如果是无向图则称链表为顶点Vi的边表如果是有向图则称链表为以顶点Vi为弧尾的出边表。7.3.1、无向图的邻接表结构从图可以知道顶点是通过一个头节点类型的一维数组保存的其中每个头节点的第1个弧都指向第1条依附在该顶点上的边的信息邻接域表示该边的另一个顶点在顶点数组中的下标下一个弧指向下一条依附在该顶点上的边的信息。有向图的邻接表和无向图类似这里不再详细讲解。7.3.2、带权值的网图连接表结构对于带权值的图在节点定义中再增加一个权重值weight的数据域存储权值信息即可如图所示。7.4、图的遍历图的遍历指从图中某一顶点出发访遍图中的每个顶点且使每一个顶点仅被访问一次。图的遍历分为广度优先遍历和深度优先遍历且对无向图和有向图都适用。7.4.1、广度优先遍历广度优先遍历也叫作广度优先搜索Breadth FirstSearch类似于树的分层遍历算法其定义为假设从图中某个顶点V出发在访问了V之后依次访问V的各个未曾访问过的邻接点然后分别从这些邻接点出发依次访问它们的邻接点并使先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问直到图中所有已被访问的顶点的邻接点都被访问若此时图中尚有顶点未被访问则另选图中未曾被访问的一个顶点作为起始点重复上述过程直至图中所有顶点均被访问。如图所示的图广度优先遍历顺序为假设从起始点V1开始遍历首先访问V1和V1的邻接点V2和V3然后依次访问V2的邻接点V4和V5及V3的邻接点V6和V7最后访问V4的邻接点V8于是得到节点的线性遍历顺序为 V1→V2→V3→V4→V5→V6→V7→V8。7.4.2、深度优先遍历图的深度优先遍历也叫作深度优先搜索Depth FirstSearch类似于树的先根遍历先访问树的根节点。其定义如下假设从图中的某个顶点V出发在访问V节点后依次从V未被访问的邻接点出发以深度优先的原则遍历图直到图中所有和V节点路径连通的顶点都被访问若此时图中尚有顶点未被访问则另选一个未曾访问的顶点作为起始点重 复上述过程直至图中所有节点都被访问。如图所示的深度优先遍历顺序为假设从起始点V1开始遍历在访问了V1后选择其邻接点V2。因为V2未曾被访问所以从V2出发进行深度优先遍历。依此类推接着从V4、V8、V5出发进行遍历。在访问了V5后由于V5的邻接点都被访问过则遍历回退到V8。同理继续回退到V4、V2直至V1此时V1的另一个邻接点V3未被访问则遍历操作又从V1到V3继续进行下去得到节点的线性顺序为V1→V2→V4→V8→V5→V3→V6→V7。8、位图位图Bitmap通常基于数组实现我们可以将数组中的每个元素都看作一系列二进制数所有元素一起组成更大的二进制集合这样就可以大大节省空间。位图通常是用来判断某个数据存不存在的常用于在Bloom Filter中判断数据是否存在还可用于无重复整数的排序等在大数据行业中使用广泛。8.1、位图的数据结构位图在内部维护了一个M×N维的数组char[M][N]在这个数组里面每个字节占8位因此可以存储M×N×8个数据。假如要存储的数据范围为015则只需使用M1,N2的数据进行存储具体的数据结构如图所示。在我们要存储的数据为{1,3,6,10,15}时只需将有数据的位设置为1表示该位存在数据将其他位设置为0具体的数据结构如图所示。8.2、位图的Java实现在Java中使用byte[]字节数组来存储bit,1Byte 8bit。对于bit中的第i位该bit为1则表示true即数据存在为0则表示false即数据不存在。其具体实现分为数据结构的定义、查询方法的实现和修改方法的实现。8.2.1、数据结构的定义在如下代码中定义了一个名为Bitmap的类用于位图数据结构的存储其中byte[]数组用于存储具体的数据length用于记录数据的长度//以bit为存储单位的数据结构对于给定的第i位1表示true,0表示falsepublicclassBitmap{privatebyte[]bytes;//length为位图的长度实际可操作的下标为[0, length)privateintlength;publicBitmap(intlength){this.lengthlength;bytesnewbyte[length%80?length/8:length/81];}}8.2.2、查询方法的实现位图的查询操作为在拿到目标bit所在的Byte后将其向右位移并将高位置0使目标bit在第1位这样结果值就是目标bit值方法如下。通过byte[index 3]等价于byte[index/8]取到目标bit所在的Byte。令i index7等价于index%8得到目标bit在该Byte中的位置。为了将目标bit前面的高位置0这样位移后的值才等于目标bit本身需要构建到目标bit为止的低位掩码即01111111 (7 - i)再与原Byte做运算。将结果向右位移i位使目标bit处于第1位结果值即为所求。具体的查询位图的Java代码实现如下//获取指定位的值publicbooleanget(intindex){intiindex7;//构建到index结束的低位掩码并做运算为了将高位置0然后将结果一直右移直到目标位index位移到第1位然后根据其值返回结果if((bytes[index3](01111111(7-i)))i0)returnfalse;elsereturntrue;}8.2.3、修改方法的实现对位图的修改操作根据设定值true或false的不同分为两种情况。如果value为true则表示数据存在将目标位与1做或运算需要构建目标位为1、其他位为0的操作数。如果value为false则表示数据不存在将目标位与0做与运算需要构建目标位为0、其他位为1的操作数。构建目标位为1且其他位为0的操作数的做法为1(index 7)。修改位图的Java代码实现如下//设置指定位的值publicvoidset(intindex,booleanvalue){if(value)//通过给定位index先定位到对应的Byte并根据value值进行不同位的操作//1如果value为true则目标位应该做或运算构建“目标位为1//其他位为0”的操作数为了只合理操作目标位而不影响其他位//2如果value为false则目标位应该做与运算构建“目标位为0//其他位为1”的操作数bytes[index3]|1(index7);//bytes[index/8] bytes[index/8] | (0b0001 (index%8))elsebytes[index3](1(index7));}