Function: avl-tree--del-balance

avl-tree--del-balance is a byte-compiled function defined in avl-tree.el.gz.

Signature

(avl-tree--del-balance NODE BRANCH DIR)

Documentation

Rebalance a tree after deleting a NODE.

The deletion was done from the left (DIR=0) or right (DIR=1) sub-tree of the left (BRANCH=0) or right (BRANCH=1) child of NODE. Return t if the height of the tree has shrunk.

Source Code

;; Defined in /usr/src/emacs/lisp/emacs-lisp/avl-tree.el.gz
;; ----------------------------------------------------------------
;;                          Deleting data

(defun avl-tree--del-balance (node branch dir)
  "Rebalance a tree after deleting a NODE.
The deletion was done from the left (DIR=0) or right (DIR=1) sub-tree
of the left (BRANCH=0) or right (BRANCH=1) child of NODE.
Return t if the height of the tree has shrunk."
  ;; (or is it vice-versa for BRANCH?)
  (let ((br (avl-tree--node-branch node branch))
	;; opposite direction: 0,1 -> 1,0
	(opp (avl-tree--switch-dir dir))
	;; direction 0,1 -> sign factor -1,+1
	(sgn (avl-tree--dir-to-sign dir))
        p1 b1 p2 b2)
    (cond
     ((> (* sgn (avl-tree--node-balance br)) 0)
      (setf (avl-tree--node-balance br) 0)
      t)

     ((= (avl-tree--node-balance br) 0)
      (setf (avl-tree--node-balance br) (- sgn))
      nil)

     (t
      ;; Rebalance.
      (setq p1 (avl-tree--node-branch br opp)
            b1 (avl-tree--node-balance p1))
      (if (<= (* sgn b1) 0)
          ;; Single rotation.
          (progn
            (setf (avl-tree--node-branch br opp)
		    (avl-tree--node-branch p1 dir)
		  (avl-tree--node-branch p1 dir) br
		  (avl-tree--node-branch node branch) p1)
            (if (= 0 b1)
                (progn
                  (setf (avl-tree--node-balance br) (- sgn)
			(avl-tree--node-balance p1) sgn)
                  nil)  ; height hasn't changed
              (setf (avl-tree--node-balance br) 0)
              (setf (avl-tree--node-balance p1) 0)
              t))  ; height has changed

        ;; Double rotation.
        (setf p2 (avl-tree--node-branch p1 dir)
              b2 (avl-tree--node-balance p2)
	      (avl-tree--node-branch p1 dir)
                (avl-tree--node-branch p2 opp)
	      (avl-tree--node-branch p2 opp) p1
	      (avl-tree--node-branch br opp)
                (avl-tree--node-branch p2 dir)
	      (avl-tree--node-branch p2 dir) br
	      (avl-tree--node-balance br)
                (if (< (* sgn b2) 0) sgn 0)
	      (avl-tree--node-balance p1)
                (if (> (* sgn b2) 0) (- sgn) 0)
	      (avl-tree--node-branch node branch) p2
	      (avl-tree--node-balance p2) 0)
        t)))))