下面的代码是我已有的，我需要添加一个懒惰的删除方法。基本上，惰性删除方法将节点标记为删除，而不是删除它。这样，删除的位置在插入时被视为空，在搜索期间被视为已占用。我假设节点中的布尔值将是最简单的方法，但我正在努力弄清楚如何配置方法以考虑节点是否已“lazyDeleted”。我已经发布了下面的代码。提前致谢。
/**
* Binary Search Trees are binary trees with search functionality on the order of lg(N)
* (lg() is the logarithm of base 2, and N is the number of elements processed)
*
* Binary Search Trees contain a root node that has exactly two child nodes of the same type
* These nodes are initially set to null but can be changed later
* The Binary Tree has a root node, with everything that is larger than the root contained in
* the right subtree, and everything smaller than the root contained in the left subtree
*
* @author Mark Allen Weiss (originally)
*
* @param <E> any element that is a subclass of Comparable
*/
public class BinarySearchTree<E extends Comparable<? super E>> {
/*-----------------------*
* Variable Declarations *
*-----------------------*/
private BinaryNode<E> root;
/**
* Constructs a tree with an empty root
*/
public BinarySearchTree() {
root = null;
}
/**
* Releases the root of the tree, rendering it empty
*
* @return void
*/
public void makeEmpty() {
root = null;
}
/**
* Checks to see if the tree is empty
*
* @return <tt>true</tt> if the tree is empty; <tt>false</tt> otherwise
*/
public boolean isEmpty() {
return root == null;
}
/**
* Searches the tree to see if it contains the specified element
*
* @param element the element to be found
* @return <tt>true</tt> if the element is found; <tt>false</tt> otherwise
*/
public boolean contains(E element) {
return contains(element, root);
}
/**
* Finds the smallest element in the tree
*
* @return the smallest element in the tree
*/
public E findMin() {
if(isEmpty()) {
// throw new UnderflowException();
return null;
/* The author throws a new UnderflowException, but the class is not included in the
* standard Java API, so I return a null instead */
} else {
return findMin(root).element;
}
}
/**
* Finds the largest element in the tree
*
* @return the largest element in the tree
*/
public E findMax() {
if(isEmpty()) {
// throw new UnderflowException();
return null;
/* The author throws a new UnderflowException, but the class is not included in the
* standard Java API, so I return a null instead */
} else {
return findMax(root).element;
}
}
/**
* Inserts the given element into the tree
*
* @param element
* @return void
*/
public void insert(E element) {
root = insert(element, root);
}
/**
* Removes the specified element from the tree
*
* @param element the element to be removed
* @return void
*/
public void remove(E element) {
root = remove(element, root);
}
/**
* Prints the tree contents in sorted order
*
* @return void
*/
public void printTree() {
if(isEmpty()) {
System.out.println("Empty Tree");
} else {
printTree(root);
}
}
/**
* Internal method to compute height of a subtree.
*
* @param t the node that roots the subtree
*/
private int height(BinaryNode<E> t) {
if( t == null ) {
return -1;
} else {
return 1 + Math.max( height( t.left ), height( t.right ) );
}
}
/**
* Internal method to find an item in a subtree
*
* @param element the item to search for
* @param t the node that roots the subtree
* @return <tt>true</tt> if the item is found; <tt>false</tt> otherwise
*/
private boolean contains(E element, BinaryNode<E> t) {
if(t == null) {
return false;
}
int compareResult = element.compareTo(t.element);
if(compareResult < 0) {
return contains(element, t.left);
} else if(compareResult > 0) {
return contains(element, t.right);
} else {
return true; // Match
}
}
/**
* Internal method to find the smallest item in a subtree
*
* @param t the node that roots the subtree
* @return the node containing the smallest item
*/
private BinaryNode<E> findMin(BinaryNode<E> t) {
if(t == null) {
return null;
} else if(t.left == null) {
return t;
} else {
return findMin(t.left);
}
}
/**
* Internal method to find the largest item in a subtree
*
* @param t the node that roots the subtree
* @return the node containing the largest item
*/
private BinaryNode<E> findMax(BinaryNode<E> t) {
if(t == null) {
return null;
} else if(t.right == null) {
return t;
} else {
return findMax(t.right);
}
}
/**
* Internal method to insert into a subtree
* Duplicates are not allowed and ignored
*
* @param element the item to insert
* @param t the node that roots the subtree
* @return the new root of the subtree
*/
private BinaryNode<E> insert(E element, BinaryNode<E> t) {
if(t == null) {
return new BinaryNode<E>(element);
}
int compareResult = element.compareTo(t.element);
if(compareResult < 0) {
t.left = insert(element, t.left);
} else if(compareResult > 0) {
t.right = insert(element, t.right);
} else {
; // Duplicate; do nothing
}
return t;
}
/**
* Internal method to remove an element from a subtree
*
* @param element the element to be removed
* @param t the node that roots the subtree
* @return the new root of the subtree
*/
private BinaryNode<E> remove(E element, BinaryNode<E> t) {
if(t == null) {
return t; // Item not found; do nothing
}
int compareResult = element.compareTo(t.element);
if(compareResult < 0) {
t.left = remove(element, t.left);
} else if(compareResult > 0) {
t.right = remove(element, t.right);
} else if(t.left != null && t.right != null) { // Two children
t.element = findMin(t.right).element;
t.right = remove(t.element, t.right);
} else {
t = (t.left != null) ? t.left : t.right;
}
return t;
}
/**
* Internal method to print a subtree in sorted order
*
* @param t the node that roots the subtree
* @return void
*/
private void printTree(BinaryNode<E> t) {
if(t != null){
printTree(t.left);
System.out.println(t.element);
printTree(t.right);
}
}
/**
* Internal class that defines a tree node with exactly two children
*
* @author Mark Allen Weiss
*
* @param <E> any element that is a subclass of Comparable
*/
private static class BinaryNode<E> {
/*-----------------------*
* Variable Declarations *
*-----------------------*/
E element; // The data in the node
BinaryNode<E> left; // The left child node
BinaryNode<E> right; // The right child node
/**
* Constructs a new BinaryNode of type E that contains the given element
*
* @param theElement the data to be stored in the node
*/
BinaryNode(E theElement) {
this(theElement, null, null);
}
/**
* Constructs a new BinaryNode of type E that contains the given element and has the
* given nodes as its left and right children respectively
*
* @param theElement the data to be stored in the node
* @param leftChild the left child of the node
* (either a leaf node or a subtree)
* @param rightChild the right child of the node
* (either a leaf node or a subtree)
*/
BinaryNode(E theElement, BinaryNode<E> leftChild, BinaryNode<E> rightChild) {
element = theElement;
left = leftChild;
right = rightChild;
}
}
}