To be honest, one reason I delayed getting back to this was that I didn’t want to use the resources that I pointed to, but rather I wanted to work the rebalancing from first principles myself. This is partly because that was how we had to do it when I first wrote one many years ago: rotations were described, but not how to recalculate the balances. Even worse… the online resource we used made the claim that all write operations were O(1), but this is only true for insertions. Deletions have a worst case of O(log(n)), and the deletions described were buggy because they did not include this. A colleague and I had to sit down and work deletions through from scratch to get it right. This experience stayed with me, and it’s what motivated me to make sure I had it all fresh in my head before writing about it.
Fortunately, I won’t be needing to delete from trees in the design I’m building towards, which has allowed me to skip these complexities.
To see the production code that we built for this (including this elusive delete operation) it’s all in the AVLNode code for Mulgara.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
To be honest, one reason I delayed getting back to this was that I didn’t want to use the resources that I pointed to, but rather I wanted to work the rebalancing from first principles myself. This is partly because that was how we had to do it when I first wrote one many years ago: rotations were described, but not how to recalculate the balances. Even worse… the online resource we used made the claim that all write operations were O(1), but this is only true for insertions. Deletions have a worst case of O(log(n)), and the deletions described were buggy because they did not include this. A colleague and I had to sit down and work deletions through from scratch to get it right. This experience stayed with me, and it’s what motivated me to make sure I had it all fresh in my head before writing about it.
Fortunately, I won’t be needing to delete from trees in the design I’m building towards, which has allowed me to skip these complexities.
To see the production code that we built for this (including this elusive
deleteoperation) it’s all in the AVLNode code for Mulgara.