学步园

2-3-4树节点分裂分两种情况。

1：节点分裂；2：根的分裂。

先要分裂的数据项设为A,B,C

节点分裂

1.创建一个新的空节点。它是要分裂节点的兄弟，在要分裂节点的右边。

2.数据项C转移到新节点上。

3.数据项B转移到要分裂节点的父节点上。

4.数据项A保留在原来的节点上。

5.最右边的两个子节点从要分裂节点处断开，连接到新节点上。

根的分裂

1.创建新的节点，作为根。它是要分裂节点的父节点。

2创建第二个新的空节点。它是要分裂节点的兄弟，在要分裂节点的右边。

3数据项C转移到新节点上。

4数据项B转移到要分裂节点的父节点上。

5数据项A保留在原来的节点上。

6.最右边的两个子节点从要分裂节点处断开，连接到新节点上。

代码

public void split(Node thisNode) // split the node<br /> {<br /> // assumes node is full<br /> DataItem itemB, itemC; //数据项B,C<br /> Node parent, child2, child3;//thisNode节点父节点，第3、4个子节点<br /> int itemIndex;</p> <p> itemC = thisNode.removeItem(); // 数据项C从thisNode节点移除<br /> itemB = thisNode.removeItem(); // 数据项B从thisNode节点移除</p> <p> child2 = thisNode.disconnectChild(2); // 节点的第3个子节点从节点中断开<br /> child3 = thisNode.disconnectChild(3); //节点的第4个子节点从节点中断开 </p> <p> Node newRight = new Node(); // make new node</p> <p> if(thisNode==root) // 如果是根节点，创建新的节点，作为根。它是要分裂节点的父节点。<br /> {<br /> root = new Node(); // make new root<br /> parent = root; // root is our parent<br /> root.connectChild(0, thisNode); // connect to parent<br /> }<br /> else // this node not the root<br /> parent = thisNode.getParent(); // 得到节点的父节点</p> <p> // deal with parent<br /> itemIndex = parent.insertItem(itemB); // 将数据项B插入父节点，并返回插入的位置<br /> int n = parent.getNumItems(); // 父节点的数据项总数</p> <p>/*<br /> *将父节点中子节点移动到合适的位置<br /> */<br /> for(int j=n-1; j>itemIndex; j--) // move parent's<br /> { // connections<br /> Node temp = parent.disconnectChild(j); // one child<br /> parent.connectChild(j+1, temp); // to the right<br /> }<br /> // connect newRight to parent<br /> parent.connectChild(itemIndex+1, newRight);//新节点与父节点相连</p> <p> // deal with newRight<br /> newRight.insertItem(itemC); // item C to newRight<br /> newRight.connectChild(0, child2); // connect to 0 and 1<br /> newRight.connectChild(1, child3); // on newRight<br /> } // end split()<br />