An AVL tree is a form of self-balancing binary tree. Other types of self-balancing binary tree which serve a similar purpose are RedBlackTrees? and SplayTrees?. Recent versions of Emacs include an implementation of AVL trees (previously, it was part of the separate Elib package). To use them in your code, you need to

  (require 'avl)

TobyCubitt has written a drop-in replacement for the version included in Emacs, which adds a number of new functions, and adds new optional arguments to some existing functions. These enhancements are necessary for efficient implementations of certain algorithms involving AVL trees (which is, after all, the whole point!).

The updates are already included in Emacs as of version 24.1.

If want to use the updated avl-tree package on an older Emacsen, you can either grab the latest version from the main Emacs bzr repository (recommended), or it can be obtained separately from:

If you want to use this replacement version, but don’t want to overwrite the version included in Emacs, then make sure that the replacement version is saved to a path that appears earlier in your Emacs load-path than the directory containing the original version (usually something like /usr/share/emacs/lisp/emacs-lisp/ on *nix systems).

CategoryCode CategoryExtensions