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.

1Creating Trees🔗 i

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! tree42)

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 (λ (xy)(<= (car x)(car y)))
(λ (xy)(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! copy42)

2Predicates🔗 i

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? treevalue)→boolean?
tree:avl?
value:any/c

Determine whether the tree contains specified value at least once.

Examples:

> (avl-contains? tree42)

#t
> (avl-contains? copy42)

#f

procedure
( avl-search treevalue)→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 (λ (xy)(<= (car x)(car y)))
(λ (xy)(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-keytreekey)
(avl-search tree(cons key'())))
> (search-by-keyanimal-dict1)

'(1 . cat)
> (search-by-keyanimal-dict2)

'(2 . dog)
> (search-by-keyanimal-dict3)

'(3 . mouse)
> (search-by-keyanimal-dict4)

#f

3Manipulating Values🔗 i

procedure
( avl-add treevalue)→avl?
tree:avl?
value:any/c

Create new tree containing specified value.

Examples:

> (let ((new-tree(avl-add tree13)))
(avl-contains? new-tree13))

#t
> (avl-contains? tree13)

#f

procedure
( avl-add! treevalue)→void?
tree:avl?
value:any/c

Like avl-add , but the container is modified in place.

Examples:

> (avl-add! tree13)
> (avl-contains? tree13)

#t

procedure
( avl-remove treevalue)→avl?
tree:avl?
value:any/c

Create new tree without the first instance of the value.

Examples:

> (let ((new-tree(avl-remove tree13)))
(avl-contains? new-tree13))

#f
> (avl-contains? tree13)

#t

procedure
( avl-remove! treevalue)→void?
tree:avl?
value:any/c

Like avl-remove , but the container is modified in place.

Examples:

> (avl-remove! tree13)
> (avl-contains? tree13)

#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-tree55)
(avl-add! new-tree10)
(avl-add! new-tree99)
(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-tree55)
(avl-add! new-tree10)
(avl-add! new-tree99)
(avl-mirror! new-tree)
(avl->list new-tree))

'(99 55 10)

4Queue Usage🔗 i

procedure
( avl-min tree)→any/c
tree:avl?

Find smallest (leftmost) value in the tree.

Examples:

> (avl-add! tree21)
> (avl-min tree)

21

procedure
( avl-max tree)→any/c
tree:avl?

Find largest (rightmost) value in the tree.

Examples:

> (avl-add! tree101)
> (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

5Iterating Over Values🔗 i

procedure
( in-avl tree)→sequence?
tree:avl?

Iterate over the tree values in ascending order.

Example:

> (for/list ((value(in-avl tree)))
(* value10))

'(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)))
(/ value10))

'(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 →