It's fairly easy to do this kind of thing using an arena and indices instead of pointers. Here's a simple splay tree with uplinks implemented this way:

https://github.com/stjepang/vec-arena/blob/master/examples/s...