(in-package :binary-trees) ;;; tree classes (defclass binary-tree () ((compfun :initarg :compfun :reader compfun :type function) (eqfun :initarg :eqfun :reader eqfun :type function) (keyfun :initarg :keyfun :reader keyfun :type function) (size :initform 0 :accessor tree-size :type fixnum) (root-node :initarg :root-node :accessor root-node) (sentinel-node :initarg :sentinel-node :reader sentinel-node))) (defclass avl-tree (binary-tree) ()) (defclass red-black-tree (binary-tree) ()) (defclass aa-tree (binary-tree) ()) (defclass splay-tree (binary-tree) ()) ;;; types associated with various kinds of nodes (deftype avl-balance-info () "Keywords denoting AVL tree balance conditions." '(member :left :right :equal ;; these last two are only used internally :left-unbalanced :right-unbalanced)) (deftype red-black-color () "Keywords denoting red-black tree colors." '(member :red :black)) ;;; tree nodes (defclass binary-tree-node () ((left :initarg :left :accessor left) (right :initarg :right :accessor right) (parent :initarg :parent :accessor parent) (rank :initform 1 :initarg :rank :accessor rank :type fixnum) (datum :initarg :datum :accessor datum))) (defclass avl-tree-node (binary-tree-node) ((balance-info :initform :equal :accessor balance-info :type avl-balance-info))) (defclass red-black-tree-node (binary-tree-node) ((color :initform :red :initarg :color :accessor color :type red-black-color))) (defclass aa-tree-node (binary-tree-node) ((level :initarg :level :initform 1 :accessor level :type fixnum))) (defclass splay-tree-node (binary-tree-node) ())