(in-package :binary-trees)

(defgeneric make-binary-tree (type &key compfun eqfun keyfun)
  (:documentation "Create a binary tree based on TYPE.  Current acceptable
values for TYPE are:

  :NORMAL - a normal binary tree, with no rebalancing
  :RED-BLACK - a red-black tree
  :AVL - an AVL tree
  :AA - an AA tree"))

(defgeneric make-binary-tree-node (tree item)
  (:documentation "Create a node appropriate for TREE containing ITEM."))

(defgeneric insert-at-node (tree item parent direction-stack)
  (:documentation "Insert ITEM underneath PARENT.  DIRECTION-STACK
indicates the path from the root of the tree to ITEM's node."))

(defgeneric tree-insert-nonempty (tree item))
(defgeneric tree-delete-nonempty (tree deleted child low-subtree))