完全在二进制搜索树中实现延迟删除时，会有什么变化？ [英] What changes when implementing lazy deletion into a binary search tree exactly?
问题描述
好吧，所以我已经研究了好几天了，每次我想把它记下来的时候，我就开始编写代码，但到现在我根本不知道该怎么做。
Okay so I've been looking into this for days and everytime I think I've gotten it down I start writing code and I get to a point where I just can't figure out what exactly to do.
树不是递归的，因此我可以真正地遵循所有内容，直到我开始尝试对其进行修改，以便它使用延迟删除而不是实际删除。 （现在它使删除的节点无效）
The tree isn't recursive, so I can follow everything really until I start trying to modify it so it uses lazy deletion instead of real deletion. (Right now it nulls out the node it deletes)
我设法弄清的内容：
- 我在节点类中添加了一个标记，以将其设置为已删除
- 我实现了一种有效的搜索方法，即使我的节点被删除，它似乎也可以注册是否（懒惰地）
- 我知道树类的其余部分应该将标记为已删除的节点视为不存在。
我不知道的事情：
- 我看过很多资源有人说您需要做的就是将
节点的Deleted标志设置为true。这是否意味着我不必为
设置了标记后的链接而担心？ - 这样做是很肤浅的适当方法吗？就像那样，即使方法确实找到了东西，也不要让方法报告即使将标志设置为删除也找到了东西？
- 我应该在哪种方法中进行更改使用惰性删除？只有delete（）方法吗？
- 如果仅更改delete方法，其他方法如何处理呢？
- 进行搜索方法看起来还好吗？
- 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?
- 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?
- In what method(s) should I change to use lazy deletion? Only the delete() method?
- If I only change the delete method, how is this picked up by the other methods?
- Does the search method look okay?
其余的代码在这里，您可以看到我在使用什么。我真的很沮丧，因为我诚实地了解到如何完全比这种愚蠢的延迟删除实现更好地删除节点。这就是他们在书中教的！大声笑
Here's the rest of the code so you can see what I'm using. I'm really frustrated because I honestly understand how to delete nodes completely way better then this stupid lazy deletion implementation. It's what they teach in the book! lol
请帮助...：（
所以这是我的搜索方法：
So here's my search method:
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!";
}
树Class
树代码（真正的删除方法在结尾处被注释掉，因此我可以将其替换为惰性删除）：
Tree Class
Tree Code (The real deletion method is commented out at the end so I could replace it with the lazy deletion):
package mybinarytreeexample;
package mybinarytreeexample;
公共类MyBinaryTree> {
public class 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;
推荐答案
什么是变化，您的树只在实际使用的空间，并且永远不会缩小。如果您选择列表作为实现树的数据结构，而不是通常的构造 Node E {V value; E对； E;左} 。我会稍后再讨论。
What changes is that your tree only grows in term of real space used, and never shrinks. This can be very useful if you choose a list as a data-structure to implement your tree, rather than the usual construct Node E {V value; E right; E; left}. I will come back on this later.
我看过很多资源，有人说，您需要做的只是设置
将节点的已删除标志设置为true。这是否意味着我不必为
设置了标记后的链接而担心？
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）仍然必须工作
Yes, if by linking you mean node.left, node.right. Delete simply mark as deleted and that's it. It change nothing else, and it should not, because x.CompareTo(y) must be still working even if x or y are marked as deleted
这样做是否很肤浅？就像在其中一样，即使方法确实找到了某些东西，只是
也不要让该方法报告是否发现某些东西，如果该标志设置为
了吗？
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?
根据此方法的定义，某物表示没有删除标志的节点。对于树的用户，带有已删除标志的所有内容都是无。
Well by definition of this method "something" means a node without the deleted flag. Anything with the deleted flag is "nothing" for the user of the tree.
我应该更改哪种方法以使用惰性删除？只有delete（）
方法？
what method(s) should I change to use lazy deletion? Only the delete() method?
当然不是。您已经自己更改了搜索方法。让我们以 isEmpty（）为例。您应该保留一个已删除节点和总节点之一的计数器。如果它们相等，则树为空。否则树不是。
Of course not. You already changed the search method yourself. Let's take the isEmpty(). You should keep a counter of deleted nodes and one of total nodes. If they are equal the tree is empty. Otherwise the tree is not.
您的算法中有一个小错误。当您插入并发现自己位于已删除的节点上时，只需取消标记该节点即可。您还必须设置节点的值。毕竟 compareTo 不能确保所有字段都严格相等，只是对象是相等的。
There is a small bug in your algorithm. When you insert and find out that you land on a deleted node, you just unmark that node. You must also set the value of the node. After all compareTo doesnt insure all fields are strictly equal, just that the objects are equivalent.
if(child.isDeleted){
child.isDeleted = false;
child.e = e; <---- missing
return true;
}
可能还有其他人。
侧注：
如前所述，使用该方法的一个实例是一棵由列表支持的树（比如说数组列表）。通过这种方法，位置i的元素的子元素位于位置 2 * i + 1 和 2 * i + 2 。通常，当删除带有子节点的节点p时，会将其替换为右子树的最左节点q（或左子树中的最右节点）。在这里，您可以仅将p标记为已删除，然后将已删除节点的值交换到最左边。 您的数组在内存中保持不变
Side Note:
As said before one instance where this method is useful is a tree backed by an list (let's say array list). With this method the children of element at position i are at position 2*i+1 and 2*i+2. Usually when you delete a node p with children, you replace that node with the leftmost node q of the right subtree (or rightmost node in the left subtree). Here you can just mark p as deleted and swap the value of the deleted node and leftmost. Your array stays intact in memory
这篇关于完全在二进制搜索树中实现延迟删除时，会有什么变化？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
