For the space of (not necessarily polynomial) Hermite type splines we develop algorithms for constructing the spline-wavelet decomposition provided that an arbitrary coarsening of a nonuniform spline-grid is a priori given. The construction is based on approximate relations guaranteeing the asymptotically optimal (with respect to the N-diameter of standard compact sets) approximate properties of this decomposition. We study the structure of restriction and extension matrices and prove that each of these matrices is the one-sided inverse of the transposed other. We propose the decomposition and reconstruction algorithms consisting of a small number of arithmetical actions.