Data Structures, Algorithms, & Applications in Java
Chapter 15, Exercise 17

We need to develop new code for the insert method only. When the element to be inserted equals an existing element, we must decide whether to insert the new element into the left or the right subtree of the existing element. Although we can arbitrarily decide to do the insertion in the left (or the right) subtree always, we expect to create trees with better balance (and hence smaller height) when this decision is made randomly and with equal probability. The code given below uses a random number generator to make this decision with equal probability. When the random number generated is less than 0.5 a left child move is made; otherwise a right child move is made. The code that is different from DBinarySearchTree is shown in red. 
public class NewDBinarySearchTree extends BinarySearchTree
                                  implements DBSTree
{
   // class data member
   static Random random = new Random();  // random number generator

   // override BinarySearchTree.put
   /** insert an element with the specified key
     * overwrite old element if there is already an
     * element with the given key */
   public void put(Object theKey, Object theElement)
   {
      BinaryTreeNode p = root,     // search pointer
                     pp = null;    // parent of p
      Comparable elementKey = (Comparable) theKey;
      // find place to insert theElement
      while (p != null)
      {// examine p.element.key
         pp = p;
         // move p to a child
         if (elementKey.compareTo(((Data) p.element).key) < 0)
            p = p.leftChild;
         else if (elementKey.compareTo(((Data) p.element).key) > 0)
                 p = p.rightChild;
              else
                 // make a random decision
                 if (random.nextFloat() < 0.5)
                    p = p.leftChild;
                 else p = p.rightChild;
      }
   
      // get a node for theElement and attach to pp
      BinaryTreeNode r = new BinaryTreeNode
                             (new Data(elementKey, theElement));
      if (root != null)
         // the tree is not empty
         if (elementKey.compareTo(((Data) pp.element).key) < 0 ||
           (elementKey.equals(((Data) pp.element).key)
            && pp.leftChild == null))
            pp.leftChild = r;
         else
            pp.rightChild = r;
         // could randomly select subtree in case of equal keys and pp a leaf
      else // insertion into empty tree
         root = r;
   }
}