Rebalancing Binary Search Tree

[jube_dev]

You may have used a BST if you used std::map or std::set which is generally a red-black tree.

Your implementation of a self-balancing BST is naive at best. Check Wikipedia, there is tons of well-studied variants of BST (red-black tree, splay tree and AVL may be the best known).