二叉平衡树算法的时间复杂度

我们在计算时间复杂度的过程中，查找单个元素总是会出现的时间复杂度，这个时间复杂度如何计算得来的？
我们在二叉平衡树中搜索一个元素的过程最多的判断次数其实就是数的高度。

例如

平衡二叉树.png

上述途中描述了如何找到元素16的位置，可以发现一共对比了3次，正好是二叉平衡树的高度。

理论

假设树中的元素总数为n，则有

因此当查询单个元素其时间复杂度为.
按照时间复杂度原则，其时间复杂为上述的，总共有n个元素，因此总的时间复杂度为。