AVL tree on Emacs Lisp

avl-tree.el

;; AVL-tree
(defun avltree-create-node (key)
  (list key 1 nil nil))

(defun avltree-height (node)
  (if (eq node nil)
      0
    (nth 1 node)))

(defun avltree-bfactor (node)
  (- (avltree-height (nth 2 node)) (avltree-height (nth 3 node))))

(defun avltree-fixheight (node)
  (let ((hl (avltree-height (nth 2 node)))
	(hr (avltree-height (nth 3 node))))
    '((nth 0 node)
      (+ 1
	 (if (> hl hr) hl hr))
      (nth 2 node)
      (nth 3 node))))

(defun avltree-rotateright (node)
  (let ((q (nth 2 node))
	(pleft (nth 3 q))
	(qright node))
    (avltree-fixheight node)
    (avltree-fixheight q)
    q))

(defun avltree-rotateleft (node)
  (let ((p (nth 3 node))
	(qright (nth 2 p))
	(pleft node))
    (avltree-fixheight node)
    (avltree-fixheight p)
    p))

(defun avltree-balance (node)
  (avltree-fixheight node)
  (if (eq (avltree-bfactor node) 2)
      (if (< (avltree-bfactor (nth 3 node)) 0)
	  (avltree-rotateleft '((nth 0 node)
				(nth 1 node)
				(nth 2 node)
				(avltree-rotateright (nth 3 node))))))
  (if (eq (avltree-bfactor node) -2)
      (if (> (avltree-bfactor (nth 2 node)) 0)
	  (avltree-rotateright '((nth 0 node)
				 (nth 1 node)
				 (avltree-rotateleft (nth 2 node))
				 (nth 3 node)))))
  node)

(defun avltree-insert (node key)
  (if (eq node nil)
      (avltree-create-node key)
    (let ((pleft (nth 2 node))
	(pright (nth 3 node)))
    (if (< key (nth 0 node))
	(setq pleft (avltree-insert pleft key))
      (setq pright (avltree-insert pright key)))
    (avltree-balance (list (nth 0 node)
		       (nth 1 node)
		       pleft
		       pright)))))

(defun avltree-findmin (node)
  (if (not (eq (node nil)))
      (avltree-findmin (nth 2 node))
    p))

(defun avltree-removemin (node)
  (let ((pleft (nth 2 node)))
    (if (eq pleft 0)
	(nth 3 node))
    (setq pleft (avltree-removemin pleft))
    (avltree-balance (node))))

(defun avltree-remove (node key)
  (let ((pleft (nth 2 node))
	(pright (nth 3 node)))
    (if (eq node nil)
	0
      (if (< key (nth 0 node))
	  (avltree-balance (list (nth 0 node)
			   (nth 1 node)
			   (avltree-remove pleft key)
			   (nth 3 node)))
	(if (> key (nth 0 node))
	    (avltree-balance (list (nth 0 node)
			     (nth 1 node)
			     (nth 2 node)
			     (avltree-remove pright key)))
	  (let ((q (nth 2 node))
		(r (nth 3 node)))
	    (if (eq r nil)
		q
	      (let ((min avltree-findmin r))
		(let ((minright (avltree-removemin r))
		      (minleft q))
		  (avltree-balance min))))))))))
 

test.el

(let ((root (avltree-create-node 5)))
  (setq root (avltree-insert root 12))
  (setq root (avltree-insert root 2))
  (setq root (avltree-remove root 12))
  (setq root (avltree-insert root 42))
  (setq root (avltree-insert root 64))
  (setq root (avltree-insert root 50))
  root)