I would like to know which balanced BST would be easy to code in C++, and still have a complexity roughly equal to O(logn).
I've already tried Red Black trees, but would like an alternative that is less complex to code. I have worked with Treaps in the past, but am interested in exploring options that either perform better or are easier to implement.
What are your suggestions?
AVL trees generally perform better than Treaps in my experience, and they're not any harder to implement.
They work by rotating branches of the tree that become unbalanced after any insertion or deletion. This guarantees that they will have perfect balance so they can't be "tricked" by strange data.
Treaps on the other hand are distributed randomly, which for large data sets is close to balanced, but you still don't get that perfect O(logn). Furthermore you could just happen to come across a data set that inserts in a very unbalanced way, and your access time can get close to O(n).
Check out wikipedia's page for more info: en.wikipedia.org/wiki/Avl_tree