查找树中列表的时间复杂度

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)。