A bijective map \(r: X^2 \longrightarrow X^2\), where \(X = \{x_1, ..., x_n \}\) is a finite set, is called a \emph{set-theoretic solution of the Yang-Baxter equation} (YBE) if the braid relation \(r_{12}r_{23}r_{12} = r_{23}r_{12}r_{23}\) holds in \(X^3.\) A non-degenerate involutive solution \((X,r)\) satisfying \(r(xx)=xx\), for all \(x \in X\), is called \emph{square-free solution}. There exist close relations between the square-free set-theoretic solutions of YBE, the semigroups of I-type, the semigroups of skew polynomial type, and the Bieberbach groups, as it was first shown in a joint paper with Michel Van den Bergh. In this paper we continue the study of square-free solutions \((X,r)\) and the associated Yang-Baxter algebraic structures -- the semigroup \(S(X,r)\), the group \(G(X,r)\) and the \(k\)- algebra \(A(k, X,r)\) over a field \(k\), generated by \(X\) and with quadratic defining relations naturally arising and uniquely determined by \(r\). We study the properties of the associated Yang-Baxter structures and prove a conjecture of the present author that the three notions: a square-free solution of (set-theoretic) YBE, a semigroup of I type, and a semigroup of skew-polynomial type, are equivalent. This implies that the Yang-Baxter algebra \(A(k, X,r)\) is Poincar\'{e}-Birkhoff-Witt type algebra, with respect to some appropriate ordering of \(X\). We conjecture that every square-free solution of YBE is retractable, in the sense of Etingof-Schedler.