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

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为根的子树替换以节点为根的子树时,节点u的父节点成为节点的父节点,并且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 }