None of the answers mention what it is exactly BSTs are good
for. If what you want to do is just lookup by values then a
hashtable is much faster, O(1) insert and lookup (amortized best
case). A BST will be O(log N) lookup where N is the height of
the tree, inserts are also O(log N). RB and AVL trees are
important like another answer mentioned because of this
property, if a plain BST is created with in-order values then
the tree will be as high as the number of values inserted, this
is bad for lookup performance. The difference between RB and AVL
trees are in the the rotations required to rebalance after an
insert or delete, AVL trees are O(log N) for rebalances while RB
trees are O(1). An example of benefit of this constant
complexity is in a case where you might be keeping a persistent
data source, if you need to track changes to roll-back you would
have to track O(log N) possible changes with an AVL tree. Why
would you be willing to pay for the cost of a tree over a hash
table? ORDER! Hash tables have no o