Author: abaine Date: Sat Aug 4 10:14:03 2007 New Revision: 116
Modified: trunk/funds/src/trees/tree-insert.lisp Log: Changed tree-insert specializer to no longer be a specializer. So leaves are now a special case, and tree insertion proceeds the same for binary trees and avl trees. The difference is that anytime during insertion or removal that a tree is 'stitched' together, stitch-tree balances an avl tree but not a binary tree; also I moved stitch-tree functions to the stitch-tree file.
Modified: trunk/funds/src/trees/tree-insert.lisp ============================================================================== --- trunk/funds/src/trees/tree-insert.lisp (original) +++ trunk/funds/src/trees/tree-insert.lisp Sat Aug 4 10:14:03 2007 @@ -27,16 +27,14 @@
(defmethod tree-insert ((tree bt-leaf) key value &key test order) (declare (ignore test order)) - (make-instance 'binary-tree - :key key - :value value)) + (stitch-binary-tree :key key :value value))
(defmethod tree-insert ((tree avl-leaf) key value &key test order) (declare (ignore test order)) - (stitch-avl-tree :key key - :value value)) + (stitch-avl-tree :key key :value value))
-(defmethod tree-insert ((tree binary-tree) key value &key (test #'eql) (order #'<)) + +(defmethod tree-insert (tree key value &key (test #'eql) (order #'<)) (if (funcall test key (bt-key tree)) (stitch-tree tree :key key :value value :left (bt-left tree) :right (bt-right tree)) (let* ((side (side-to-insert tree key :order order)) @@ -46,15 +44,3 @@ :test test :order order) other-side (tree-child tree :side other-side))))) - -(defmethod stitch-tree ((tree binary-tree) - &key (key (bt-key tree)) (value (bt-value tree)) left right) - (make-instance 'binary-tree - :key key - :value value - :left left - :right right)) - -(defmethod stitch-tree ((tree avl-tree) - &key (key (bt-key tree)) (value (bt-value tree)) left right) - (balance key value left right))