Let's say that you have created a class that creates a rb-tree(dinamically allocating the nodes). How would you clean it up in the destructor? Erase one node at a time? that would mean that destroying the tree is an O(nlog(n)) operation. Another way would be to do a visit in order of the tree and put pointers to the elements on a vector and then free them. This way the destruction of the tree would be an O(n) operation. There are probably other ways to achieve this, but it was just an example.