Author: abaine Date: Wed Jun 20 13:06:54 2007 New Revision: 30
Modified: trunk/funds/src/trees/avl-tree.lisp Log: Minor semantic changes.
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 13:06:54 2007 @@ -103,6 +103,11 @@ in their absolute values, by more than one." (> (abs (height-difference left right)) 1))
+(defun balanced (left right) + "Whether the heights of the given sub-trees differ, +in their absolute values, by no more than one." + (< -2 (height-difference left right) 2)) + (defun height-difference (a b) "The difference in heights of the given sub-trees." (- (avl-height a) (avl-height b))) @@ -116,12 +121,12 @@ (defun left-heavy (tree) "Whether the given imbalanced AVL Tree has a left sub-tree taller than its right sub-tree." - (< (balance-factor tree) 0)) + (minusp (balance-factor tree)))
(defun right-heavy (tree) "Whether the given imbalanced AVL Tre has a right sub-tree taller than its left sub-tree." - (> (balance-factor tree) 0)) + (plusp (balance-factor tree)))
(defun balance-factor (tree) "The difference in heights of the right sub-tree and left