Geek asks and answers

Remove AVL Tree Code Example

I look through AVL trees and it seems I can’t find the deletion reference code (either from Googling, or from several tutorials that I have).
I am not sure why this is so, but do you know about any link / example of removing AVL in java?
(I only found this: deleting the avl tree , which it indicates in the link that it did not pass the test)

+5
source share
3 answers

I have an implementation of AVL Tree in Java that has been well tested if you want to use it for reference. It is based on the description of wikipedia, and it is very well commented.

, BST. node BST, .

BST (node node, node):

    ... 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);
            }
        }
    }
+3

( , ), node, , ( ), . ; node, , , , node, . , , . - AVL Scheme; , , :

(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)))))))
+2
source

More articles:


All Articles