有人能向我解释一下这个二叉树移植算法吗？

Question

我在一本教科书中发现了这个算法，但我不确定是否理解它。

TRANSPLANT(T,u,v){
  1 if u.p == NIL
  2   T.root = v
  3 else if u == u.p.left
  4   u.p.left=v
  5 else u.p.right == v
  6 if v != NIL
  7   v.p=u.p
}

此外，你认为节点中的p是什么？

为什么他不能只比较节点与节点？

教科书笔记：

为了在二叉搜索树中移动子树，我们定义了一个子程序TRANSPLANT，它将一个子树替换为其父节点的另一个子树。当TRANSPLANT用以u为根节点的子树替换以v为根节点的子树时，u的父节点变成v的父节点，u的父节点最终将v作为其适当的子节点。

- AlanRubinoff

---

这段代码中的 p 代表“父级”，如 -> u.p // 表示 u 的父级引用。 - Haomin

Answer 1

据我理解这段代码，它试图用另一个节点v及其子树替换节点u及其相应的子树。我猜测p代表一个节点的父节点。

TRANSPLANT(T,u,v) {
1   if u.p == NIL          -- if u doesn't have a parent => u is the root
2       T.root = v         --   then v must replace u as the root of the tree T
3   else if u == u.p.left  -- if u is a left subtree of its parent
4       u.p.left = v       --   then v must replace u as the left  
-                          --   subtree of u's parent
5   else u.p.right == v    -- otherwise u is a right subtree 
-                          --   (as the tree is binary) and v must replace
-                          --   u as the right subtree of u's parent
6   if v != NIL            -- if v has replaced u (and thus is not NIL)
7       v.p = u.p          --   v must have the same parent as u
8 }

- yasen