4 ms·
Insertion in AVL tree's is fairly simple and doesn't really have any cascades so they are quite predictable, deletions on the other hand cascades upwards with a
by whizzter 2y ago
Insertion in AVL tree's is fairly simple and doesn't really have any cascades so they are quite predictable, deletions on the other hand cascades upwards with a bunch of different imbalances and thus rotations(and post rotation balances) to be accounted for.
Recently implemented them for an advanced hobby project and having a solid fuzzing tester in place really alleviated a lot of headaches in the long term since it was able to produce quite an exhaustive set of conditions.
- nayuki 2y agoB-tree deletions are quite complicated too, requiring stealing keys from either-side sibling or merging with either-side sibling. In practice, I find that a B-tree implementation is 2 to 3× the length of an AVL tree impl. I also fuzz-tested my implementations thoroughly. https://www.nayuki.io/page/avl-tree-list https://www.nayuki.io/page/avl-tree-list , https://www.nayuki.io/page/btree-set https://www.nayuki.io/page/btree-set , etc.
- DanielHB 2y agoYeah, this is what I was thinking too. The rebalancing on AVL is a bit tricky but once you grok it, it is not that much code...