Basically, we shouldn't be using toList and fromList to implement other functions. Implement for and rfor traversals directly and use them instead when necessary.
The union function is implemented with the wrong complexity: it should be O(min(n,m) * log(max(n,m))) where n, m are the sizes of arguments. So that the following
for (acc := Set.empty) (x in sets) {Set.union acc x}
always has complexity O(k * log(k)) where k is the size of the result.
In union one needs to check the heights and traverse the tree with the smaller height inserting into the one with larger height.
Basically, we shouldn't be using
toListandfromListto implement other functions. Implementforandrfortraversals directly and use them instead when necessary.The
unionfunction is implemented with the wrong complexity: it should beO(min(n,m) * log(max(n,m)))wheren,mare the sizes of arguments. So that the followingalways has complexity
O(k * log(k))wherekis the size of the result.In
unionone needs to check the heights and traverse the tree with the smaller height inserting into the one with larger height.