查找樹中列表的時間複雜度

Question

我正在研究算法和數據結構類的項目。

如果我有一個二叉搜索樹，其中每個節點包含：

typedef struct Node { 
    char* name; 
    List* list; 
    struct Node *right; 
    struct Node *left; 
} Node; 

，我想搜索該列表中所確定的值，這將是本次搜索的時間複雜度？我知道列表中搜索的時間複雜度是O（n），但我也想要說明樹中搜索的時間複雜度。該列表未排序，BST按字母順序排列。

Answer 1

A 非平衡二叉搜索樹可退化爲鏈表，所以最壞情況的複雜度仍然是O(n)。

Answer 2

的答案歸結爲「排序樹」（和有用的順序。）

如果你需要搜索的所有節點，所有列表中的每個節點，（平均情況下）的時間複雜度會爲O(n*m)，其中n是列表的平均長度，m是樹中節點的數量。

如果您只能檢查某個路徑（類似於您只能在二叉搜索樹中搜索一條路徑），則（平均情況下）複雜度爲O(n*logm)。