> with O(1) typical insert This isn't the case. Half the inserts become leaves, which don't require restructuring but do require O(lg n) to find the insertion

> with O(1) typical insert This isn't the case. Half the inserts become leaves, which don't require restructuring but do require O(lg n) to find the insertion point.