Trees don't have to have terrible locality. There are a number of tricks to encode parts of the tree structure into nice flat blocks. (This can involve some memory overhead, which may or may not be offset by the space saved on pointers depending on the size of elements.)
Just because std::set and map are completely awful doesn't mean you should completely give up on trees.
From my experience, using vector<list<int>> behaves more poorly due to terrible locality of lists. My use of red-black trees for graphs is mostly limited to implementing Dijkstra using set<pair<cost, node_index>> as a queue, since the priority_queue in <queue> does not have a DecreaseKey operation. Using that set (and some map (needn't be std::map, could well be a vector) of node_index to cost for faster compare during Dijkstra's neighbor loop) can make for a very fast, short, and easy to implement Dijkstra.
My usage is mostly competitive programming, so YMMV.