Skip to content

Instantly share code, notes, and snippets.

@char16t
Created April 5, 2019 12:57
Show Gist options
  • Save char16t/85750b3ea99fbd4d9decfe7c67edfbd8 to your computer and use it in GitHub Desktop.
Save char16t/85750b3ea99fbd4d9decfe7c67edfbd8 to your computer and use it in GitHub Desktop.
AVL tree on Emacs Lisp
;; 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))))))))))
(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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment