null(-)
t(X,t(X,Null,Null,1)) :- null(Null).

inct(t(X,L,R,N0),t(X,L,R,N)) :- N is N0 + 1.

insert(X,T0,T) :- insertR(T0,X,T).

insertR(-,X,T) :- t(X,T).
insertR(t(K0=V0,L,R,N),K=V,T) :-
	random(10000)/10000*N < 1
	-> insertT(t(K0=V0,L,R,N),K=V,T)
	;  compare(Op,K0,K),
	   insertR1(Op, t(K0=V0,L,R,N),K=V,T1),
	   incT(T1,T).

insertR1(<, t(K,L0,R, N),X, t(K,L,R,N)) :- insertR(L0,X,L).
insertR1(=, t(K,L, R0,N),X, t(K,L,R,N)) :- insertR(R0,X,,R).
insertR1(>, t(K,L ,R0,N),X, t(K,L,R,N)) :- insertR(R0,X,,R).

insertT(-,X,T) :- t(X,T).
insertT(t(K0=V0,L,R,N),K=V,T) :-
	compare(Op,K0,K),
	insertT1(Op,t(K0=V0,L,R,N),K=V,T).

insertT1(<,t(K=L0,R,  N),X,T) :- insertT(L0,X,L), rotR(t(K=L,R,N),T).
insertT1(=,t(K=L ,R0, N),X,T) :- insertT(R0,X,R), rotL(t(K=L,R,N),T).
insertT1(>,t(K=L ,R0, N),X,T) :- insertT(R0,X,R), rotL(t(K=L,R,N),T).

rotR(t(Ns,t(Ne,Le,Re),Rs), t(Ne,Le,t(Ns,Re,Rs))).
rotL(t(Na,La,t(Ne,Lc,Rs)), t(Ne,t(Na,La,Lc),Rs)).