Сумма длин ветвей / кол-во вершин = степень сбалансированности
кол-во вершин / (2^Макс.длина или размер ArrayList) = степень заполнения
добавить вывод пары строк с расчетами до и посл
Есть логика расчета на Jav
void balance(ArrayList array, int a, int b)
if (a>b) return
int m = (a + b) / 2
insertByIndex(0, array.get(m))
balance(array, a, m-1)
balance(array, m+1, b)
int countDescendants(int n, ArrayList arrayList) {//подсчет потомко
if (n>=size || arr.get(n)==null) return 0
arrayList.add(arr.get(n))
return 1 + countDescendants(2*n+1,arrayList)+countDescendants(2*n+2,arrayList)
int getSumPathLength(int n, int i)
if (n>=size || arr.get(n) == null)
return 0
return i + getSumPathLength(2*n+1, i+1) + getSumPathLength(2*n+2, i+1)
int getHeight(int n
if (n>= size || arr.get(n) == null)
return 0
else if (getHeight(2*n+1) > getHeight(2*n+2)
return getHeight(2*n+1) + 1
els
return getHeight(2*n+2) + 1
public void balance()
ArrayList list = new ArrayList()
int numDescendants = countDescendants(0, list)
list.sort(list.get(0).getTypeComparator())
init()
balance(list, 0, numDescendants-1)
// Calculate balance factor as ratio of sum of path lengths to number of node
public double getBalanceFactor()
int sumPathLengths = getSumPathLength(0, 0)
int numNodes = countDescendants(0, new ArrayList()) + 1; // add 1 for root nod
return (double)sumPathLengths / numNodes
// Calculate fill factor as ratio of number of nodes to maximum possible number of nodes in tre
public double getFillFactor()
int height = getHeight(0)
int numNodes = countDescendants(0, new ArrayList()) + 1; // add 1 for root nod
int maxPossibleNodes = (int)Math.pow(2, height) - 1
return (double)numNodes / maxPossibleNodes
}