Author: abaine Date: Wed Jun 20 14:47:38 2007 New Revision: 32
Modified: trunk/funds/src/trees/avl-tree.lisp Log: Added avl-find-value function.
Modified: trunk/funds/src/trees/avl-tree.lisp ============================================================================== --- trunk/funds/src/trees/avl-tree.lisp (original) +++ trunk/funds/src/trees/avl-tree.lisp Wed Jun 20 14:47:38 2007 @@ -43,7 +43,7 @@ should be supplied as arguments." (let ((left (avl-insert (avl-left tree) key value :test test :order order)) (right (avl-right tree))) - (if (imbalanced left right)n + (if (imbalanced left right) (if (left-heavy left) (right-rotate left tree right) (right-rotate (left-rotate (avl-left left) @@ -103,6 +103,13 @@ :left a :right new-c)))
+(defun avl-find-value (tree key &key (order #'<) (test #'eql)) + (cond ((avl-empty-p tree) (values nil nil)) + ((funcall test key (avl-key tree)) (values (avl-value tree) t)) + ((funcall order key (avl-key tree)) + (avl-find-value (avl-left tree) key :order order :test test)) + (t (avl-find-value (avl-right tree) key :order order :test test)))) + (defun imbalanced (left right) "Whether the heights of the given sub-trees differ, in their absolute values, by more than one."