我们总是看到（二叉搜索）树上的操作具有 O(logn) 最坏情况的运行时间，因为树的高度是 logn。我想知道我们是否被告知算法的运行时间是 logn 的函数，例如 m + nlogn，我们是否可以得出结论它必须涉及（增强的）树？
编辑：感谢您的评论，我现在意识到分治和二叉树在视觉/概念上是如此相似。我从来没有在两者之间建立联系。但我想到了一个 O(logn) 不是分治算法的情况，它涉及一棵没有 BST/AVL/红黑树属性的树。
这是具有 Find/Union 操作的不相交集数据结构，其运行时间为 O(N + MlogN)，其中 N 是元素的数量，M 是 Find 操作的数量。
如果我错过了某事，请告诉我，但我看不出分治法是如何在这里发挥作用的。我只是在这个（不相交集）案例中看到它有一个没有 BST 属性的树，并且运行时间是 logN 的函数。所以我的问题是关于为什么/为什么我不能从这个案例中做出概括。
不，您也可以对已排序的数组进行二进制搜索（例如）。但不要相信我的话http://en.wikipedia.org/wiki/Binary_search_algorithm
你所拥有的完全是倒退的。O(lg N)通常意味着某种分而治之的算法，实现分而治之的一种常见方式是二叉树。虽然二叉树是所有分治算法的重要子集，但无论如何它们都是子集。
在某些情况下，您可以将其他分而治之的算法相当直接地转换为二叉树（例如，对另一个答案的评论已经尝试声称二叉搜索是相似的）。然而，仅举另一个明显的例子，多路树（例如 B-树、B+ 树或 B* 树），而树显然不是二叉树。
同样，如果您非常想，您可以延伸多路树可以表示为二叉树的扭曲版本的点。如果您愿意，您可能可以将所有异常延伸到说它们都是（至少类似于）二叉树的程度。然而，至少对我来说，所做的只是让“二叉树”成为“分而治之”的同义词。换句话说，你所做的只是扭曲词汇并从本质上消除一个既独特又有用的术语。
作为一个反例：
given array 'a' with length 'n'
y = 0
for x = 0 to log(length(a))
y = y + 1
return y
运行时间为 O(log(n))，但这里没有树！
答案是否定的。有序数组的二分查找是O(log(n)).
取对数时间的算法常见于二叉树的运算中。
O(logn) 的例子：
使用二分搜索或平衡搜索树在已排序数组中查找项目。
按二分法在已排序的输入数组中查找一个值。
由于 O(log(n)) 只是一个上限，所以所有 O(1) 算法都function (a, b) return a+b;满足条件。
但我必须同意所有 Theta(log(n)) 算法看起来有点像树算法，或者至少可以抽象为树。
简短的回答：
仅仅因为算法将 log(n) 作为其分析的一部分并不意味着涉及到一棵树。例如，以下是一个非常简单的算法，即O(log(n)
for(int i = 1; i < n; i = i * 2)
print "hello";
如您所见，没有涉及任何树。John，还提供了一个很好的例子，说明如何在排序数组上进行二分搜索。这些都需要 O(log(n)) 时间，并且还有其他可以创建或引用的代码示例。所以不要根据渐近时间复杂度做假设，看代码就知道了。
更多关于树木：
仅仅因为算法涉及“树”并不意味着O(logn)。您需要知道树的类型以及操作如何影响树。
一些例子：
插入或搜索以下不平衡树将是O(n)。
插入或搜索以下平衡树都将通过O(log(n)).
平衡二叉树：
3 级平衡树：
补充评论
如果您使用的树木没有“平衡”的方法，那么您的操作很可能不会是O(n)时间O(logn)。如果您使用自平衡的树，则插入通常需要更多时间，因为树的平衡通常发生在插入阶段。