To determine and analyze arbitrary left non-degenerate set-theoretic solutions of the Yang-Baxter equation (not necessarily bijective), we introduce an associative algebraic structure, called a YB-semitruss, that forms a subclass of the category of semitrusses as introduced by Brzeziński. Fundamental examples of YB-semitrusses are structure monoids of left non-degenerate set-theoretic solutions and (skew) left braces. Gateva-Ivanova and Van den Bergh introduced structure monoids and showed their importance (as well as that of the structure algebra) for studying involutive non-degenerate solutions. Skew left braces were introduced by Guarnieri, Vendramin and Rump to deal with bijective non-degenerate solutions. Hence, YB-semitrusses also yield a unified treatment of these different algebraic structures. The algebraic structure of YB-semitrusses is investigated, and as a consequence, it is proven, for example, that any finite left non-degenerate set-theoretic solution of the Yang-Baxter equation is right non-degenerate if and only if it is bijective. Furthermore, it is shown that some finite left non-degenerate solutions can be reduced to non-degenerate solutions of smaller size. The structure algebra of a finitely generated YB-semitruss is an algebra defined by homogeneous quadratic relations. We prove that it often is a left Noetherian algebra of finite Gelfand-Kirillov dimension that satisfies a polynomial identity, but in general, it is not right Noetherian.