java - 在二叉搜索树中实现延迟删除到底有什么变化？

Question

好吧，我已经研究了好几天了，每次我觉得我已经把它记下来了，我就开始写代码，但我到了一个地步，我就是想不出到底该怎么做。

这棵树不是递归的，所以我可以真正了解所有内容，直到我开始尝试修改它，以便它使用延迟删除而不是真正的删除。 (现在它清空了它删除的节点)

我已经弄明白了:

• 我向节点类添加了一个标志以将它们设置为已删除
• 我已经实现了一种有效的搜索方法，它甚至可以记录我的节点是否被删除(懒惰地)
• 我知道树类的其余部分应该将标记为已删除的节点视为不存在的节点。

我不知道的是:

1. 我看了很多资源，有些人说你需要做的就是设置节点的删除标志为真。这是否意味着我不必担心设置标志后的链接？
2. 做这件事的合适方法是非常肤浅的吗？比如，如果标志设置为删除，即使方法确实找到了某些东西，也不要让方法报告找到了某些东西？
3. 我应该在什么方法中更改为使用惰性删除？只有 delete() 方法？
4. 如果我只更改 delete 方法，其他方法如何选择它？
5. 搜索方法看起来还好吗？

这是其余代码，因此您可以看到我使用的是什么。我真的很沮丧，因为我真的理解如何比这个愚蠢的延迟删除实现更好地完全删除节点。书上是这么教的!哈哈

请帮忙...:(

---

搜索方法

所以这是我的搜索方法:

public String search(E data){
    Node<E> current = root;
    String result = "";

    while(current != null){
        if(data.compareTo(current.e) < 0){
            current = current.left;
        }
        else if (data.compareTo(current.e) > 0){
            current = current.right;
        }
        else{
            if (current.isDeleted == false){
                return result += "Found node with matching data that is not deleted!";
            }
            else{
                return result += "Found deleted data, not usable, continuing search\n";
            }
        }
    }

    return result += "Did not find non-deleted matching node!";
}

---

树类

树代码(真正的删除方法在最后被注释掉，所以我可以用惰性删除代替它):

打包 mybinarytreeexample;

公共(public)类 MyBinaryTree> {

private Node<E> root = null;

public class Node<E> {
    public boolean isDeleted = false;
    public E e = null;
    public Node<E> left = null;
    public Node<E> right = null;
}

public boolean insert(E e) {
    // if empty tree, insert a new node as the root node
    // and assign the elementy to it
    if (root == null) {
        root = new Node();
        root.e = e;
        return true;
    }

    // otherwise, binary search until a null child pointer 
    // is found
    Node<E> parent = null;
    Node<E> child = root;

    while (child != null) {
        if (e.compareTo(child.e) < 0) {
            parent = child;
            child = child.left;
        } else if (e.compareTo(child.e) > 0) {
            parent = child;
            child = child.right;
        } else {
            if(child.isDeleted){
                child.isDeleted = false;
                return true;
            }
            return false;
        }
    }

    // if e < parent.e create a new node, link it to 
    // the binary tree and assign the element to it
    if (e.compareTo(parent.e) < 0) {
        parent.left = new Node();
        parent.left.e = e;
    } else {
        parent.right = new Node();
        parent.right.e = e;
    }
    return true;
}

public void inorder() {
    System.out.print("inorder:   ");
    inorder(root);
    System.out.println();
}
private void inorder(Node<E> current) {
    if (current != null) {
        inorder(current.left);
        System.out.printf("%3s", current.e);
        inorder(current.right);
    }
}

public void preorder() {
    System.out.print("preorder:  ");
    preorder(root);
    System.out.println();
}
private void preorder(Node<E> current) {
    if (current != null) {
        System.out.printf("%3s", current.e);
        preorder(current.left);
        preorder(current.right);
    }
}

public void postorder() {
    System.out.print("postorder: ");
    postorder(root);
    System.out.println();
}
private void postorder(Node<E> current) {
    if (current != null) {
        postorder(current.left);
        postorder(current.right);
        System.out.printf("%3s", current.e);
    }
}

public String search(E data){
    Node<E> current = root;
    String result = "";

    while(current != null){
        if(data.compareTo(current.e) < 0){
            current = current.left;
        }
        else if (data.compareTo(current.e) > 0){
            current = current.right;
        }
        else{
            if (current.isDeleted == false){
                return result += "Found node with matching data that is not deleted!";
            }
            else{
                return result += "Found deleted data, not usable, continuing search\n";
            }
        }
    }

    return result += "Did not find non-deleted matching node!";
}

public boolean delete(E e) {


}


// an iterator allows elements to be modified, but can mess with
// the order if element not written with immutable key; it is better
// to use delete to remove and delete/insert to remove or replace a
// node
public java.util.Iterator<E> iterator() {
    return new PreorderIterator();
}

private class PreorderIterator implements java.util.Iterator<E> {

    private java.util.LinkedList<E> ll = new java.util.LinkedList();
    private java.util.Iterator<E> pit= null;

    // create a LinkedList object that uses a linked list of nodes that
    // contain references to the elements of the nodes of the binary tree 
    // in preorder
    public PreorderIterator() {
        buildListInPreorder(root);
        pit = ll.iterator();
    }

    private void buildListInPreorder(Node<E> current) {
        if (current != null) {
            ll.add(current.e);
            buildListInPreorder(current.left);
            buildListInPreorder(current.right);
        }
    }

    // check to see if their is another node in the LinkedList
    @Override
    public boolean hasNext() {
        return pit.hasNext();
    }

    // reference the next node in the LinkedList and return a 
    // reference to the element in the node of the binary tree
    @Override
    public E next() {
        return pit.next();
    }

    @Override
    public void remove() { 
        throw new UnsupportedOperationException("NO!");
    }
}
}


// binary search until found or not in list
//        boolean found = false;
//        Node<E> parent = null;
//        Node<E> child = root;
//        
//        while (child != null) {
//            if (e.compareTo(child.e) < 0) {
//                parent = child;
//                child = child.left;
//            } else if (e.compareTo(child.e) > 0) {
//                parent = child;
//                child = child.right;
//            } else {
//                found = true;
//                break;
//            }
//        }        
//        
//        
//        if (found) {
//            // if root only is the only node, set root to null
//            if (child == root && root.left == null && root.right == null)
//                root = null;
//            // if leaf, remove
//            else if (child.left == null && child.right == null) {
//                if (parent.left == child)
//                    parent.left = null;
//                else 
//                    parent.right = null;
//            } else
//                // if the found node is not a leaf
//                // and the found node only has a right child, 
//                // connect the parent of the found node (the one 
//                // to be deleted) to the right child of the 
//                // found node 
//                if (child.left == null) {
//                    if (parent.left == child)
//                        parent.left = child.right;
//                    else 
//                        parent.right = child.right;
//            } else {
//                // if the found node has a left child,
//                // the node in the left subtree with the largest element 
//                // (i. e. the right most node in the left subtree) 
//                // takes the place of the node to be deleted
//                Node<E> parentLargest = child;
//                Node<E> largest = child.left;
//                while (largest.right != null) {
//                    parentLargest = largest;
//                    largest = largest.right;
//                }
//                
//                // replace the lement in the found node with the element in
//                // the right most node of the left subtree
//                child.e = largest.e;
//                
//                // if the parent of the node of the largest element in the 
//                // left subtree is the found node, set the left pointer of the
//                // found node to point to left child of its left child
//                if (parentLargest == child)
//                    child.left = largest.left;
//                else 
//                    // otherwise, set the right child pointer of the parent of 
//                    // largest element in the left subtreeto point to the left
//                    // subtree of the node of the largest element in the left 
//                    // subtree
//                    parentLargest.right = largest.left;
//            }
//            
//        } // end if found
//        
//        return found;

Answer 1

改变的是你的树只会根据实际使用的空间增长，而不会缩小。如果您选择一个列表作为数据结构来实现您的树，而不是通常的结构 Node E {V value; E对； E;左。我稍后会回来讨论这个问题。

I've looked at MANY resources and some say all you need to do is set the node's deleted flag to true. Does this mean that I don't have to worry about the linking after their flag is set?

是的，如果链接是指 node.left、node.right。删除只需标记为已删除即可。它没有改变任何其他东西，它也不应该改变，因为即使 x 或 y 被标记为已删除，x.CompareTo(y) 也必须仍在工作

Is an appropriate way to do this very superficial? As in, just don't let the methods report that something is found if the flag is set to deleted even though the methods do find something?

好吧，根据此方法的定义，“某物”表示没有已删除标志的节点。对于树的用户而言，带有删除标志的任何内容都是“无”的。

what method(s) should I change to use lazy deletion? Only the delete() method?

当然不是。您已经自己更改了搜索方法。让我们以 isEmpty() 为例。您应该保留已删除节点的计数器和总节点之一。如果它们相等，则树为空。否则树不是。

您的算法中有一个小错误。当您插入并发现您落在已删除的节点上时，您只需取消标记该节点即可。您还必须设置节点的值。毕竟 compareTo 并不能确保所有字段都严格相等，只是对象是等价的。

 if(child.isDeleted){
      child.isDeleted = false;
      child.e = e; <---- missing
      return true;
 }

可能还有其他的。

旁注:
如前所述，此方法有用的一个实例是由列表(假设数组列表)支持的树。使用此方法，位置 i 的元素的子元素位于位置 2*i+1 和 2*i+2。通常当你删除一个有 child 的节点 p 时，你用右子树的最左边的节点 q 替换那个节点(或者左子树的最右边的节点)。在这里您可以将 p 标记为已删除并交换已删除节点和最左边的值。 您的数组在内存中保持完整