;;; avl-tree.el --- balanced binary trees, AVL-trees
-;; Copyright (C) 1995, 2007-2012 Free Software Foundation, Inc.
+;; Copyright (C) 1995, 2007-2014 Free Software Foundation, Inc.
;; Author: Per Cederqvist <ceder@lysator.liu.se>
;; Inge Wallin <inge@lysator.liu.se>
;; Thomas Bellman <bellman@lysator.liu.se>
;; Toby Cubitt <toby-predictive@dr-qubit.org>
-;; Maintainer: FSF
+;; Maintainer: emacs-devel@gnu.org
;; Created: 10 May 1991
;; Keywords: extensions, data structures, AVL, tree
(opp (avl-tree--switch-dir dir))
;; direction 0,1 -> sign factor -1,+1
(sgn (avl-tree--dir-to-sign dir))
- p1 p2 b2 result)
+ p1 p2 b2)
(cond
((< (* sgn (avl-tree--node-balance br)) 0)
(setf (avl-tree--node-balance br) 0)
(if (> (* sgn b2) 0) (- sgn) 0)
(avl-tree--node-balance p1)
(if (< (* sgn b2) 0) sgn 0)
- (avl-tree--node-branch node branch) p2
- (avl-tree--node-balance
- (avl-tree--node-branch node branch)) 0))
+ (avl-tree--node-branch node branch) p2))
+ (setf (avl-tree--node-balance
+ (avl-tree--node-branch node branch)) 0)
nil))))
(defun avl-tree--do-enter (cmpfun root branch data &optional updatefun)
(cons nil newdata)) ; return value
))))
+(defun avl-tree--check (tree)
+ "Check the tree's balance."
+ (avl-tree--check-node (avl-tree--root tree)))
+(defun avl-tree--check-node (node)
+ (if (null node) 0
+ (let ((dl (avl-tree--check-node (avl-tree--node-left node)))
+ (dr (avl-tree--check-node (avl-tree--node-right node))))
+ (assert (= (- dr dl) (avl-tree--node-balance node)))
+ (1+ (max dl dr)))))
+
;; ----------------------------------------------------------------