3

来自 CLRS 的问题，3ed。

12.3-5
假设不是每个节点 x 保持属性 xp 指向 x 的父节点，而是保持 x.succ 指向 x 的后继节点。使用这种表示法在二叉搜索树 T 上给出 SEARCH、INSERT 和 DELETE 的伪代码。这些过程应该在 O(h) 时间内运行，其中 h 是树 T 的高度。（提示：您可能希望实现一个返回节点父节点的子程序。）

我知道如何实现一个在 O(h) 时间内返回节点父节点的子程序。

要找到节点的父节点，我们应该首先找到以子树为根x的最大键。然后，我们从 向右下。当我们到达时，我们之前遇到的节点是的父节点。MxM.succ.leftxxx

查看代码。

typedef struct TREE{
  struct TREE* left,right,succ;
}*BST;

PARENT(BST x)
{
  if(x==root) return NULL;
  BST max=TREE_MAXIMUM(x);
  BST parent=max->succ,t;
  if(parent) t=parent->left;
  else t=root;
  while(t!=x){parent=t;t=t->right;}
  return parent;
}

时DELETE x，x前身的succ应该被修改为指向x.succ，不再x。那么问题来了——如何x在 O(h) 时间内找到 的前身？

当 的左子树不x为空时，它是 的左子树中最右边的节点x。但是，当 的左子树x为空时，前驱是x的祖先，要找到调用 的 O(h) 次PARENT。这需要 O(h*h) 时间吗？还是应该从根向下搜索？

请注意，操作INSERT, 还需要找到一个节点的前任。

有一个问题——如果所有的键共享相同的值怎么办？那么我们不能通过x比较找到 ' 的前任，因为与 keya相等的 keyx可能出现在x' 的左子树或右子树中。

4

3 回答 3

1

如果 的左子树x为空，则 的前身x不仅是其祖先，还是 的直接父级x。因此，您只需要parent对子例程进行一次调用，即可完成所有运行时O(h)+O(h)=O(h).

PS
即使不是直接父节点，也不必重复调用来获取所有祖先节点，可以像往常一样从树根parent开始搜索，保存路径上的所有节点x在x一次长度遍历中O(h)。您在搜索时经过的所有节点x，并且只有那些节点，根据定义是 的祖先x。

于 2015-09-24T07:34:20.163 回答
0

如果键是离散的，则 x 的前身具有 <= key(x)-1 的键，对吗？如果你在树中搜索 key(x)-1 会发生什么？在遍历期间您不一定会遇到 pred(x) 吗？你必须仔细检查我。当然，非离散键（例如浮点）可能是有问题的（至于-1）。

于 2015-09-26T19:53:42.230 回答
0

注意：O(h) 仅在根直接可用时才有可能。（应该是这种情况）

稍微改变一下你的数据结构。

typedef struct TREE{
 int key;
 struct TREE* left,right,succ;
}*BST;

如果左子树非空，我们使用 TREE_MAXIMUM，否则我们在 BST 中搜索 x，从根开始搜索并维护（在变量目标中）遇到右子节点的最后一个（即最新）节点。在搜索结束时，目标是前任。

前身功能

 BST PRE(BST x)
    {
      if(x->left!=NULL)
          return TREE_MAXIMUM(x->left);
      if(x== root)
          return NULL;
      BST goal = NULL, y = root;
      while(1)
      {
        if(x->key <= y->key)
            y=y->left;
        else
        {
            goal=y;
            y=y->right;
        }
        if(x==y)
        {
            return goal;
        }
      }      
    }
于 2015-09-28T11:15:54.893 回答