我有一个程序，它采用两个二叉搜索树，tree1和tree2，其中填充了字符串。该程序对tree1 进行中序遍历，并且对于tree1 中的每个字符串，它在tree2 中搜索该字符串。我认为从tree2中的tree1中搜索每个值的复杂度为O(logn)，遍历tree1中的每个值的复杂度为O(n)。这是否意味着整个过程是O(nlogn)，n用于遍历tree1获取每个值，logn在tree2中找到该值？我不太擅长理解大 O 表示法，因此感谢任何帮助或解释。谢谢!
最佳答案
思考这个问题的另一种方式是:
你有一个排序数组 t1 :
var t1 = ['1','2','3','4']
你有一个既排序又尽可能平坦的树，每个节点最多有 2 个子节点(二叉搜索树)
var t2 = '1' -> '2' -> '4'
-> '3'
现在，对于 t1 中的每个元素，您将在 t2 中搜索该元素。正如您所想 - 这意味着执行 n 次 logN 操作，这会给您 nlogn 总计算
关于java - 二叉搜索树的搜索和比较内容的大O，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33988612/