B树的java源码实现 - JAVA

{
if(siblingIndex < result.getIndex()) // 左兄弟节点满足条件
{
childNode.insertKey(node.keyAt(siblingIndex), 0);
node.removeKey(siblingIndex);
node.insertKey(siblingNode.keyAt(siblingNode.size() - 1), siblingIndex);
siblingNode.removeKey(siblingNode.size() - 1);
// 将左兄弟节点的最后一个孩子移到childNode
if(!siblingNode.isLeaf())
{
childNode.insertChild(siblingNode.childAt(siblingNode.size()), 0);
siblingNode.removeChild(siblingNode.size());
}
}
else // 右兄弟节点满足条件
{
childNode.insertKey(node.keyAt(result.getIndex()), childNode.size() - 1);
node.removeKey(result.getIndex());
node.insertKey(siblingNode.keyAt(0), result.getIndex());
siblingNode.removeKey(0);
// 将右兄弟节点的第一个孩子移到childNode
// childNode.insertChild(siblingNode.childAt(0), childNode.size() + 1);
if(!siblingNode.isLeaf())
{
childNode.addChild(siblingNode.childAt(0));
siblingNode.removeChild(0);
}
}
delete(childNode, key);
}
else // 3.b 如果其相邻左右节点都包含t-1个关键字
{
if(result.getIndex() < node.size()) // 存在右兄弟
{
BTreeNode rightSiblingNode = node.childAt(result.getIndex() + 1);
childNode.addKey(node.keyAt(result.getIndex()));
node.removeKey(result.getIndex());
node.removeChild(result.getIndex() + 1);
for(int i = 0; i < rightSiblingNode.size(); ++ i)
childNode.addKey(rightSiblingNode.keyAt(i));
if(!rightSiblingNode.isLeaf())
{
for(int i = 0; i <= rightSiblingNode.size(); ++ i)
childNode.addChild(rightSiblingNode.childAt(i));
}
}
else // 存在左节点
{
BTreeNode leftSiblingNode = node.childAt(result.getIndex() - 1);
childNode.addKey(node.keyAt(result.getIndex() - 1));
node.removeKey(result.getIndex() - 1);
node.removeChild(result.getIndex() - 1);
for(int i = leftSiblingNode.size() - 1; i >= 0; -- i)

childNode.insertKey(leftSiblingNode.keyAt(i), 0);
if(!leftSiblingNode.isLeaf())
{
for(int i = leftSiblingNode.size(); i >= 0; -- i)
childNode.insertChild(leftSiblingNode.childAt(i), 0);
}
}
// 如果node是root并且node不包含任何关键字了
if(node == root && node.size() == 0)
root = childNode;
delete(childNode, key);
}
}
}
}

/**
* 一个简单的层次遍历B树实现，用于输出B树。
*

* TODO 待改进，使显示更加形象化。
*/
public void output()
{
Queue queue = new LinkedList();
queue.offer(root);
while(!queue.isEmpty())
{
BTreeNode node = queue.poll();
for(int i = 0; i < node.size(); ++ i)
System.out.print(node.keyAt(i) + " ");
System.out.println();
if(!node.isLeaf())
{
for(int i = 0; i <= node.size(); ++ i)
queue.offer(node.childAt(i));
}
}
}

public static void main(String[] args)
{
Random random = new Random();
BTree btree = new BTree();
for(int i = 0; i < 10; ++ i)
{
int r = random.nextInt(100);
System.out.println(r);
btree.insert(r);
}
System.out.println("----------------------");
btree.output();
}
}

摘自 Bloodwolf的专栏

B树的java源码实现(十)