B树的java源码实现(七)

* 该结果有两部分组成。第一部分表示此次查找是否成功，
* 如果查找成功，第二部分表示给定键值在B树节点中的位置，
* 如果查找失败，第二部分表示给定键值应该插入的位置。
*/
private static class SearchResult
{
private boolean result;
private int index;

public SearchResult(boolean result, int index)
{
this.result = result;
this.index = index;
}

public boolean getResult()
{
return result;
}

public int getIndex()
{
return index;
}
}

/**
* 为了简单起见，暂时只支持整型的key，
* 等到工作完成后，支持泛型。
*

*
* TODO 需要考虑并发情况下的存取。
*/
private static class BTreeNode
{
/** 节点的关键字，以非降序存放 */
private List keys;
/** 内节点的子节点 */
private List children;
/** 是否为叶子节点 */
private boolean leaf;

public BTreeNode()
{
keys = new ArrayList();
children = new ArrayList();
leaf = false;
}

public boolean isLeaf()
{
return leaf;
}

public void setLeaf(boolean leaf)
{
this.leaf = leaf;
}

/**
* 返回关键字的个数。如果是非叶子节点，该节点的
* 子节点个数为({@link #size()} + 1)。
*
* @return 关键字的个数
*/
public int size()
{
return keys.size();
}

/**
* 在节点中查找给定的key，如果节点中存在给定的
* key，则返回一个SearchResult，
* 标识此次查找成功，给定key在节点中的索引和给定
* key对应的值。如果不存在，则返回SearchResult
* 标识此次查找失败，给定key应该插入的位置，该key
* 对应的值为null。
*

* 如果查找失败，返回结果中的索引域为[0, {@link #size()}]；
* 如果查找成功，返回结果中的索引域为[0, {@link #size()} - 1]
*

* 这是一个二分查找算法，可以保证时间复杂度为O(log(t))。
*
* @param key - 给定的键值
* @return - 查找结果 www.2cto.com
*/
public SearchResult searchKey(Integer key)
{
int l = 0;
int h = keys.size() - 1;
int mid = 0;
while(l <= h)
{
mid = (l + h) / 2; // 先这么写吧，BTree实现中，l+h不可能溢出
if(keys.get(mid) == key)
break;
else if(keys.get(mid) > key)
h = mid - 1;
else // if(keys.get(mid) < key)
l = mid + 1;
}
boolean result = false;
int index = 0;
if(l <= h) // 说明查找成功

* 你需要自己保证给定的索引是合法的。
*
* @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);
}

/**