B树的java源码实现 - JAVA

表示元素应该插入的位置
}
return new SearchResult(result, index);
}

/**
* 将给定的key追加到节点的末尾，
* 一定要确保调用该方法之后，节点中的关键字还是
* 以非降序存放。
*
* @param key - 给定的键值
*/
public void addKey(Integer key)
{
keys.add(key);
}

/**
* 删除给定索引的键值。
*

* 你需要自己保证给定的索引是合法的。
*
* @param index - 给定的索引
*/
public void removeKey(int index)
{
keys.remove(index);
}

/**
* 得到节点中给定索引的键值。
*

* 你需要自己保证给定的索引是合法的。
*
* @param index - 给定的索引
* @return 节点中给定索引的键值
*/
public Integer keyAt(int index)
{
return keys.get(index);
}

/**
* 在该节点中插入给定的key，
* 该方法保证插入之后，其键值还是以非降序存放。
*

* 不过该方法的时间复杂度为O(t)。
*

* TODO 需要考虑键值是否可以重复。
*
* @param key - 给定的键值
*/
public void insertKey(Integer key)
{
SearchResult result = searchKey(key);
insertKey(key, result.getIndex());
}

/**
* 在该节点中给定索引的位置插入给定的key，
* 你需要自己保证key插入了正确的位置。
*
* @param key - 给定的键值
* @param index - 给定的索引
*/
public void insertKey(Integer key, int index)
{
/* TODO
* 通过新建一个ArrayList来实现插入真的很恶心，先这样吧
* 要是有类似C中的reallocate就好了。
*/
List newKeys = new ArrayList();

int i = 0;

// index = 0或者index = keys.size()都没有问题
for(; i < index; ++ i)
newKeys.add(keys.get(i));
newKeys.add(key);
for(; i < keys.size(); ++ i)
newKeys.add(keys.get(i));
keys = newKeys;
}

/**
* 返回节点中给定索引的子节点。
*

* 你需要自己保证给定的索引是合法的。
*
* @param index - 给定的索引
* @return 给定索引对应的子节点
*/
public BTreeNode childAt(int index)
{
if(isLeaf())
throw new UnsupportedOperationException("Leaf node doesn't have children.");
return children.get(index);
}

/**
* 将给定的子节点追加到该节点的末尾。
*
* @param child - 给定的子节点
*/
public void addChild(BTreeNode child)
{
children.add(child);
}

/**
* 删除该节点中给定索引位置的子节点。
*

* 你需要自己保证给定的索引是合法的。
*
* @param index - 给定的索引
*/
public void removeChild(int index)
{
children.remove(index);
}

/**
* 将给定的子节点插入到该节点中给定索引
* 的位置。
*
* @param child - 给定的子节点
* @param index - 子节点带插入的位置
*/
public void insertChild(BTreeNode child, int index)
{
List newChildren = new ArrayList();
int i = 0;
for(; i < index; ++ i)
newChildren.add(children.get(i));
newChildren.add(child);
for(; i < children.size(); ++ i)
newChildren.add(children.get(i));
children = newChildren;
}
}

private static final int DEFAULT_T = 2;

/** B树的根节点 */
private BTr

B树的java源码实现(二)