BST削除方法の説明

Question

私はバイナリツリーの概念を理解しています。私はこのメソッドで再帰呼び出しが何をしているのか理解していません。

public BSTNode<T> remove(T element, BSTNode<T> node) { 
    if (node == null) 
     return null; 
    else { 
     int cmp = element.compareTo((node.getValue())); 
     if (cmp == 0) { 
      if (node.getLeft() == null) { 
       size--; 
       return node.getRight(); 
      } 
      if (node.getRight() == null) { 
       size--; 
       return node.getLeft(); 
      } 

      // first, find smallest right 
      BSTNode<T> smallestRight = node.getRight(); 
      while (smallestRight.getLeft() != null) 
       smallestRight = smallestRight.getLeft(); 
       node.setValue(smallestRight.getValue()); 
       node.setRight(remove(smallestRight.getValue(), node.getRight())); 

      return node; 

     } else if (cmp > 0) { 
      node.setRight(remove(element, node.getRight())); 
      return node; 
     } else { 
      node.setLeft(remove(element, node.getLeft())); 
      return node; 
     } 
    } 
} 

誰かが私にこの方法の概要を教えてもらえますか？

Answer 1

サブツリーから要素を削除できれば、このサブツリー以外は変更する必要はありません。したがって、現在のノードが検索された値と等しくない場合は、要素が存在する必要がある場合は、削除する1つのサブツリーを選択するだけです（ある場合）。

では、次のツリーを持っていると6を削除する想像：

 4 
    2  6 
1 3 5 7 

あなたは6が4よりも大きくなるように、それは右のサブツリーになければならない、ということを知っています。だからあなたはそこに行って、サブツリーがツリー全体であるかのように進んで、残りのツリーは変更されません。このメソッドは、サブツリーの新しいルートを返します。このルートは、親の新しい左または右の子として設定する必要があります。

次に、等価のケースの再帰があります。現在のノードの値を設定します（これは、削除したいノードです）。ツリー全体で次の大きなノードとして検出されたノードに設定します。あなたはすでにこれが休暇（whileループ！）であることを知っているので、ツリーをそれ以上変更することなくそれを削除することができます（休暇は再帰がもう再入力されないことを保証します）。