Home | Notifications | New Note | Local | Federated | Search | Logout

Note Detail

Reply to @dthompson@toot.cat
Robin H. Hansen@robinheghan@snabelen.no (2026-10-27 16:22:37)
@dthompson @pinoaffe I found this paper sometime last year. It uses the sub-tree height to determine the need for rotations. The benefit is that insert and remove are straight forward, and I believe performance is comparable to a red-black tree.

https://www.sciencedirect.com/science/article/pii/S0304397512010572?via%3Dihub
---Reply---
dave@dthompson@toot.cat (2026-10-27 21:19:06)
@robinheghan @pinoaffe I took a look and it seems that it uses the subtree *size*, the number of elements in the subtree, rather than the height. it looks interesting but I'm not sure I see a real advantage over AVL trees since they both have the same balance factor and the same worst case behavior.