<p>I've been able to find details on several self-balancing <code>BST</code>s through several sources, but I haven't found any good descriptions detailing which one is best to use in different situations (or if it really doesn't matter).  </p>

<p>I want a <code>BST</code> that is optimal for storing in excess of ten million nodes. The order of insertion of the nodes is basically random, and I will never need to delete nodes, so insertion time is the only thing that would need to be optimized.  </p>

<p>I intend to use it to store previously visited game states in a puzzle game, so that I can quickly check if a previous configuration has already been encountered.</p>

The two self-balancing
```
BST
```
s I'm most familiar with are red-black and
```
AVL
```
, so I can't say for certain if any other solutions are better, but as I recall, red-black has faster insertion and slower retrieval compared to
```
AVL
```
.
So if insertion is a higher priority than retrieval, red-black may be a better solution.