二叉樹vs二進制搜索樹大哦分析

Question

平衡二叉搜索樹能否幫助您在比平衡二叉樹更快的大時間內完成以下任務？

創建樹小於某些值V較小的所有元素的列表。

在我看來沒有，因爲如果在BST所有的值是什麼小於V，那麼你就必須訪問每個節點，那就是O（n），它不比二叉樹好。

我正確嗎？

Answer 1

在我看來沒有，因爲如果有什麼的BST所有值都小於V 。然後，你將不得不訪問每個節點，這將是爲O（n） 這並不比二元更好樹。

我正確嗎？

你是。但是請注意，出於所有實際目的，最好使用BST，因爲對於「普通」二叉樹，您必須訪問所有節點以訪問所有節點，以便在小於v的情況下訪問所有節點，而在具有按順序遍歷的BST中，您只能檢查那些小於v的節點小於v。