Open
Description
We have
link :: a -> Set a -> Set a -> Set a
link x Tip r = insertMin x r
link x l Tip = insertMax x l
link x l@(Bin sizeL y ly ry) r@(Bin sizeR z lz rz)
| delta*sizeL < sizeR = balanceL z (link x l lz) rz
| delta*sizeR < sizeL = balanceR y ly (link x ry r)
| otherwise = bin x l rSeveral places we call this, we know that only one subtree could possibly be heavy. So we should add
linkL :: a -> Set a -> Set a -> Set a
linkL x l Tip = insertMax x l
linkL x (Bin sizeL y ly ry) r@(Bin sizeR z lz rz)
| delta*sizeR < sizeL = balanceR y ly (link x ry r)
linkL x l r = bin x l rand linkR similarly.
So I don't forget: these should be useful for implementing insert2 and insert2R for two-element union special cases. If both elements go left/right, we only need to check balance one way; if one goes left and the other right, we don't need to check balance at all.