algorithm - 如何在 BST 中找到一个节点的前任节点，每个节点都有 3 个属性——succ、left 和 right？

Question

来自 CLRS 的问题，3ed。

12.3-5
Suppose that instead of each node x keeping the attribute x.p, pointing to x’s parent, it keeps x.succ, pointing to x’s successor. Give pseudocode for SEARCH,INSERT, and DELETE on a binary search tree T using this representation. These procedures should operate in time O(h), where h is the height of the tree T . (Hint:You may wish to implement a subroutine that returns the parent of a node.)

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

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

查看代码。

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;
}

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

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

注意操作INSERT，也需要找到一个节点的前导。

有一个问题——如果所有的键共享相同的值怎么办？然后我们无法通过比较找到x的前身，因为等于键x的键a可能出现在x中 的左子树或右子树。

Answer 1

如果 x 的左子树为空，则 x 的前身不仅仅是它的祖先，它是 x 的直接父级.因此，您只需调用一次 parent 子例程，使整个运行时 O(h)+O(h)=O(h)。

附言
即使它不是直接父级，您仍然不必重复调用 parent 来获取所有祖先，您可以从 x 的根开始搜索像往常一样创建树，在长度为 O(h) 的单个遍历中保存沿路径到 x 的所有节点。您在搜索 x 时经过的所有节点，并且只有那些节点，根据定义是 x 的祖先。