►AVL Trees
AVL Trees
1 Creating Trees
make-avl
make-avleq
make-avleqv
make-custom-avl
avl-copy
2 Predicates
avl?
avl-equal?
avl-eqv?
avl-eq?
avl-empty?
avl-contains?
avl-search
3 Manipulating Values
avl-add
avl-add!
avl-remove
avl-remove!
avl-mirror
avl-mirror!
4 Queue Usage
avl-min
avl-max
avl-pop-min
avl-pop-min!
avl-pop-max
avl-pop-max!
5 Iterating Over Values
in-avl
in-avl/  reverse
avl->list
7.7
  top  ← prev  up  next → 

AVL Trees

Jan Dvořák <mordae@anilinux.org>

 (require avl) package: avl

A self-balancing binary search tree variant.

All mutations of the AVL tree create new nodes instead of modifying the data in place. The imperative variants change the root node in place for convenience. Mutating the tree is not thread-safe.

These trees could be used for as priority queues with possibility to remove elements from the middle.

1 Creating Trees

procedure

(make-avl <=?) → avl?

  <=? : procedure?

procedure

(make-avleq <=?) → avl?

  <=? : procedure?

procedure

(make-avleqv <=?) → avl?

  <=? : procedure?
Create new tree using specified comparator function.

Like hash tables, every AVL tree variant uses a different equality predicate. make-avl uses equal?, make-avleq uses eq? and make-avleqv uses eqv?.

Tree with number? elements would use <= as the comparator, tree with string? elements would use string<=? and so on.

Examples:
> (define tree (make-avleqv <=))
> (avl-add! tree 42)

procedure

(make-custom-avl <=? =?) → avl?

  <=? : procedure?
  =? : procedure?
Create new tree using both specified comparator function and equality predicate.

Examples:
> (define custom-avl
    (make-custom-avl (λ (x y) (<= (car x) (car y)))
                     (λ (x y) (equal? (car x) (car y)))))
> (avl-add! custom-avl (cons 1 'hello))
> (avl-add! custom-avl (cons 2 'ciao))
> (avl-add! custom-avl (cons 1 'bye))
> (avl->list custom-avl)

'((1 . bye) (2 . ciao))

procedure

(avl-copy tree) → avl?

  tree : avl?
Copy the tree container, effectively creating a standalone tree that is decoupled from the original.

Examples:
> (define copy (avl-copy tree))
> (avl-remove! copy 42)

2 Predicates

procedure

(avl? v) → boolean?

  v : any/c
Predicate identifying the AVL tree.

Examples:
> (avl? tree)

#t

> (avl? copy)

#t

> (avl? 'something-else)

#f

procedure

(avl-equal? v) → boolean?

  v : any/c

procedure

(avl-eqv? v) → boolean?

  v : any/c

procedure

(avl-eq? v) → boolean?

  v : any/c
Predicates for trees created using respective constructors above.

Examples:
> (avl-equal? tree)

#f

> (avl-eqv? tree)

#t

> (avl-eq? tree)

#f

procedure

(avl-empty? tree) → boolean?

  tree : avl?
Determine whether the tree contains no values.

Examples:
> (avl-empty? tree)

#f

> (avl-empty? copy)

#t

procedure

(avl-contains? tree value) → boolean?

  tree : avl?
  value : any/c
Determine whether the tree contains specified value at least once.

Examples:
> (avl-contains? tree 42)

#t

> (avl-contains? copy 42)

#f

procedure

(avl-search tree value) → any/c?

  tree : avl?
  value : any/c
Search the tree and return a needle corresponding to the specified value. Return #f if none exist.

Examples:
> (define animal-dict
    (make-custom-avl (λ (x y) (<= (car x) (car y)))
                     (λ (x y) (equal? (car x) (car y)))))
> (avl-add! animal-dict (cons 1 'cat))
> (avl-add! animal-dict (cons 2 'dog))
> (avl-add! animal-dict (cons 3 'mouse))
> (avl->list animal-dict)

'((1 . cat) (2 . dog) (3 . mouse))

> (define (search-by-key tree key)
    (avl-search tree (cons key '())))
> (search-by-key animal-dict 1)

'(1 . cat)

> (search-by-key animal-dict 2)

'(2 . dog)

> (search-by-key animal-dict 3)

'(3 . mouse)

> (search-by-key animal-dict 4)

#f

3 Manipulating Values

procedure

(avl-add tree value) → avl?

  tree : avl?
  value : any/c
Create new tree containing specified value.

Examples:
> (let ((new-tree (avl-add tree 13)))
    (avl-contains? new-tree 13))

#t

> (avl-contains? tree 13)

#f

procedure

(avl-add! tree value) → void?

  tree : avl?
  value : any/c
Like avl-add, but the container is modified in place.

Examples:
> (avl-add! tree 13)
> (avl-contains? tree 13)

#t

procedure

(avl-remove tree value) → avl?

  tree : avl?
  value : any/c
Create new tree without the first instance of the value.

Examples:
> (let ((new-tree (avl-remove tree 13)))
    (avl-contains? new-tree 13))

#f

> (avl-contains? tree 13)

#t

procedure

(avl-remove! tree value) → void?

  tree : avl?
  value : any/c
Like avl-remove, but the container is modified in place.

Examples:
> (avl-remove! tree 13)
> (avl-contains? tree 13)

#f

procedure

(avl-mirror tree) → avl?

  tree : avl?
Mirror (invert) a tree by swapping each left and right node. Returns the mirrored tree.

Example:
> (let ([new-tree (make-avl <)])
    (avl-add! new-tree 55)
    (avl-add! new-tree 10)
    (avl-add! new-tree 99)
    (avl->list (avl-mirror new-tree)))

'(99 55 10)

procedure

(avl-mirror! tree) → void?

  tree : avl?
Like avl-mirror, but the container is modified in place.

Example:
> (let ([new-tree (make-avl <)])
    (avl-add! new-tree 55)
    (avl-add! new-tree 10)
    (avl-add! new-tree 99)
    (avl-mirror! new-tree)
    (avl->list new-tree))

'(99 55 10)

4 Queue Usage

procedure

(avl-min tree) → any/c

  tree : avl?
Find smallest (leftmost) value in the tree.

Examples:
> (avl-add! tree 21)
> (avl-min tree)

21

procedure

(avl-max tree) → any/c

  tree : avl?
Find largest (rightmost) value in the tree.

Examples:
> (avl-add! tree 101)
> (avl-max tree)

101

procedure

(avl-pop-min tree) → 
any/c avl?
  tree : avl?
Find and remove smallest (leftmost) value from the tree. Returns both the removed value and new tree container.

Examples:
> (avl-pop-min tree)

21

#<avl>

> (avl-min tree)

21

procedure

(avl-pop-min! tree) → any/c

  tree : avl?
Like avl-pop-min, but returns only the value and modifies the container in place.

Examples:
> (avl-pop-min! tree)

21

> (avl-min tree)

42

procedure

(avl-pop-max tree) → 
any/c avl?
  tree : avl?
Find and remove largest (rightmost) value from the tree. Returns both the removed value and new tree container.

Examples:
> (avl-pop-max tree)

101

#<avl>

> (avl-max tree)

101

procedure

(avl-pop-max! tree) → any/c

  tree : avl?
Like avl-pop-max, but returns only the value and modifies the container in place.

Examples:
> (avl-pop-max! tree)

101

> (avl-max tree)

42

5 Iterating Over Values

procedure

(in-avl tree) → sequence?

  tree : avl?
Iterate over the tree values in ascending order.

Example:
> (for/list ((value (in-avl tree)))
    (* value 10))

'(420)

procedure

(in-avl/reverse tree) → sequence?

  tree : avl?
Iterate over the tree values in descending order.

Example:
> (for/list ((value (in-avl/reverse tree)))
    (/ value 10))

'(21/5)

procedure

(avl->list tree) → list?

  tree : avl?
Convert the tree to an ordered list.

Examples:
> (avl->list tree)

'(42)

> (avl->list copy)

'()

  top  ← prev  up  next →