我正在实现以下类型AVLTree<K extends Comparable<K>,V>的AVL树，基本上树的每个节点都是键值节点，目前我正在努力删除所有V值的方法。这是我的:
private void deleteAll(AVLTreeNode<K,V> root, V value){
if(root == null) return;
deleteAll(root.left, value);
deleteAll(root.right, value);
if(root.getValue().equals(value)){
delete(root.getKey());
}
}
超级简单的方法(可能没有优化O(nlog(n))，如果你有一个更好的优化解决方案，请随意编写)使用自下而上的递归。
delete法:
public void delete(K key){
super.setRoot(delete(super.getRoot(), key));
}
private AVLTreeNode<K,V> delete(AVLTreeNode<K,V> root, K key) {
if (root == null) {
return root;
} else if (root.getKey().compareTo(key) > 0) {
root.setLeft(delete(root.left, key));
} else if (root.getKey().compareTo(key) < 0) {
root.setRight(delete(root.right, key));
} else {
if (root.left == null || root.right == null) {
root = (root.left == null) ? root.right : root.left;
} else {
AVLTreeNode<K,V> mostLeftChild = AVLTreeUtils.minValueNode(root.right);
root.key = mostLeftChild.getKey();
root.value = mostLeftChild.getValue();
root.setRight(delete(root.right, root.key));
}
size--;
}
if (root != null) {
root = AVLTreeUtils.rebalance(root);
}
return root;
}
实际情况是，它正确地删除了大部分值，但有时会留下一些必须删除的值，这里有一个例子:
DELETING ALL VALUES: 2
BEFORE DELETION OF EVERY: 2
->2
->0
->1
->2
->1
->1
->1
->0
->2
->2
AFTER DELETION
->2
->0
->1
->2
->1
->1
->1
->0
Time used: 0 ms tree size: 8
-------------------------------------------
Does tree contain value: 2? true
编辑:
下面是类 的所有代码package structure.tree.balanced;
import structure.array.Array;
import structure.node.Node;
import structure.tree.Tree;
public class AVLTree<K extends Comparable<K>,V> extends Tree<AVLTree.AVLTreeNode<K, V>> {
private static final long serialVersionUID = 5046115177325966348L;
public boolean containsValue(V value) {
return containsValue(((AVLTreeNode<K,V>) super.getRoot()), value);
}
private boolean containsValue(AVLTreeNode<K,V> root, V value){
if(root == null) return false;
else {
if(root.getValue().equals(value)) return true;
else return containsValue(root.getLeft(), value) || containsValue(root.getRight(), value);
}
}
public boolean containsKey(K key){
return containsKey(((AVLTreeNode<K,V>) super.getRoot()), key);
}
private boolean containsKey(AVLTreeNode<K,V> root, K key){
if(root == null) return false;
else {
if(root.getKey().compareTo(key) < 0) return containsKey(root.getRight(), key);
else if(root.getKey().compareTo(key) > 0) return containsKey(root.getLeft(), key);
else return true;
}
}
public void delete(K key){
super.setRoot(delete(super.getRoot(), key));
}
private AVLTreeNode<K,V> delete(AVLTreeNode<K,V> root, K key) {
if (root == null) {
return root;
} else if (root.getKey().compareTo(key) > 0) {
root.setLeft(delete(root.left, key));
} else if (root.getKey().compareTo(key) < 0) {
root.setRight(delete(root.right, key));
} else {
if (root.left == null || root.right == null) {
root = (root.left == null) ? root.right : root.left;
} else {
AVLTreeNode<K,V> mostLeftChild = minValueNode(root.right);
root.key = mostLeftChild.getKey();
root.value = mostLeftChild.getValue();
root.setRight(delete(root.right, root.key));
}
if(size > 0) size--;
}
if (root != null) {
root = rebalance(root);
}
return root;
}
public void deleteAll(V value){
deleteAll(super.getRoot(), value);
}
private void deleteAll(AVLTreeNode<K,V> root, V value){
if(root == null) return;
deleteAll(root.left, value);
deleteAll(root.right, value);
if(root.getValue().equals(value)) delete(root.getKey());
}
public V get(K key){
return get(super.getRoot(), key);
}
private V get(AVLTreeNode<K, V> root, K key) {
if(root.getKey().compareTo(key) == 0) return root.getValue();
else if(root.getKey().compareTo(key) > 0) return get(root.getLeft(), key);
else return get(root.getRight(), key);
}
private int getBalance(AVLTreeNode<K,V> n) {
return (n == null) ? 0 : height(n.getRight()) - height(n.getLeft());
}
private int height(AVLTreeNode<K,V> n) {
return n == null ? -1 : n.getHeight();
}
public void insert(K key, V value) {
size++;
super.setRoot(insert(super.getRoot(), key, value));
}
private AVLTreeNode<K,V> insert(AVLTreeNode<K,V> root, K key, V value){
if (root == null) {
return new AVLTreeNode<K,V>(key, value);
} else if (root.getKey().compareTo(key) > 0) {
root.setLeft(insert(root.getLeft(), key, value));
} else if (root.getKey().compareTo(key) < 0) {
root.setRight(insert(root.getRight(), key, value));
} else {
size--;
throw new RuntimeException("duplicate Key!");
}
return rebalance(root);
}
private AVLTreeNode<K,V> minValueNode(AVLTreeNode<K,V> root){
if(root == null) return null;
else {
if(root.getLeft() != null) return minValueNode(root.getLeft());
else return root;
}
}
private AVLTreeNode<K,V> rebalance(AVLTreeNode<K,V> z) {
updateHeight(z);
int balance = getBalance(z);
if (balance > 1) {
if (height(z.getRight().getRight()) > height(z.getRight().getLeft())) {
z = rotateLeft(z);
} else {
z.setRight(rotateRight(z.getRight()));
z = rotateLeft(z);
}
} else if (balance < -1) {
if (height(z.getLeft().getLeft()) > height(z.getLeft().getRight()))
z = rotateRight(z);
else {
z.setLeft(rotateLeft(z.getLeft()));
z = rotateRight(z);
}
}
return z;
}
public void replace(K key, V newValue) {
replace(super.getRoot(), key, newValue);
}
private void replace(AVLTreeNode<K, V> root, K key, V newValue) {
if(root != null){
if(root.getKey().compareTo(key) == 0) root.setValue(newValue);
else if(root.getKey().compareTo(key) > 0) replace(root.getLeft(), key, newValue);
else replace(root.getRight(), key, newValue);
}
}
public void replaceAll(V oldValue, V newValue){
replaceAll(super.getRoot(), oldValue, newValue);
}
private void replaceAll(AVLTreeNode<K, V> root, V oldValue, V newValue){
if(root == null) return;
if(root.getValue().equals(oldValue)) root.setValue(newValue);
replaceAll(root.left, oldValue, newValue);
replaceAll(root.right, oldValue, newValue);
}
private AVLTreeNode<K,V> rotateLeft(AVLTreeNode<K,V> y){
AVLTreeNode<K,V> x = y.getRight();
AVLTreeNode<K,V> z = x.getLeft();
x.setLeft(y);
y.setRight(z);
updateHeight(y);
updateHeight(x);
return x;
}
private AVLTreeNode<K,V> rotateRight(AVLTreeNode<K,V> y){
AVLTreeNode<K,V> x = y.getLeft();
AVLTreeNode<K,V> z = x.getRight();
x.setRight(y);
y.setLeft(z);
updateHeight(y);
updateHeight(x);
return x;
}
public Object[] toArray(){
return toArray(super.getRoot(), new Array<>(size()));
}
private Object[] toArray(AVLTreeNode<K,V> root, Array<AVLTreeNode<K,V>> arr){
if(root != null){
toArray(root.left, arr);
arr.insert(root);
toArray(root.right, arr);
}
return arr.toArray();
}
private void updateHeight(AVLTreeNode<K,V> root){
root.setHeight(1 + Math.max(height(root.getLeft()), height(root.getRight())));
}
public static class AVLTreeNode<K extends Comparable<K>, V> implements Node<V> {
private static final long serialVersionUID = -2099221188924293375L;
private AVLTreeNode<K,V> left, right;
private K key;
private V value;
private int height = 0;
public AVLTreeNode(K key, V value){
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
@SuppressWarnings("unused")
private void setKey(K key) {
this.key = key;
}
public AVLTreeNode<K,V> getLeft() {
return left;
}
protected void setLeft(AVLTreeNode<K,V> left) {
this.left = left;
}
public AVLTreeNode<K,V> getRight() {
return right;
}
protected void setRight(AVLTreeNode<K,V> right) {
this.right = right;
}
@Override
public String toString() {
return "{"key":"+key+","value":"+getValue()+"}";
}
@Override
public V getValue() {
return value;
}
@Override
public void setValue(V value) {
this.value = value;
}
public int getHeight() {
return height;
}
protected void setHeight(int height) {
this.height = height;
}
public int getBalance() {
return (left != null ? left.getHeight() : 0) - (right != null ? right.getHeight() : 0);
}
}
}
父类是:
package structure.tree;
import structure.Structure;
import structure.node.Node;
/**
* A Tree is a {@Structure} that uses {@Node} as value.
*/
public abstract class Tree<N extends Node<?>> {
private static final long serialVersionUID = -2524427972418434522L;
private N root;
public void clear() {
root = null;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public N getRoot() {
return root;
}
protected void setRoot(N value) {
this.root = value;
}
}
这是我运行的代码，给出了一些问题注意，有时它工作，有时它不:
AVLTree<Integer,Integer> avlt = new AVLTree<Integer,Integer>();
Random r = new Random();
for(int i = 1; i <= SIZE; i++){
avlt.insert(i, r.nextInt(keySize));
}
int vdel = r.nextInt(keySize);
avlt.deleteAll(vdel);
assertEquals(false, avlt.containsValue(vdel));
问题是，当您试图查找要删除的节点时，树结构发生了变化。
考虑这棵树，我们将从中删除'X':
2->X
/
1->X 3->X
4->O
删除操作从'2'开始。由于"2"节点有一个左侧分支，我们下降到"1"节点。'1'节点既没有左分支也没有右分支，因此没有进一步下降。
节点'1'必须被删除。
2->X
3->X
4->O
然后树需要重新平衡。
3->X
/
2->X 4->O
这完成了对'1'节点的处理，因此递归搜索移回'2'。
左侧分支已被处理。由于再平衡，不再有一个右手分支来处理。"2"节点本身需要删除。
3->X
4->O
这完成了节点'2'的处理，所以我们返回。此算法完成。
节点'3'和'4'未被检查，因为重新平衡。
如何解决这个问题?
最简单的解决方案是将搜索与"删除"one_answers"重新平衡"分开。操作。创建映射到要删除的值的所有键的集合。一旦识别出所有这样的键，就一次删除一个映射。由于树在搜索过程中不会改变形状，因此搜索将找到所有相关的键值对。
我自己的偏好是在支持删除的树节点上创建一个Iterator。除了删除匹配值之外，这样的迭代器还可以用于其他任务。对于这样的迭代器，需要能够从任何指定的节点中识别出下一个节点。这意味着一个节点必须知道它的父节点是什么。
为此，我建议将您的代码修改如下:
节点实现跟踪它的父节点，并且它的键不能被更改。
public static class AVLTreeNode<K extends Comparable<K>, V> implements Node<V> {
private AVLTreeNode<K,V> left, right, parent;
private final K key;
private V value;
private int height = 0;
public AVLTreeNode(K key, V value){
this.key = key;
this.value = value;
}
protected void setLeft(AVLTreeNode<K,V> left) {
this.left = left;
if( left!=null ) {
left.parent = this;
}
}
public AVLTreeNode<K,V> getNext() {
AVLTreeNode<K,V> next;
// If a right branch exists, the next node is the left-most node in the right branch.
if( right!=null ) {
next = right;
while( next.left!=null ) {
next = next.left;
}
return next;
}
// The closest parent of which this is a left-branch descendant is the next node
next = this;
while( next.parent!=null ) {
if( next.parent.left==next ) {
return next.parent;
}
next = next.parent;
}
// no next node
return null;
}
protected void setRight(AVLTreeNode<K,V> right) {
this.right = right;
if( right!=null ) {
right.parent = this;
}
}
... rest of class is unchanged
}
树的插入和删除方法可以将节点移动到树的根，所以如果发生这种情况，它们也必须将节点的父节点设置为null。
public void insert(K key, V value) {
size++;
AVLTreeNode<K,V> newRoot = insert(super.getRoot(),key,value);
newRoot.parent = null;
super.setRoot(newRoot);
}
public void delete(K key){
AVLTreeNode<K,V> newRoot = delete(super.getRoot(), key);
if( newRoot!=null ) {
newRoot.parent = null;
}
super.setRoot(newRoot);
}
delete方法更改了节点的键，使其偏离顺序。为了保持序列，它不能这样做。
private AVLTreeNode<K,V> delete(AVLTreeNode<K,V> root, K key) {
if (root == null) {
return root;
} else if (root.getKey().compareTo(key) > 0) {
root.setLeft(delete(root.left, key));
} else if (root.getKey().compareTo(key) < 0) {
root.setRight(delete(root.right, key));
} else {
if (root.left == null || root.right == null) {
root = (root.left == null) ? root.right : root.left;
} else {
// Promote the next node to replace root.
AVLTreeNode<K,V> mostLeftChild = minValueNode(root.right);
mostLeftChild.setRight(delete(root.right, mostLeftChild.key));
mostLeftChild.setLeft(root.left);
root = mostLeftChild;
}
if(size > 0) size--;
}
if (root != null) {
root = rebalance(root);
}
return root;
}
则可以创建一个Iterator:
public static class AVLNodeIterator<K extends Comparable<K>,V> implements Iterator<AVLTreeNode<K,V>> {
AVLTree<K,V> tree;
AVLTreeNode<K,V> current;
AVLTreeNode<K,V> next;
public AVLNodeIterator(AVLTree<K,V> tree) {
this.tree = tree;
current = null;
next = tree.minValueNode(tree.getRoot());
}
@Override
public boolean hasNext() {
return next!=null;
}
@Override
public AVLTreeNode<K, V> next() {
if( next==null ) {
throw new NoSuchElementException();
}
current = next;
next = current.getNext();
return current;
}
@Override
public void remove() {
if( current==null ) {
throw new IllegalStateException();
}
tree.delete(current.getKey());
current=null;
}
}
，最后我们可以重写deleteAll来使用新的迭代器:
public void deleteAll(V value){
Iterator<AVLTreeNode<K,V>> iterator = new AVLNodeIterator<>(this);
while( iterator.hasNext()) {
AVLTreeNode<K,V> node = iterator.next();
if( node.getValue().equals(value) ) {
iterator.remove();
}
}
}