上图描述了节点分裂的例子,另一种描述节点分裂的说法是4-节点变成了两个 2- 节点。节点分裂是把数据向上和向右移动,从而保持了数的平衡。一般插入只需要分裂一个节点,除非插入路径上存在不止一个满节点时,这种情况就需要多重分裂。
2、根的分裂如果一开始查找插入节点时就碰到满的根节点,那么插入过程更复杂:
①、创建新的根节点,它是要分裂节点的父节点。
②、创建第二个新的节点,它是要分裂节点的兄弟节点;
③、数据项C移到新的兄弟节点中;
④、数据项B移到新的根节点中;
⑤、数据项A保留在原来的位置;
⑥、要分裂节点最右边的两个子节点断开连接,连到新的兄弟节点中。
上图便是根分裂的情况,分裂完成之后,整个树的高度加1。另外一种描述根分裂的方法是说4-节点变成三个2-节点。
注意:插入时,碰到没有满的节点时,要继续向下寻找其子节点进行插入。如果直接插入该节点,那么还要进行子节点的增加,因为在2-3-4树中节点的子节点个数要比数据项多1;如果插入的节点满了,那么就要进行节点分裂。下图是一系列插入过程,有4个节点分裂了,两个是根,两个是叶节点:
4、完整源码实现
分为节点类Node,表示每个节点的数据项类DataItem,以及最后的2-3-4树类Tree234.class
package com.ys.tree.twothreefour; public class Tree234 { private Node root = new Node() ; /*public Tree234(){ root = new Node(); }*/ //查找关键字值 public int find(long key){ Node curNode = root; int childNumber ; while(true){ if((childNumber = curNode.findItem(key))!=-1){ return childNumber; }else if(curNode.isLeaf()){//节点是叶节点 return -1; }else{ curNode = getNextChild(curNode,key); } } } public Node getNextChild(Node theNode,long theValue){ int j; int numItems = theNode.getNumItems(); for(j = 0 ; j < numItems ; j++){ if(theValue < theNode.getItem(j).dData){ return theNode.getChild(j); } } return theNode.getChild(j); } //插入数据项 public void insert(long dValue){ Node curNode = root; DataItem tempItem = new DataItem(dValue); while(true){ if(curNode.isFull()){//如果节点满数据项了,则分裂节点 split(curNode); curNode = curNode.getParent(); curNode = getNextChild(curNode, dValue); }else if(curNode.isLeaf()){//当前节点是叶节点 break; }else{ curNode = getNextChild(curNode, dValue); } }//end while curNode.insertItem(tempItem); } public void split(Node thisNode){ DataItem itemB,itemC; Node parent,child2,child3; int itemIndex; itemC = thisNode.removeItem(); itemB = thisNode.removeItem(); child2 = thisNode.disconnectChild(2); child3 = thisNode.disconnectChild(3); Node newRight = new Node(); if(thisNode == root){//如果当前节点是根节点,执行根分裂 root = new Node(); parent = root; root.connectChild(0, thisNode); }else{ parent = thisNode.getParent(); } //处理父节点 itemIndex = parent.insertItem(itemB); int n = parent.getNumItems(); for(int j = n-1; j > itemIndex ; j--){ Node temp = parent.disconnectChild(j); parent.connectChild(j+1, temp); } parent.connectChild(itemIndex+1, newRight); //处理新建的右节点 newRight.insertItem(itemC); newRight.connectChild(0, child2); newRight.connectChild(1, child3); } //打印树节点 public void displayTree(){ recDisplayTree(root,0,0); } private void recDisplayTree(Node thisNode,int level,int childNumber){ System.out.println("levle="+level+" child="+childNumber+" "); thisNode.displayNode(); int numItems = thisNode.getNumItems(); for(int j = 0; j < numItems+1 ; j++){ Node nextNode = thisNode.getChild(j); if(nextNode != null){ recDisplayTree(nextNode, level+1, j); }else{ return; } } } //数据项 class DataItem{ public long dData; public DataItem(long dData){ this.dData = dData; } public void displayItem(){ System.out.println("http://www.likecs.com/"+dData); } } //节点 class Node{ private static final int ORDER = 4; private int numItems;//表示该节点有多少个数据项 private Node parent;//父节点 private Node childArray[] = new Node[ORDER];//存储子节点的数组,最多有4个子节点 private DataItem itemArray[] = new DataItem[ORDER-1];//存放数据项的数组,一个节点最多有三个数据项 //连接子节点 public void connectChild(int childNum,Node child){ childArray[childNum] = child; if(child != null){ child.parent = this; } } //断开与子节点的连接,并返回该子节点 public Node disconnectChild(int childNum){ Node tempNode = childArray[childNum]; childArray[childNum] = null; return tempNode; } //得到节点的某个子节点 public Node getChild(int childNum){ return childArray[childNum]; } //得到父节点 public Node getParent(){ return parent; } //判断是否是叶节点 public boolean isLeaf(){ return (childArray[0] == null)?true:false; } //得到节点数据项的个数 public int getNumItems(){ return numItems; } //得到节点的某个数据项 public DataItem getItem(int index){ return itemArray[index]; } //判断节点的数据项是否满了(最多3个) public boolean isFull(){ return (numItems == ORDER-1) ? true:false; } //找到数据项在节点中的位置 public int findItem(long key){ for(int j = 0 ; j < ORDER-1 ; j++){ if(itemArray[j]==null){ break; }else if(itemArray[j].dData == key){ return j; } } return -1; } //将数据项插入到节点 public int insertItem(DataItem newItem){ numItems++; long newKey = newItem.dData; for(int j = ORDER-2 ; j >= 0 ; j--){ if(itemArray[j] == null){//如果为空,继续向前循环 continue; }else{ long itsKey = itemArray[j].dData;//保存节点某个位置的数据项 if(newKey < itsKey){//如果比新插入的数据项大 itemArray[j+1] = itemArray[j];//将大数据项向后移动一位 }else{ itemArray[j+1] = newItem;//如果比新插入的数据项小,则直接插入 return j+1; } } } //如果都为空,或者都比待插入的数据项大,则将待插入的数据项放在节点第一个位置 itemArray[0] = newItem; return 0; } //移除节点的数据项 public DataItem removeItem(){ DataItem temp = itemArray[numItems-1]; itemArray[numItems-1] = null; numItems--; return temp; } //打印节点的所有数据项 public void displayNode(){ for(int j = 0 ; j < numItems ; j++){ itemArray[j].displayItem(); } System.out.println("http://www.likecs.com/"); } } }