構建二叉搜索樹時的比較次數

Question

我正在自學二叉搜索樹。有一個問題，詢問在初始空樹中插入字母E，A，S，Y，Q，U，E，S，T，I，O和N時需要多少次比較來構建樹。

我畫了二叉搜索樹，並計算插入每個元素時的比較次數。

E 
/\ 
A S 
    /\ 
    Q Y 
//
E U 
\ /
    I S 
    \ \ 
    O T 
    /
    N 

我得到了36

是正確的嗎？另外，還有另一種方法可以知道比較次數而不必繪製樹？

Answer 1

比較次數爲36次。

可以得出結論，插入比較的最大數量BST一個元素不會是樹超過高度。