java - b-tree 丰满度（百分比）

Question

我目前正忙于在 JAVA 中实现B-Tree 。其中一种方法要求我以百分比形式返回完整树的完整度。该百分比应不超过 100，例如，如果返回 50，则表示树已满 50%。一棵空树是 0% 满的。

这是我正在使用的节点类

class btNode<T extends Comparable<? super T>>
{
    boolean leaf = true;
    int keyCount = 0;
    int referenceCount= 0;
    Comparable<T>[] keys = new Comparable[m-1];
    btNode<T>[] references= new btNode[m];
    btNode(int m){...}
    ...
}

总结：请帮我实现以下方法：

public int fullness()
{
    ???
}

任何建议、帮助和/或代码将不胜感激。

Answer 1

在您的 b-tree 类中，维护树中元素的数量和树的容量。

百分比是“树中的元素”/容量。