Author: abaine Date: Wed Jun 20 14:22:40 2007 New Revision: 31
Modified: trunk/funds/src/trees/avl-tree.lisp Log: AVL-Insert properly documented.
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:22:40 2007 @@ -18,12 +18,17 @@ (null tree))
(defun avl-insert (tree key value &key (test #'eql) (order #'<)) + "The AVL Tree that results when the given key-value pair is inserted +into the given tree. If the test function determines that the given key +and the root key af the given tree are "equal", then a new AVL Tree is +created as if the given key-value pair replaced the root key-value pair. +The given order function, < by default, is used to determine the order of +the resulting AVL Tree." (cond ((avl-empty-p tree) (make-avl :ht 1 :key key :value value :left (empty-avl-tree) :right (empty-avl-tree))) - ((funcall test key (avl-key tree)) (make-avl :ht (avl-ht tree) :key key :value value @@ -38,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) + (if (imbalanced left right)n (if (left-heavy left) (right-rotate left tree right) (right-rotate (left-rotate (avl-left left) @@ -124,7 +129,7 @@ (minusp (balance-factor tree)))
(defun right-heavy (tree) - "Whether the given imbalanced AVL Tre has a right sub-tree + "Whether the given imbalanced AVL Tree has a right sub-tree taller than its left sub-tree." (plusp (balance-factor tree)))