Topic: Merkle Trees - How many leaf nodes in a tree with N total nodes? (Read 2640 times)

int GetNodeCount(int leafCount) {
    int nodeCount = 1;
    for (int i = leafCount; i > 1; i = (i + 1) >> 1)
        nodeCount += i;
    return nodeCount;
}

public static ulong ToWaltzIndex(int level, ulong offset)
{
    return (offset * (1u << (level + 1))) + (1u << level) - 1;
}

/// 

///     We know that:
///     * All positive integers are valid leafCounts
///     * Only certain values are valid nodeCounts.
///     * There is a 1:1 mapping between leafCount:nodeCount
///     * When listed in order, the differences between the valid nodeCount values follows the waltz series
///     * When the tree is complete (aka symetric) then: leafCount = (nodeCount + 1) / 2
///     Therefore:
///     * The difference between any nodeCount and the nodeCount of a complete tree with the same height
///     must be the sum of K elements of the waltz series.
///     * nodeDiff = sum(waltz[0],...,waltz[K-1])
///     * X = GetWaltzSumCount(nodeDiff)
///     * leafCount = maxLeafCount - X
/// 

public static ulong GetLeafCount(ulong nodeCount)
{
	//max possible leaf count at the current height
	ulong maxLeafCount = Pow2Prev(nodeCount);

	//max possible total node count at the current height
	ulong maxNodeCount = (maxLeafCount * 2) - 1;

	//Get the difference between the current node count and the max node count
	ulong nodeDiff = maxNodeCount - nodeCount;

	//if numNodes equals maxNodes then leafCount must equal maxLeafCount
	if (nodeDiff == 0)
		return maxLeafCount;

	//Subtract the number of summed waltz elements (steps) that are required to equal nodeDiff, from maxLeafCount
	return maxLeafCount - GetWaltzSumCount(nodeDiff);
}

///     Returns the number of elements that need to be added in order to reach the target value. 
/// 
/// The target result to emulate
/// The number of consecutive elements that need to be added together before reaching the target
public static ulong GetWaltzSumCount(ulong target)
{
	ulong counter = 0;
	ulong sum = 0;

	while (sum < target)
		sum += GetWaltzValue(++counter) + 1;

	if (sum > target)
		counter--;

	return counter;
}

/// 

///     A waltz value is the amount of times a number can be halved without leaving a remainder. These
///     values (series) are useful for navigating and storing binary tree structures.
/// 

/// A positive int greater than 0
public static uint GetWaltzValue(ulong number)
{
	//Covers all unsigned 64bit values
	const uint maxDivisions = 64;

	ulong num = number;

	for (uint i = 0; i <= maxDivisions; i++)
	{
		if ((num % 2) == 1)
			return i;

		num = num / 2;
	}

	throw new IndexOutOfRangeException("Could not find Waltz value for number: " + number);
}

int GetNodeCount(int leafCount) {
    int nodeCount = 1;
    for (int i = leafCount; i > 1; i = (i + 1) >> 1)
        nodeCount += i;
    return nodeCount;
}