;; tree = (nl left middle nr right)

(defun prof (tree)
  (if (null tree) 0
    (1+ (max (first tree) (fourth tree))))
  )
  

(defun roda? (tree)
  (if (null tree) nil
    (let ((nl (first tree))
	  (nr (fourth tree))
	  )
      (cond
       ((> (- nr nl) 1) (arotate-l tree))
       ((> (- nl nr) 1) (arotate-r tree))
       (t tree))
      )))
      


(defun arotate-r (tree)
  " roda uma arvore para a direita"
  (destructuring-bind (nl (na a b nc c) m nr r) tree
    (list na a b (1+ (max nc nr)) (list nc c m nr r)))
  )


(defun arotate-l (tree)
  "roda uma arvore para a esquerda"
  (destructuring-bind (nl l m nr (na a b nc c)) tree
    (list (1+ (max nl na)) (list nl l m na a) b nc c)))


(defun avl-insert (tree dado)
"insere um dado numa arvore, retorna a arvore nova"
  (if (null tree) (list 0 nil dado 0 nil)
    (destructuring-bind (nl l m nr r) tree
      (if (= dado m) 
	  tree
	(if (> dado m) 
	    (let ((oo (avl-insert r dado))
		  )
	    (roda? (list nl l m (prof oo) oo )))
	  
	  (let ((oo (avl-insert l dado))
		)
	    (roda? (list  (prof oo) oo m nr r)))
	  ))
      )))
	  


(defun avl-delete (tree dado)
  "remove um dado da arvore, retorna a arvore nova"
  (if (null tree) nil
    (destructuring-bind (nl l m nr r) tree
      (let (oo)
	(roda? 
	   (cond 
	    ((and (= m dado) (null l)) r)
	    ((and (= m dado) (null r)) l)
	    ((= m dado) (avl-delete (arotate-r tree) dado))
	    ((< m dado) (setf oo (avl-delete r dado))
	     (list nl l m (prof oo) oo))
	    ((> m dado) (setf oo (avl-delete l dado))
	     (list (prof oo) oo  m nr r))
	    ))
	))))


(defun aux_mk_st (lev)
  "auuxiliar"
   (make-string (* 3 lev) :initial-element #\Space ))



(defun avl-print (tree &optional (lev 0))
  "imprime (mal) uma arvore deitada"
  (cond
   ((null tree) (format t "~& ~a --/" (aux_mk_st lev)))
   ((and (null (second tree))  (null (fifth tree)))
    (format t "~& ~a --[~a]" (aux_mk_st lev) (third tree)))
   (t 
    (progn 
      (avl-print (second tree) (1+ lev))
      (format t "~& ~a --[~a]" (aux_mk_st lev) (third tree))
      (avl-print (fifth tree) (1+ lev))
      ))
   ))