java - AVL ツリーのサンプル コードから削除

Question

私はAVLツリーを調べていますが、削除に関する参照コードを見つけることができないようです（グーグルまたは私が手元にあるいくつかの教科書から）。
これがなぜなのかわかりませんが、JavaでAVLを削除した参考文献や例をご存知ですか？
（私はこれだけを見つけました：リンクでテスト中に失敗したと述べているavl ツリーの削除）

Answer 1

参照用に使用したい場合は、十分にテストされた 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);
            }
        }
    }

Answer 2

の実装があれば、アルゴリズムはそれほど悪くはありませんbalance()...

頭に浮かぶ最初の実装は、Apache Commons CollectionsでのTreeListの実装です。これは、AVLツリーに裏打ちされたリストです。 http://www.docjar.org/html/api/org/apache/commons/collections/list/TreeList.java.htmlにソースコードがあります。

Answer 3

ツリーの削除は、削除するノードが見つかるまで (ルックアップと同じ方法で) 検索し、それを最小の後続ノード (最大の先行ノードを使用することもできます) に置き換えてから、ツリーのバランスを取り直します。リバランスはボトムアップで行われます。削除するノードを見つけた後、アルゴリズムは右のサブツリーの左のスパインを下って最小の後継ノードを見つけ、削除されるノードまでツリーを遡ってリバランスし、最小の後継ノードに置き換えられます。唯一の特殊なケースは、削除されるアイテムがツリーに存在しない場合に発生します。この場合、ツリーは変更されずに返されます。これが私の 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)))))))