java árvore de busca binária

Question

Eu tenho uma pergunta sobre como eu iria remover uma criança de um nó (root)? Desde que eu não posso chamar de remoção, se eu fizer o nulo criança, será que os filhos de que a criança mover-se? Como, se eu só inicializar-lo como nulo ?? Ou será que eu apontar para o filho da criança?

Answer 1

Em um tradicional árvore de busca binária, a remoção de um nó pode ter consequências diferentes dependendo de quantas crianças o nó tem:

• Um nó sem filhos pode simplesmente ser removida
• Um nó com uma criança pode ser removido, e o nó será substituído por seu filho único. Isto aplica-se independentemente da criança é uma criança para a esquerda ou direita.
• Um nó com dois filhos tem uma regra um pouco mais complicado: você deve encontrar o sucessor na ordem ou predecessor na ordem do nó a ser removido, substitua o valor do nó atual com o seu sucessor de ou o valor do predecessor, em seguida, elimine o sucessor ou predecessor (de acordo com estas regras).

Answer 2

É este o dever de casa? errado nada com isso ... nós apenas gosto de ajudar as pessoas a aprender em vez de dizer-lhes as respostas.

Se você apenas definir o nó filho para nula você vai perder qualquer informação sobre as crianças da criança.

Answer 3

A classe de árvore padrão saberá seus filhos, geralmente preso em uma matriz ou coleção - no caso de uma árvore binária, você só tem dois filhos diretos, assim que uma matriz de tamanho fixo vai funcionar. Por causa disso, eles costumam implementar algum tipo de método "removeMe" que as chamadas criança para obter removido dessa lista de crianças.

Como mencionado acima, isso fica complicado se a criança estiver a remover tem filhos.

Answer 4

A resposta de Tim parece melhor. Mas sim, você vai querer fazer uma de três coisas dependendo do que tipo de criança é a sua remoção. Se você fizer um nulo criança, os filhos de que não irá mover-se, porque você perdeu referência a eles. Em vez disso, você vai querer determinar se as crianças para a esquerda ou direito da criança a sua remoção deve ser definido para o ponteiro que aponta para a criança a sua remoção. Depois de definir o anterior ponteiro nós (esquerda ou direita) para a criança (esquerda ou direita) do nó de sua remoção, você não terá uma referência mais para esse nó, por isso não há necessidade de defini-lo como nulo (você pode' acesso t-lo mais. a menos que você escreveu algum tipo de BST duplamente vinculada, caso em que isso não é o BST clássico)

Answer 5

Este código deve ajudá-lo

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

Você pode fazer algo como isto (código pseudo):

Dada a raiz da árvore "root" eo nó de apagar ou alguns dados "x" faça o seguinte

 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;

código:

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;

}