The emerging HEVC standard introduces several techniques which increase compression efficiency in comparison to its predecessors. However, such advances are accompanied by increases in computational complexity, limiting the encoder use in computational or power-constrained devices. This paper proposes a novel complexity control method for the future HEVC encoders based on a dynamic adjustment of the newly proposed coding tree structures. The relationship between coding tree depths and the encoding complexity is explored to selectively constrain encoding possibilities in order to not exceed a predefined complexity target. Experimental results show that the encoder computational complexity can be downscaled to 60% with a bit rate increase under 3.5% and a PSNR decrease under 0.1 dB.