자바 이진 검색 트리

Question

노드 (루트)에서 자식을 어떻게 제거하겠습니까? 내가 전화를 걸 수 없기 때문에, 아이를 무효로 만들면 그 아이의 아이들이 위로 올라갈 것입니까? 마찬가지로, 난 그냥 null로 초기화할까요 ?? 아니면 내가 그 아이의 아이를 가리키고 있습니까?

기존의 이진 검색 트리에서

Answer 1

, 노드의 제거는 얼마나 많은 어린이에 따라 다른 결과를 가져올 수있는 노드가 있습니다 자녀가없는

• 노드는 단순히 하나
• 노드를 제거 할 수 있습니다 하위 노드는 제거 될 수 있으며 노드는 유일한 하위 노드로 교체됩니다. 이는 자녀가 왼쪽 또는 오른쪽 자식인지 여부에 관계없이 적용됩니다.
• 약간 더 복잡한 규칙이 두 아이를 가진 노드 : 당신이 제거 할 노드의 에서 주문 후계자 또는 에서 주문 전임자를 발견해야한다는 그 sucessor의 또는 이전의 값을 현재 노드의 값을 대체 후속 규칙 또는 선행 규칙을 삭제하십시오 (이 규칙에 따라).

Answer 2

이 숙제가 있습니까? 그 점에 아무 문제가 없습니다 ... 우리는 사람들이 대답을하기보다는 배우는 것을 돕기를 좋아합니다.

자식 노드를 null로 설정하면 하위 노드에 대한 정보가 손실됩니다.

Answer 3

표준 트리 클래스는 일반적으로 배열 또는 컬렉션에 고정 된 자식을 인식합니다. 이진 트리의 경우에는 직접 자식이 두 개인 경우 고정 크기 배열이 작동합니다. 그 때문에, 그들은 보통, 아이가 그 아이의리스트로부터 삭제되도록 (듯이) 호출하는 일종의 「removeMe」메소드를 구현합니다.

위에서 언급 한 것처럼, 제거하려는 자식에 하위 항목이 있으면이 작업이 복잡해집니다.

Answer 4

팀의 대답이 가장 좋습니다. 하지만 네가 어떤 종류의 아이가 제거 되는가에 따라 세 가지 중 하나를하고 싶을 것입니다. 만약 당신이 아이를 null로 만들면, 그것들에 대한 참조를 잃어 버렸기 때문에 그것의 자식들은 움직이지 않을 것입니다. 대신 제거하는 자식의 왼쪽 또는 오른쪽 자식이 제거중인 자식을 가리키는 포인터로 설정되어야하는지 확인해야합니다. 이전 노드 포인터 (왼쪽 또는 오른쪽)를 자식 노드 (왼쪽 또는 오른쪽)로 설정하면 제거 할 노드는 더 이상 참조가 없으므로 null로 설정할 필요가 없습니다. 당신이 고전 BST 아니라 어떤 경우에는 이중 연결 BST의 일종) 작성하지 않으면 t 접근을 더 이상은.

Answer 5

이 코드는

public Node<T> getParentOf(Node<T> child){ 
    findParentOf(this.root, child); 
    return temp; 
} 

private void findParentOf(Node<T> ROOT, Node<T> child){ 
    if(ROOT.hasLeft()){ 
     findParentOf(ROOT.left, child); 
    } 

    if(ROOT.left == child || root.right == child){ 
     temp = ROOT; 
    } 

    if(ROOT.hasRight()){ 
     findParentOf(ROOT.right, child); 
    } 
} 


private void replaceNode(Node<T> original, Node<T> newNode){ 
    Node<T> tempParent = getParentOf(original); 
    if(original == tempParent.left){ 
     tempParent.left = newNode; 
    }else if(original == tempParent.right){ 
     tempParent.right = newNode; 
    } 
} 

private void traverseChildrenAndAdd(Node<T> newParent, Node<T> oldParent){ 
    newParent.insert(oldParent.data); 
    if(oldParent.hasLeft()){ 
     traverseChildrenAndAdd(newParent,oldParent.left); 
    } 



    if(oldParent.hasRight()){ 
     traverseChildrenAndAdd(newParent,oldParent.right); 
    } 
} 
private void deleteNode(Node<T> ROOT, Node<T> d){ 
    if(d.data.compareTo(ROOT.data) < 0){ 
     deleteNode(ROOT.left, d); 
    }else if(d.data.compareTo(ROOT.data) > 0){ 
     deleteNode(ROOT.right, d); 
    }else if(d == this.root){ 
     if(this.root.hasLeft()){ 
      traverseChildrenAndAdd(root.left, root.right); 
      root = root.left; 
     }else if(root.hasRight()){ 
      root = root.right; 
     }else{ 
      root = null; 
     } 
    }else{ 
     if(ROOT.hasLeft()&&ROOT.hasRight()){ 
      Node<T> successor = getMinNode(ROOT); 
      replaceNode(successor, successor.right); 
     }else if(ROOT.hasLeft() || ROOT.hasRight()){ 
      if(ROOT.hasLeft()){ 
       replaceNode(ROOT, ROOT.left); 
      }else{ 
       replaceNode(ROOT, ROOT.right); 
      } 
     }else{ 
      replaceNode(ROOT, null); 
     } 
    } 
} 

public void remove(T data){ 
    deleteNode(this.root, new Node<T>(data)); 
} 

Answer 6

당신은 (의사 코드 같은 것을 할 수 있습니다 도움이 될 것입니다) :

주어진 "루트"트리의 루트 및 삭제할 노드 또는 일부 데이터 "x"는 다음을 수행합니다.

if x < root 
     recurse to left child 
if x > root 
     recurse to right child 
else //node found 
     find the min item of the node right child //min item should be left most leaf node node 
     replace the value of the node you want to delete with min nodes value 
     now delete the min node 
return root; 

코드 :

delete(Node root, Object x){ 
    if(root == null){ 
     return null; 
    } 

    if(data < root.data){ 
     root = delete(root.left); 
    }else if(root.data < data){ 
     root = delete(root.right); 
    }else{ 
     if(root.left != null && root.right != null){ 
      Object tmp = findMin(root.right); 
      root.data = tmp; 
      root.right = delete(root.right, tmp); 
     }else{ 
      return (root.left != null) ? root.left : root.right;  
     } 
    } 
return root; 

}