3 ms·

Do you mean tree rebalancing algorithms? I have to agree with this. AVL tree insertion is fine enough, but it gets hairy when you get to deletion. And Red-Black

Do you mean tree rebalancing algorithms? I have to agree with this. AVL tree insertion is fine enough, but it gets hairy when you get to deletion. And Red-Black trees…

charlieyu1 3y ago
There are more than that, even finding diameter of a tree is pretty nasty
- qsantos 3y ago
  Ah yes, but I use Rust, I cannot go back up a tree (-:
  - KRAKRISMOTT 3y ago
    No graphs either :(
- n2d4 3y ago
  Only nasty to find diameter of general graphs, right? If you know you have a tree, just root it at a random vertex and recursively compute `max(largest diameter of children, sum of the two biggest heights of children)`
peterfirefly 3y ago
Once you relax the invariants a bit, it becomes much easier to delete from your reddish-blackish trees :) If you don't have to implement deletion, things are already a lot easier. And if you decide to implement a persistent red-black tree then they can be downright easy, even without relaxed invariants. Relaxed invariants: https://en.wikipedia.org/wiki/AA_tree https://en.wikipedia.org/wiki/AA_tree https://en.wikipedia.org/wiki/Left-leaning_red%E2%80%93black_tree https://en.wikipedia.org/wiki/Left-leaning_red%E2%80%93black... --- Years ago, I played around with red-black trees and I figured that I could relax the invariants and make the code a lot simpler -- and maybe get slightly worse theoretical performance and quite likely slightly better practical performance for small trees. I looked around for other people's ideas along the same lines and found AA trees, which didn't quite please me. A few years later, Sedgewick's left-leaning red-black trees came out. I would probably have found them myself (+ some other related ideas) if I had continued to play around + systematically tried different relaxations. But I didn't, so I didn't.
- qsantos 3y ago
  I never heard of these, thanks for the links!

Do you mean tree rebalancing algorithms? I have to agree with this. AVL tree insertion is fine enough, but it gets hairy when you get to deletion. And Red-Black trees…

charlieyu1 3y ago

There are more than that, even finding diameter of a tree is pretty nasty

qsantos 3y ago
Ah yes, but I use Rust, I cannot go back up a tree (-:
- KRAKRISMOTT 3y ago
  No graphs either :(
n2d4 3y ago
Only nasty to find diameter of general graphs, right? If you know you have a tree, just root it at a random vertex and recursively compute `max(largest diameter of children, sum of the two biggest heights of children)`

peterfirefly 3y ago

Once you relax the invariants a bit, it becomes much easier to delete from your reddish-blackish trees :) If you don't have to implement deletion, things are already a lot easier. And if you decide to implement a persistent red-black tree then they can be downright easy, even without relaxed invariants. Relaxed invariants: https://en.wikipedia.org/wiki/AA_tree https://en.wikipedia.org/wiki/AA_tree https://en.wikipedia.org/wiki/Left-leaning_red%E2%80%93black_tree https://en.wikipedia.org/wiki/Left-leaning_red%E2%80%93black... --- Years ago, I played around with red-black trees and I figured that I could relax the invariants and make the code a lot simpler -- and maybe get slightly worse theoretical performance and quite likely slightly better practical performance for small trees. I looked around for other people's ideas along the same lines and found AA trees, which didn't quite please me. A few years later, Sedgewick's left-leaning red-black trees came out. I would probably have found them myself (+ some other related ideas) if I had continued to play around + systematically tried different relaxations. But I didn't, so I didn't.

qsantos 3y ago
I never heard of these, thanks for the links!