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

Note Detail

Reply to @pinoaffe@hsnl.social
dave@dthompson@toot.cat (2026-10-26 23:02:12)
@pinoaffe my experience has been that the addition of red-black rebalancing rules to the insert operation works and is worth it. deletion is more complicated and I'm not done with implementation but it's probably worth the complexity. we could explore using a different balanced binary tree, as well, but red-black feels like a sweet spot between time spent rebalancing and query speed.
---Reply---
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

---Replies---

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.