The emerging high-efficiency video coding standard achieves higher coding efficiency than previous standards by virtue of a set of new coding tools such as the quadtree coding structure. In this novel structure, the pixels are organized into coding units (CU), prediction units, and transform units, the sizes of which can be optimized at every level following a tree configuration. These tools allow highly flexible data representation; however, they incur a very high computational complexity. In this paper, we propose an effective complexity control (CC) algorithm based on a hierarchical approach. An early termination condition is defined at every CU size to determine whether subsequent CU sizes should be explored. The actual encoding times are also considered to satisfy the target complexity in real time. Moreover, all parameters of the algorithm are estimated on the fly to adapt its behavior to the video content, the encoding configuration, and the target complexity over time. The experimental results prove that our proposal is able to achieve a target complexity reduction of up to 60% with respect to full exploration, with notable accuracy and limited losses in coding performance. It was compared with a state-of-the-art CC method and shown to achieve a significantly better trade-off between coding complexity and efficiency as well as higher accuracy in reaching the target complexity. Furthermore, a comparison with a state-of-the-art complexity reduction method highlights the advantages of our CC framework. Finally, we show that the proposed method performs well when the target complexity varies over time.