Как удалить узел с 2 дочерними узлами в бинарном дереве поиска?

Question

Как удалить узел с 2 дочерними узлами в двоичном дереве?

Есть ли какой-нибудь метод для его удаления?Я гуглил это.Но не получил ясного представления об этом.Кто-нибудь объяснит это с помощью схематического представления?

Как удалить узел '5' из этого изображения и каков может быть результат?

Answer 1

Вы заменяете указанный узел самым левым дочерним узлом с правой стороны или самым правым дочерним узлом с левой стороны. Затем вы удаляете ребенка снизу, которым он был заменен.

Удаление пяти может привести либо к дереву с корнем 3, либо к корню 18, в зависимости от того, в каком направлении вы идете.

Похоже, вы получили это изображение с этого сайта: http://www.algolist.net/Data_structures/Binary_search_tree/Removal

Показывает алгоритм, который вы хотите с изображениями тоже.

Answer 2

Для удаления узла возможны три сценария.

1. Узел является листовым узлом: это простой случай, выясните, является ли этот узел левым или правым узлом родительского узла, и установите нулевое значение в качестве дочернего для родителя для этой стороны.
2. У узла есть один дочерний узел: установите прямую связь между родительским узлом и дочерним узлом этого узла.
3. У узла двое детей: это немного сложно ... шаги, которые нужно сделать, это.
   1. Сначала найдите преемника (или предшественника) этого узла.
   2. Удалить преемника (или предшественника) из дерева.
   3. Заменить удаляемый узел преемником (или предшественником)

Прежде чем знать концепцию удаления, мы должны понять концепцию преемника и предшественников

Преемник: в двоичном дереве наследником узла является наименьший узел дерева, который строго больше этого узла.

Есть два возможных случая с узлом

• У узла есть правые дочерние элементы: в этом случае самый левый дочерний элемент правого поддерева будет преемником.

• Узел не имеет дочерних элементов: перейдите к родительскому узлу и найдите узел, для которого этот узел является частью левого поддерева.

  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;
  }
  

Теперь логика удаления

     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);
        }
    }

    }

Решение взято из http://coder2design.com/binary-tree/

Также они объяснили ход прохождения и вставки с полным исходным кодом.

Answer 3

Простое и легкое решение:

            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 4

Статья в Википедии дает хорошее описание BST:

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

Когда вы удаляете узел с 2 дочерними элементами, в вашем случае 5, вы можете заменить удаленный узел узлом минимального значения из правого поддерева или узлом максимального значения из левого поддерева.

Answer 5

Найти преемника преемника удаляемого узла. Затем скопируйте содержимое преемника inorder узла и удалите преемник inorder. (Вы также можете использовать прекурсор inorder вместо преемника inorder)

Answer 6

Алгоритм:

->Find the node which need to delete (assume data is given)
->Find the deepest node of tree
->Replace deepest node's data with the node to be deleted
->Delete the deepest node

Реализация Java:

 public static void deleteTheNode(BTNode root, int data) {
    BTNode nodeToDelete = findTheNode(root, data);

    if (nodeToDelete == null) {
        System.out.println("Node Does not exists in Binary Tree");
        return;
    }
    BTNode deepestNode = findDepestNodeOfBinaryTree(root);
    nodeToDelete.setData(deepestNode.getData());
    _deleteTheNode(root, deepestNode);

}

private static void _deleteTheNode(BTNode root, BTNode node) {
    Queue<BTNode> q = new LinkedList<>();
    q.offer(root);

    while (!q.isEmpty()) {
        BTNode temp = q.poll();
        if (temp.getLeft() == node) {
            temp.setLeft(null);
            node = null;
            break;
        } else if (temp.getRight() == node) {
            temp.setRight(null);
            node = null;
            break;
        }
        if (temp.getLeft() != null) {
            q.offer(temp.getLeft());
        }
        if (temp.getRight() != null) {
            q.offer(temp.getRight());
        }
    }
}
//Find the deepest nodeof the binary tree
public static BTNode findDepestNodeOfBinaryTree(BTNode root) {
    int depth = 0;
    BTNode deepetNode = root;
    Stack<BTNode> nodes = new Stack<>();
    Stack<BTNode> path = new Stack<>();

    if (root == null) {
        return null;
    }
    nodes.push(root);
    while (!nodes.empty()) {
        BTNode node = nodes.peek();
        if (!path.empty() && node == path.peek()) {
            if (path.size() > depth) {
                depth = path.size() - 1;
                deepetNode = node;
            }
            path.pop();
            nodes.pop();
        } else {
            path.push(node);
            if (node.getRight() != null) {
                nodes.push(node.getRight());
            }
            if (node.getLeft() != null) {
                nodes.push(node.getLeft());
            }
        }
    }

    return deepetNode;
}

Answer 7

Вы не можете использовать самый левый узел правого поддерева. Допустим, у вас есть дерево, а самый левый узел правого поддерева - 15, но родитель 15 также 15, поэтому замена удаляемого узла на самый левый узел в правом поддереве может дать вам равный узел значение в правом поддереве. 15 станет новым корнем этого поддерева в моем примере, а затем будет еще 15 справа от корня.

Answer 8

Простое удаление узла, у которого есть 2 дочерних элемента, состоит в том, чтобы связать дочерний узел родителя удаленного узла с его преемником.