[funds-cvs] r31 - trunk/funds/src/trees

[abaine at common-lisp.net]

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)))