java árbol de búsqueda binaria

Question

Tengo una pregunta acerca de cómo iba a retirar a un niño de un nodo (raíz)? Ya que no puedo llamar a eliminar, si hago el niño nula, serán los hijos de ese niño moverse hacia arriba? Al igual que, ¿me acaba de inicializar como nulo ?? O iba a apuntar a los niños del niño?

Answer 1

En un árbol binario de búsqueda tradicional, la eliminación de un nodo puede tener consecuencias diferentes en función del número de hijos del nodo tiene:

• Un nodo sin hijos simplemente se puede quitar
• Un nodo con un niño se puede quitar, y el nodo será reemplazado por su único hijo. Esto se aplica independientemente de si el niño es un niño izquierda o la derecha.
• Un nodo con dos hijos tiene una regla un poco más complicado: hay que encontrar el sucesor en orden o en orden predecesor del nodo a ser retirado, reemplace el valor del nodo actual con su sucesor o del valor de su predecesor, a continuación, elimine el sucesor o predecesor (de acuerdo con estas reglas).

Answer 2

¿Es esta tarea? No hay nada malo con eso ... simplemente nos gusta ayudar a la gente a aprender más que les diga las respuestas.

Si acaba de configurar el nodo hijo en nulo si no se pierden ninguna información acerca de los childs niños.

Answer 3

Un árbol de la clase estándar sabrá sus hijos, por lo general atrapados en una matriz o colección - en el caso de un árbol binario, sólo tienes dos hijos directos, por lo que una matriz de tamaño fijo funcionará. Debido a que, por lo general implementar algún tipo de método "removeMe" que el niño llama para ser retirado de la lista de los niños.

Como se mencionó anteriormente, esto se complica si el niño va a extraer tiene hijos.

Answer 4

La respuesta de Tim parece mejor. Pero sí tendrá que hacer una de tres cosas dependiendo de qué tipo de niño es su eliminación. Si comete un niño nulo, los hijos de los que no se moverán hasta porque ha perdido la referencia a ellos. En su lugar, tendrá que determinar si los hijos izquierdo o derecho del niño a su eliminación se deben establecer en el puntero que apunta a la eliminación de su hijo. Después de establecer la anterior nodos puntero (izquierda o derecha) para el niño (izquierda o derecha) del nodo de su eliminación, usted no tendrá una referencia más a ese nodo, por lo que no hay necesidad de ponerlo en nulo (se puede' t acceso más. a menos que usted escribió una especie de BST doblemente enlazada, en cuyo caso ese no es el clásico BST)

Answer 5

Este código debe ayudarle a

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

Puede hacer algo como esto (pseudocódigo):

Dado un la raíz del árbol "raíz" y el nodo a eliminar o algunos datos "x" hacer lo siguiente

 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;

}