AVL Trees¶

Supports constructing AVL trees.

AVL trees are balanced search binary trees. They are named after their inventors, Adelson-Velskii and Landis, and they were the first dynamically balanced trees to be proposed. The YAP AVL tree manipulation predicates library uses code originally written by Martin van Emdem and published in the Logic Programming Newsletter, Autumn 1981. A bug in this code was fixed by Philip Vasey, in the Logic Programming Newsletter, Summer 1982. The library currently only includes routines to insert and lookup elements in the tree. Please try red-black trees if you need deletion.

AVl trees are available through the directive:

 :- use_module(library(avl)).

Currently, they support the following predicates:

• avl_insert//44

• avl_lookup//33

• avl_new//11

• prolog::avl_lookup/3

• prolog::avl_insert/4
• prolog::avl_new/1