BST中的时间复杂度

Question

在什么情况下，使用二叉搜索树搜索一个词需要的时间复杂度与词汇词汇的大小（比如M）成线性关系？如何确保log M的最糟时间复杂度？

Answer 1

一个完整的二叉树是一个完整的二叉树，除了可能的最后一个以外，每一层都被完全填满。最差的搜索性能是树的高度，在这种情况下，树的高度为O(lgM)，假设树中有词汇词M。

确保这种性能的一种方法是使用自平衡树，一棵红黑树。