0

我有这个问题需要解决。我不是在寻找答案，而是在寻找我应该去哪里的提示。我有一个算法，但不是 O(log n)。

给定二叉树 T 和一个不大于 T 中节点数的正整数 k，编写识别 T 中的元素 v 的伪代码，使得 T 中的 k-1 个元素恰好小于 v。您的代码应该花费时间与T的高度成正比。

我这里的基本想法是我会首先检查左树，检查左树的大小。如果左树的大小大于 k-1，则继续向左搜索。否则我会搜索正确的。如果整个左树不包含具有 k-1 个元素的节点，那么我搜索右子树。问题是我知道这不是 O(log n)，因为最坏的情况是我必须搜索树中的每个节点。

有什么我想念的吗？任何提示或帮助都会很棒，但请不要只给我答案。

4

3 回答 3

0

它与快速选择几乎相同的算法。根据左分支的大小递归到左分支或右分支。

Find(T, k) :=
    size(T.left) == k - 1 -> return T
    size(T.left) > k - 1 -> return Find(T.left, k)
    size(T.left) < k - 1 -> return Find(T.right, k - size(T.left) - 1)

问题中没有直接给出（但在评论中澄清）size（T）是O（1）。

这最多需要 height(T) 个步骤，因为在每个递归步骤中高度至少减少 1。

你也可以迭代地写这个：

Find(T, k) := 
   while size(T.left) != k - 1:
       if size(T.left) > k - 1:
           T = T.left
       else:
           T = T.right
           k -= size(T.left) + 1
   return T
于 2013-09-28T12:21:57.163 回答
0

（我假设这棵树实际上是一棵二叉搜索树，而不仅仅是任何旧的二叉树）

您的算法是O(d)，d树的最大深度在哪里。

这是因为每次您进行比较时，您都会继续往下一层（假设您还没有找到该元素）。因此，您最多将进行与树中的级别一样多的比较。

因此，除非您的树真的不平衡，否则您实际上不会查看每个元素。事实上，如果您可以假设树是平衡的，那么您就可以开始了（为什么？）。

于 2013-09-28T01:22:33.563 回答
0

如果我们谈论的是常规二叉树，很容易证明您需要探索整棵树才能找到这样的节点，所以我假设我们谈论的是二叉搜索树。

在二叉搜索树中，以下小于节点 N：

  • 节点 A，它的左孩子和它的所有后代，其中节点 B 是节点 A 的右孩子，节点 B 是节点 N 或其任何祖先。

        A
   / \
  X   B
 /     \
Y      ...
 \     /
  Z   N

    A、X、Y 和 Z 都小于 N。（根据相同的规则，B 也小于 N）。

  • 节点 N 的左孩子

我怀疑你假设所有的孩子都更小。

**剧透警报**

算法：

寻找m元素较小的节点...

  1. 从顶部开始。

  2. 让x= 左子树中的节点数（如果没有左子树，则 x = 0）

  3. 如果x = m，则返回当前节点。

  4. 如果x < m，则向左递归。

  5. 如果x > m，设置m = m - x - 1并递归右。

由于您只能向左或向右，并且节点数是恒定的（因为它是在节点级别上给出的），所以运行时间是O(h)树h的高度，它O(log n)位于平衡树中。

于 2013-09-28T11:07:07.350 回答