二叉樹的理想拓撲？

Question

二分查找樹（BST）的理想拓撲是什麼意思？我明白，任何對值的搜索都應該以對數時間複雜度進行，但它是否需要「精確」記錄？除了最後一行（如堆），樹必須是完整的樹嗎？還是應該大致平衡？我真的試過搜索，但沒有得到任何體面的答案。

例如：

       25 
          / \ 
          10  50 
         /  \ 
         9    62 
            / \ 
            55 70  

難道這棵樹有一個理想的拓撲結構？

或者是理想的拓撲結構，可以從一組數據構建的最佳平衡BST？所以它不是可以檢查的樹的身份？

什麼是BST的理想拓撲結構？

Answer 1

你的例子是不平衡的，因爲你不能在55之​​下放置一個55，因爲它比50更大，你可以在小50中插入任何小於50或50的值。 理想的拓撲結構意味着該樹很容易訪問和操作，並且它以一種通用的方式進行排序（在您的情況下，可以很容易地進行刪除）。 它可以是偶數和偶數的拓撲，偶數在右邊，可能性在左邊。 我希望我回答你的問題。