我正在研究 AVL 树，但似乎找不到关于删除的参考代码（通过谷歌搜索或从我方便的几本教科书）。
我不确定为什么会这样，但是您知道在 java 中删除 AVL 的任何参考/示例吗？
（我只发现了这个：avl tree removal，它在链接中说明它在测试中失败）
问问题
9776 次
3 回答
3
我有一个Java 中的 AVL 树的实现，它已经过很好的测试，如果您想使用它作为参考。它基于维基百科的描述，并且评论很好。
就像您在常规 BST 插入后必须保持平衡一样。您像 BST 一样删除节点，然后根据以下算法进行平衡。
在 BST 移除后进行平衡的情况是（节点是用于替换被移除节点的节点的父节点）：
... remove code ...
// Re-balance the tree all the way up the tree
while (nodeToRefactor != null) {
nodeToRefactor.updateHeight();
balanceAfterDelete(nodeToRefactor);
nodeToRefactor = (AVLNode<T>) nodeToRefactor.parent;
}
... remove code ...
... balance code ...
int balanceFactor = node.getBalanceFactor();
if (balanceFactor==-2 || balanceFactor==2) {
if (balanceFactor==-2) {
AVLNode<T> ll = (AVLNode<T>) node.lesser.lesser;
int lesser = ll.height;
AVLNode<T> lr = (AVLNode<T>) node.lesser.greater;
int greater = lr.height;
if (lesser>=greater) {
rightRotation(node);
} else {
leftRotation(node.lesser);
rightRotation(node);
}
} else if (balanceFactor==2) {
AVLNode<T> rr = (AVLNode<T>) node.greater.greater;
int greater = rr.height;
AVLNode<T> rl = (AVLNode<T>) node.greater.lesser;
int lesser = rl.height;
if (greater>=lesser) {
leftRotation(node);
} else {
rightRotation(node.greater);
leftRotation(node);
}
}
}
于 2012-05-27T12:30:00.777 回答
2
树删除的工作原理是搜索（以与查找相同的方式）直到找到要删除的节点，用它的最小后继节点替换它（你也可以使用它的最大前驱节点），然后重新平衡树。再平衡是自下而上进行的；在找到要删除的节点后，该算法向下插入右子树的左脊柱，找到最小的后继节点，并在它返回树的过程中重新平衡到被删除的节点，该节点被最小后继节点替换。唯一的特殊情况发生在树中不存在被删除的项目时，在这种情况下，树将原封不动地返回。这是我在 Scheme 中实现的 AVL 树；通过使用递归而不是更传统的迭代，代码变得非常简单：
(define (tree k v l r)
(vector k v l r (+ (max (ht l) (ht r)) 1)))
(define (key t) (vector-ref t 0))
(define (val t) (vector-ref t 1))
(define (lkid t) (vector-ref t 2))
(define (rkid t) (vector-ref t 3))
(define (ht t) (vector-ref t 4))
(define (bal t) (- (ht (lkid t)) (ht (rkid t))))
(define nil (vector 'nil 'nil 'nil 'nil 0))
(vector-set! nil 2 nil)
(vector-set! nil 3 nil)
(define (nil? t) (eq? t nil))
(define (rot-left t)
(if (nil? t) t
(tree (key (rkid t))
(val (rkid t))
(tree (key t) (val t) (lkid t) (lkid (rkid t)))
(rkid (rkid t)))))
(define (rot-right t)
(if (nil? t) t
(tree (key (lkid t))
(val (lkid t))
(lkid (lkid t))
(tree (key t) (val t) (rkid (lkid t)) (rkid t)))))
(define (balance t)
(let ((b (bal t)))
(cond ((< (abs b) 2) t)
((positive? b)
(if (< -1 (bal (lkid t))) (rot-right t)
(rot-right (tree (key t) (val t)
(rot-left (lkid t)) (rkid t)))))
((negative? b)
(if (< (bal (rkid t)) 1) (rot-left t)
(rot-left (tree (key t) (val t)
(lkid t) (rot-right (rkid t)))))))))
(define (lookup lt? t k)
(cond ((nil? t) #f)
((lt? k (key t)) (lookup lt? (lkid t) k))
((lt? (key t) k) (lookup lt? (rkid t) k))
(else (cons k (val t)))))
(define (insert lt? t k v)
(cond ((nil? t) (tree k v nil nil))
((lt? k (key t))
(balance (tree (key t) (val t)
(insert lt? (lkid t) k v) (rkid t))))
((lt? (key t) k)
(balance (tree (key t) (val t)
(lkid t) (insert lt? (rkid t) k v))))
(else (tree k v (lkid t) (rkid t)))))
(define (delete-successor t)
(if (nil? (lkid t)) (values (rkid t) (key t) (val t))
(call-with-values
(lambda () (delete-successor (lkid t)))
(lambda (l k v)
(values (balance (tree (key t) (val t) l (rkid t))) k v)))))
(define (delete lt? t k)
(cond ((nil? t) nil)
((lt? k (key t))
(balance (tree (key t) (val t)
(delete lt? (lkid t) k) (rkid t))))
((lt? (key t) k)
(balance (tree (key t) (val t)
(lkid t) (delete lt? (rkid t) k))))
((nil? (lkid t)) (rkid t))
((nil? (rkid t)) (lkid t))
(else (call-with-values
(lambda () (delete-successor (rkid t)))
(lambda (r k v) (balance (tree k v (lkid t) r)))))))
于 2012-05-27T12:01:33.417 回答
2
算法并没有那么糟糕，一旦你实现了balance()......
想到的第一个实现是 Apache Commons Collections 中 TreeList 的实现，它是一个由 AVL 树支持的列表。 http://www.docjar.org/html/api/org/apache/commons/collections/list/TreeList.java.html有源代码。
于 2012-05-27T09:51:39.857 回答