Ejemplos: 

Insertando 5, 3, 2, 4, 8: 

     5

    / \

   3   8

  / \    

 2   4

El peor caso es buscar 2 ó 4 (3 comparaciones) 
En media 11/5=2,2 

Insertando 4, 5, 8, 2, 3: 

     4

    / \

   2   5

    \   \

     3   8

El peor caso es buscar 3 ó 8 (3 comparaciones) 
En media 11/5=2,2 

Insertando 2, 3, 5, 4, 8: 

   2

    \

     3

      \

       5

      / \  

     4   8

El peor caso es buscar 4 ó 8 (4 comparaciones) 
En media 14/5=2,8 

Insertando 2, 3, 4, 5, 8: 

   2

    \

     3

      \

       4

        \  

         5 

          \

           8

El peor caso es buscar 8 (5 comparaciones) 
En media 15/5=3 
  

     Buscar un nodo cuesta el nivel del nodo +1. 

     El coste en caso peor es la altura del árbol +1. 
     La altura de un BST de N nodos puede valer desde log2(N) hasta N-1 

     El coste en caso medio es el nivel medio de los nodos +1. 
 

Intuitivamente: 

     El mejor caso son los árboles "poblados", que son anchos y no
     profundos 
     El peor caso son los árboles "alargados", que son profundos y estrechos