B树的java源码实现 - JAVA

;
}
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();
}
}
package com.discover;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Random;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

/**
* 一颗B树的简单实现。
*

* 其实现原理参考《算法导论》第二版第十八章。
*

* 如果大家想读懂这些源代码，不妨先看看上述章节。
*
* @author WangPing
*
* @param - 键类型
* @param - 值类型
*/
public class BTree
{
private static Log logger = LogFactory.getLog(BTree.class);

/**
* 在B树节点中搜索给定键值的返回结果。

B树的java源码实现(六)