algorithm - 有人可以解释一下这个二叉树移植算法吗？

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，它将一个子树作为其父级的子树替换为另一棵子树。当用以 node 为根TRANSPLANT的子树替换以 nodeu为根的子树时， nodeu的父级将成为 node 的父级，并且u' 的父级最终具有其适当的子级。

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 }