BST中的時間複雜度

Question

在什麼情況下，使用二叉搜索樹搜索一個詞需要的時間複雜度與詞彙詞彙的大小（比如M）成線性關係？如何確保log M的最糟時間複雜度？

Answer 1

一個完整的二叉樹是一個完整的二叉樹，除了可能的最後一個以外，每一層都被完全填滿。最差的搜索性能是樹的高度，在這種情況下，樹的高度爲O(lgM)，假設樹中有詞彙詞M。

確保這種性能的一種方法是使用自平衡樹，一棵紅黑樹。