A continuum of monopole, dyon and black hole solutions exist in the Einstein-Yang-Mills theory in asymptotically anti-de Sitter space. Their structure is studied in detail. The solutions are classified by non-Abelian electric and magnetic charges and the ADM mass. The stability of the solutions which have no node in non-Abelian magnetic fields is established. There exist critical spacetime solutions which terminate at a finite radius, and have universal behavior. The moduli space of the solutions exhibits a fractal structure as the cosmological constant approaches zero.