private static void allocateNodeLengthsWithRelocation (final int[] array, final int nodesToMove, final int insertDepth) {

		int firstNode = array.length - 2;
		int nextNode = array.length - 1;
		int currentDepth = (insertDepth == 1) ? 2 : 1;
		int nodesLeftToMove = (insertDepth == 1) ? nodesToMove - 2 : nodesToMove;

		for (int availableNodes = currentDepth << 1; availableNodes > 0; currentDepth++) {
			final int lastNode = firstNode;
			firstNode = (firstNode <= nodesToMove) ? firstNode : first (array, lastNode - 1, nodesToMove);

			int offset = 0;
			if (currentDepth >= insertDepth) {
				offset = Math.min (nodesLeftToMove, 1 << (currentDepth - insertDepth));
			} else if (currentDepth == (insertDepth - 1)) {
				offset = 1;
				if ((array[firstNode]) == lastNode) {
					firstNode++;
				}
			}

			for (int i = availableNodes - (lastNode - firstNode + offset); i > 0; i--) {
				array[nextNode--] = currentDepth;
			}

			nodesLeftToMove -= offset;
			availableNodes = (lastNode - firstNode + offset) << 1;
		}

	}