I am confused by this question. Both noms and dolt, and presumably most other prolly tree implementations do what you propose. if they didn't, inserts would be terribly slow.