data structures - programar - ¿Cómo eliminar un nodo con 2 nodos secundarios en un árbol de búsqueda binario?

arboles binarios estructura de datos

Question

¿Cómo eliminar un nodo con 2 nodos hijos en un árbol binario?

¿Hay algún tipo de método para eliminarlo? Lo busqué en Google. Pero no tuvo una idea clara al respecto. ¿Alguien lo explica con representación diagramática?

¿Cómo eliminar el nodo ''5'' de esta imagen y cuál podría ser el resultado?

Answer 1

Artículo de Wikipedia da una buena descripción de BST:

http://en.wikipedia.org/wiki/Binary_search_tree

Cuando elimina un nodo con 2 hijos, 5 en su caso, puede reemplazar el nodo eliminado con el nodo de valor mínimo del subárbol derecho, o el nodo de valor máximo desde el subárbol izquierdo.

Answer 2

usted reemplaza dicho nodo con el niño más a la izquierda en su lado derecho, o el niño más a la derecha en su lado izquierdo. A continuación, elimine al niño del fondo con el que fue reemplazado.

Eliminar cinco podría dar como resultado un árbol con 3 como raíz o 18 como raíz, según la dirección que tome.

Parece que obtuviste esa imagen de este sitio: http://www.algolist.net/Data_structures/Binary_search_tree/Removal

Muestra el algoritmo que desea con las imágenes también.

Answer 3

Una eliminación simple de un nodo que tiene 2 hijos es volver a etiquetar el elemento primario del nodo eliminado con su sucesor.

Answer 4

No puede usar el nodo más a la izquierda del subárbol derecho. Digamos que tiene un árbol y el nodo más a la izquierda del subárbol derecho es 15, pero el padre de 15 también es 15, por lo que reemplazar el nodo que se eliminará con el nodo más a la izquierda del subárbol derecho puede darle un nodo de igual valor en el subárbol derecho. El 15 se convertiría en una nueva raíz de ese subárbol en mi ejemplo y luego habría otros 15 a la derecha de la raíz.

Answer 5

Una solución simple y fácil:

 Node* findMaxNode(Node* root)
{
if(root->right == NULL) return root;
findMaxNode(root->right);
}
Node* DeleteNodeInBST(Node* root,int data)
{
//base case when not found or found then recursion breaks
if(root == NULL) return root;
else if(root->data > data) root->left = DeleteNodeInBST(root->left, data);
else if(root->data < data) root->right = DeleteNodeInBST(root->right, data);
else
{
//when the node to be deleted is found
//Four possibilities
//case1: When the node to be deleted has no children
if(root->left == NULL && root->right == NULL)
{
delete root;
root = NULL;
}
//case2: When the node to be deleted has ONLY LEFT child
else if(root->right == NULL)
{
Node* temp = root;
root = root->left;
delete temp;
}
//case3: When the node to be deleted has ONLY RIGHT child
else if(root->left == NULL)
{
Node* temp = root;
root = root->right;
delete temp;
}
//case4: When the node to be deleted has TWO children
else
{
Node* maxNode = findMaxNode(root->left);//finding the maximum in LEFT sub-tree
root->data = maxNode->data; //Overwriting the root node with MAX-LEFT
root->left = DeleteNodeInBST(root->left, maxNode->data);//deleted the MAX-LEFT node
}
return root;
}
}

Answer 6

Para eliminar un nodo, existen tres escenarios posibles.

1. El nodo es un nodo hoja: este es un caso simple, determine si este nodo es el nodo izquierdo o derecho del elemento primario y establezca nulo como secundario para el elemento primario de ese lado.
2. El nodo tiene un hijo: establece un enlace directo entre el nodo padre y el nodo hijo de este nodo.
3. Nodo tiene dos hijos: esto es un poco complicado ... los pasos involucrados en esto son.
   1. Primero encuentre el sucesor (o predecesor) de este nodo.
   2. Eliminar el sucesor (o predecesor) del árbol.
   3. Reemplace el nodo que se eliminará con el sucesor (o predecesor)

Antes de conocer el concepto de eliminación, debemos entender el concepto de sucesor y predecesores

Sucesor: en un árbol binario, el sucesor de un nodo es el nodo más pequeño del árbol que es estrictamente mayor que este nodo.

Hay dos casos posibles con un nodo

• Un nodo tiene hijos correctos: en este caso, el hijo más a la izquierda del subárbol correcto será el sucesor.

• Un nodo no tiene hijos: vaya al nodo padre y encuentre un nodo para el cual este nodo sea parte del subárbol izquierdo.

  public Node sucessor(Node node) {
  Node sucessor = null;
  if (node.getRightNode() != null) {
  Node newNode = node.getRightNode();
  while (newNode != null) {
  sucessor = newNode;
  newNode = newNode.getLeftNode();
  }
  } else {
  sucessor = findRightParent(node);
  }
  return sucessor;
  }
  private Node findRightParent(Node node) {
  Node newNode = null;
  if (node.getParentNode() != null) {
  if (node.getParentNode().getLeftNode() == node) {
  newNode = node.getParentNode();
  } else {
  newNode = findRightParent(node.getParentNode());
  }
  }
  return newNode;
  }

Ahora la lógica de eliminación

 public void deleteNode(Node node) {
// Node is a leaf node //
if( node.getLeftNode() == null && node.getRightNode() == null){
if(isRightNode(node.getParentNode(), node)){
node.getParentNode().setRightNode(null);
}else{
node.getParentNode().setLeftNode(null);
}
// Only left child is there//
}else if( node.getLeftNode() != null && node.getRightNode() == null){
if(isRightNode(node.getParentNode(), node)){
node.getParentNode().setRightNode(node.getLeftNode());
}else{
node.getParentNode().setLeftNode(node.getLeftNode());
}
// Only Right child is there //
}else if( node.getLeftNode() == null && node.getRightNode() != null){
if( isRightNode(node.getParentNode(), node)){
node.getParentNode().setRightNode(node.getRightNode());
}else{
node.getParentNode().setLeftNode(node.getRightNode());
}
// Both Left and Right children are their//
}else{
Node psNode = predessor(node);
deleteNode(psNode);
psNode.setParentNode(node.getParentNode());
psNode.setLeftNode(node.getLeftNode());
psNode.setRightNode(node.getRightNode());
if( isRightNode(node.getParentNode(), node)){
node.getParentNode().setRightNode(psNode);
}else{
node.getParentNode().setLeftNode(psNode);
}
}
}

La solución está tomada de http://coder2design.com/binary-tree/

También han explicado el flujo de recorrido e inserción con el código fuente completo.