Author: abaine Date: Tue Jul 3 14:57:04 2007 New Revision: 46
Modified: trunk/funds/src/trees/avl-tree.lisp Log: Refactored left and right rotate.
Modified: trunk/funds/src/trees/avl-tree.lisp ============================================================================== --- trunk/funds/src/trees/avl-tree.lisp (original) +++ trunk/funds/src/trees/avl-tree.lisp Tue Jul 3 14:57:04 2007 @@ -102,45 +102,17 @@ ;;;; Rotation Functions
(defun left-rotate (t0 a b) - (let ((c (avl-right b)) - (new-a (make-avl :ht (1- (avl-ht a)) ; re-calculate? - :key (avl-key a) - :value (avl-value a) - :left t0 - :right (avl-left b)))) - (make-avl :ht (1+ (avl-ht new-a)) - :key (avl-key b) - :value (avl-value b) - :left new-a - :right c))) + (rotate t0 a b :direction :left))
(defun right-rotate (t3 c b) - (let ((a (avl-left b)) - (new-c (make-avl :ht (1- (avl-ht c)); re-calculate? - :key (avl-key c) - :value (avl-value c) - :left (avl-right b) - :right t3))) - (make-avl :ht (1+ (avl-ht new-c)) ; re-calculate? - :key (avl-key b) - :value (avl-value b) - :left a - :right new-c))) + (rotate t3 c b :direction :right))
(defun rotate (inside root outside &key direction) (let* ((left-p (eq direction :left)) - (outside-accessor (if left-p - #'avl-right - #'avl-left)) - (inside-accessor (if left-p - #'avl-left - #'avl-right)) - (inside-init-key (if left-p - :left - :right)) - (outside-init-key (if left-p - :right - :left)) + (outside-accessor (if left-p #'avl-right #'avl-left)) + (inside-accessor (if left-p #'avl-left #'avl-right)) + (inside-init-key (if left-p :left :right)) + (outside-init-key (if left-p :right :left)) (new-outside (funcall outside-accessor outside)) (new-inside (make-avl :ht (1- (avl-height root)) :key (avl-key root)