このコードでBSTから削除するには、この行が必要なのはなぜですか？

Question

私はバイナリツリーについてもっと学びたいと思っています。ノードを削除しようとすると、後継ノードを見つける方法について知りましたが、その一部を理解するのは苦労しています。 コードは次のとおりです。

private Node getSuccessor(Node delNode){ 
    Node successorParent = delNode; 
    Node successor = delNode; 
    Node current = delNode.rightChild; 

    while(current != null){ 
     successorParent = successor; 
     successor = current; 
     current = current.leftChild; 
    } // end of if 

    if(successor != delNode.rightChild){ 
     successorParent.leftChild = successor.rightChild; 
     successor.rightChild = delNode.rightChild; 
    } 
    return successor; 


} 

whileループとその中に入っているものを完全に理解しています。私は理解していないことはif文とされ、具体的...

successor.rightChild = delNode.rightChild; 

なぜ私は後続ノードの右の子にdelNodeの右の子を割り当てたいでしょう

？ if文が必要な理由

Answer 1

getSuccessor（）は、delNodeよりも小さい値を持つノード、つまりdelNodeの右側のサブツリーの一番左のノードであるdelNodeの後続ノードを見つけます。その後、それを右のサブツリーから削除し、右のサブツリーを後継者の右に接続します。

条件が成立した理由は、後継者がdelNodeの右の子である場合、既に右のサブツリーの先頭にあり、サブツリーから取り出さずに先頭に移動する必要があるということですそれの。

次の手順では、delNodeが削除され、後継ノードがdelNodeの親ノードに接続され、delNodeの下の左側のサブツリーが後継ノードの左側に追加されます。このすべての効果は、delNoteをその後継者に置き換えることです。

（この方法は、バイナリツリーからノードを削除する最も簡単な方法ではありません。右のサブツリーをdelNodeの親ノードに、左のサブツリーを後継の左に追加するだけです）。すべてのノードが同じ深さにとどまっているか、ルートに近づいているのでツリーの高さを増やさないという利点があります）。次にノード3を削除する例を示します。その後継者は4で、右のサブツリーから4を削除してサブツリーの先頭に配置し、ノード3を後継者4に置き換えて、左のサブツリーを添付します。

 9            9 
    /\           /\ 
    3 ...      4     4 ... 
/\        \    /\ 
    2 6    6    6    2 6 
//\   /\   /\   //\ 
1 4 7   4 7   5 7   1 5 7 
    \ \   \ \    \     \ 
     5 8   5 8    8     8 

（あなたがノードを削除した後、すべてのノードが同じ深さで、それは前だったされるか、またはルートに近い移動したので、木の高さが増加していないことがわかります。）

次に、ノード3を削除する例を考えてみましょう。ただし、ノード4の後継ノードがすでに右側のサブツリーの先頭にあることがわかります。それは我々がすぐに後継者4によりノード3を交換し、最初の右部分木の先頭にノード4を移動することなく、そこに左のサブツリーを添付することができます意味：

 8         8 
    /\        /\ 
    3 ...       4 ... 
/\        /\ 
    2 4    4    2 6 
/ \    \   //\ 
1  6    6   1 5 7 
    /\   /\   
     5 7   5 7   

Answer 2

このコードがあることを2つのケースがあります。説明しようとしている。あなたはその後継者Yは、そのすぐ右の子であるノードX削除しているところ最初は次のようになります。この場合、

X 
\ 
    Y 
    \ 
    Z 

を、我々は最終的にはYとXを交換しようとしているので、この方法は、単にYを返すことができますし、ここではXを置き換えるノードがあります一方、「

、Xの後継者Yは、その右の子ツリーのサブツリーであることとします

この場合

X 
\ 
    A 
/\ 
Y C 
\ 
    B 

そうだろうやっているので、我々は盲目的に、YとXを置き換えることはできません私たちが言う前に、だからサブツリーCにノードAとすべてを失う「ちょっと木 - 、ノードYとノードXを置き換えて行く」彼らはこのように見えるように、私たちは、ツリー内のノードを並べ替える：

X 
\ 
    Y 
    \ 
    A 
/\ 
    B C 

を今、 XをYに置き換えると、ツリー内の他のノードは失われていません。

ここでの形状は、XとYを交換し、Yの前の親をYの元の右のサブツリーに左の子として持つことによってXを削除することによって形成される。これらの行をトレースして、どのように動作するかを確認してください。