;; tree = (left middle right)

(defun trotate-r (tree)
  " roda uma arvore para a direita"
  (let* ((l (first tree))
	 (m (second tree))
	 (r (third tree))
	 (a (first l))
	 (b (second l))
	 (c (third l))
	 )
    (list a b (list c m r))
  ))


(defun trotate-l (tree)
  "roda uma arvore para a esquerda"
  (destructuring-bind (l m (a b c)) tree
    (list (list l m a) b c)))


(defun tinsert (tree dado)
"insere um dado numa arvore, retorna a arvore nova"
  (if (null tree) (list nil dado nil)
    (let* ((l (first tree))
	   (m (second tree))
	   (r (third tree)))
      (cond
       ((= dado m) tree)
       ((< dado m) (list (tinsert l dado) m r))
       (t (list l m (tinsert r dado))))
      )))


(defun tdelete (tree dado)
  "remove um dado da arvore, retorna a arvore nova"
  (if (null tree) nil
    (let* ((l (first tree))
	   (m (second tree))
	   (r (third tree)))
      (cond 
       ((and (= m dado) (null l)) r)
       ((and (= m dado) (null r)) l)
       ((= m dado) (tdelete (trotate-r tree) dado))
       ((< m dado) (list l m (tdelete r dado)))
       ((> m dado) (list (tdelete l dado) m r))
       ))
    ))


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



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