diff options
| author | Paul Eggert <eggert@cs.ucla.edu> | 2012-04-09 15:54:59 -0700 |
|---|---|---|
| committer | Paul Eggert <eggert@cs.ucla.edu> | 2012-04-09 15:54:59 -0700 |
| commit | 45e9f7da84c1bd3fc0d36d05c5708ed3b2d3a193 (patch) | |
| tree | 5bc87a8b5a3c754b8eb44a612cc6c03561d6b968 /lisp/emacs-lisp/avl-tree.el | |
| parent | 9d6b4d53469a9ffd67bd770fabc6fe254e35c21d (diff) | |
| parent | 05920a43fc18e696b464387e781e7cfdcea5b5af (diff) | |
| download | emacs-45e9f7da84c1bd3fc0d36d05c5708ed3b2d3a193.tar.gz emacs-45e9f7da84c1bd3fc0d36d05c5708ed3b2d3a193.tar.bz2 emacs-45e9f7da84c1bd3fc0d36d05c5708ed3b2d3a193.zip | |
Merge from trunk.
Diffstat (limited to 'lisp/emacs-lisp/avl-tree.el')
| -rw-r--r-- | lisp/emacs-lisp/avl-tree.el | 16 |
1 files changed, 13 insertions, 3 deletions
diff --git a/lisp/emacs-lisp/avl-tree.el b/lisp/emacs-lisp/avl-tree.el index cb5ea048999..9f348767478 100644 --- a/lisp/emacs-lisp/avl-tree.el +++ b/lisp/emacs-lisp/avl-tree.el @@ -295,9 +295,9 @@ Return t if the height of the tree has grown." (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) @@ -339,6 +339,16 @@ inserted data." (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))))) + ;; ---------------------------------------------------------------- |