7

このアルゴリズムは教科書で見つけましたが、よくわかりません。

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 をルートとするサブツリーを node をルートとするサブツリーにTRANSPLANT置き換えるuと、 nodeuの親は node の親になり、 node の親は最終的uに適切な子になります。

4

1 に答える 1

10

私がコードを理解している限り、ノード u とそれに対応するサブツリーを他のノード v とそのサブツリーに置き換えようとします。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 }
于 2013-09-06T04:27:27.397 に答える