Java 이진 검색 트리

Question

노드 (루트)에서 아이를 어떻게 제거 할 것인가에 대한 질문이 있습니까? 내가 제거 할 수 없기 때문에, 아이를 무효로 만들면 그 아이의 아이들이 올라갈까요? 마찬가지로, 나는 단지 그것을 null로 초기화 할 것입니까 ?? 아니면 아이의 자녀를 가리킬 것인가?

Answer 1

기존의 이진 검색 트리에서 노드를 제거하면 노드에 몇 명의 어린이 수에 따라 다른 결과를 초래할 수 있습니다.

• 어린이가없는 노드를 간단히 제거 할 수 있습니다
• 한 아이가있는 노드를 제거 할 수 있으며 노드는 유일한 자식으로 대체됩니다. 이것은 자녀가 왼쪽 또는 오른쪽 자녀인지에 관계없이 적용됩니다.
• 두 자녀가있는 노드는 약간 더 복잡한 규칙을 가지고 있습니다. 순서의 후임자 또는 사역 전임자 제거 할 노드의 경우 현재 노드의 값을 성공적인 노드 또는 전임자의 값으로 바꾸고 후임자 또는 선행 (이 규칙에 따라)을 삭제하십시오.

Answer 2

이 숙제입니까? 그것에 아무런 문제가 없습니다 ... 우리는 사람들이 그들에게 답을 말하지 않고 배우도록 돕는 것을 좋아합니다.

자식 노드를 NULL로 설정하면 Childs Children에 대한 정보를 잃게됩니다.

Answer 3

표준 트리 클래스는 어린이를 알게 될 것입니다. 일반적으로 배열이나 컬렉션에 갇힌 어린이를 알게됩니다. 이진 트리의 경우 직접 어린이가 두 명 밖에 없으므로 고정 크기의 배열이 작동합니다. 그로 인해 그들은 일반적으로 어린이가 그 어린이 목록에서 제거되도록 요청하는 일종의 "제거"방법을 구현합니다.

위에서 언급했듯이, 당신이 제거하는 아이가 자녀가있는 경우 이것은 복잡해집니다.

Answer 4

팀의 대답이 가장 좋을 것 같습니다. 그러나 그렇습니다. 당신은 당신이 제거하는 아이의 종류에 따라 세 가지 일 중 하나를하고 싶을 것입니다. 당신이 아이를 null로 만들면, 당신은 그들에 대한 언급을 잃어 버렸기 때문에 그 아이들이 올라 가지 않을 것입니다. 대신, 제거하는 자녀의 왼쪽 또는 오른쪽 자녀가 제거하는 어린이를 가리키는 포인터로 설정되어야하는지 확인하고 싶을 것입니다. 제거한 노드의 자식 (왼쪽 또는 오른쪽)에 이전의 '노드 포인터 (왼쪽 또는 오른쪽)를 설정 한 후에는 해당 노드에 대한 참조가 없으므로 NULL로 설정할 필요가 없습니다 (할 수 있습니다'). t 더 이상 액세스하십시오. 당신이 일종의 이중 연결 BST를 쓰지 않았다면,이 경우 클래식 BST가 아닙니다)

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;

}