javatreeb-treemultiway-tree

b-tree fullness (as percentage)


I am currently busy implementing a B-Tree in JAVA. One of the methods requires me return as a percentage the fullness of the complete tree. The percentage should be out of 100 and if, for example, 50 is returned, it means that the tree is 50% full. A empty tree is 0% full.

Here is the node class I am working with

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){...}
    ...
}

To summaries: please help me implement the following method:

public int fullness()
{
    ???
}

Any suggestions, help and/or code would be appreciated.


Solution

  • In your b-tree class, maintain the number of elements in the tree and the capacity of the tree.

    The percentage is "elements in tree" / capacity.