This is what I came up with. I'd rather accept another answer, but this is the best so far.
The BinarySearchable
Interface
Both BinarySearchTree
and RedBlackTree
conform to this interface. The file also defines functions common to all binary-searchable structs, including insert()
, .find()
, leftRotate()
, and so on.
In order to dynamically create objects of various types, the insert()
function takes a childConstructor
function parameter. This function is used by BinarySearchTree
and RedBlackTree
to create child trees of arbitrary types.
// binary_searchable.go
type BinarySearchable interface {
Parent() BinarySearchable
SetParent(searchable BinarySearchable)
Left() BinarySearchable
SetLeft(searchable BinarySearchable)
Right() BinarySearchable
SetRight(searchable BinarySearchable)
Value() interface{}
Insert(value interface{}) BinarySearchable
Find(value interface{}) BinarySearchable
Less() comparators.Less
}
type childConstructor func(parent BinarySearchable, value interface{}) BinarySearchable
func insert(searchable BinarySearchable, value interface{}, constructor childConstructor) BinarySearchable {
if searchable.Less()(value, searchable.Value()) {
if searchable.Left() == nil {
// The constructor function is used to
// create children of dynamic types
searchable.SetLeft(constructor(searchable, value))
return searchable.Left()
} else {
return searchable.Left().Insert(value)
}
} else {
if searchable.Right() == nil {
searchable.SetRight(constructor(searchable, value))
return searchable.Right()
} else {
return searchable.Right().Insert(value)
}
}
}
BinarySearchTree
This is the "base" struct that is embedded in other tree structs. It provides default implementations of the BinarySearchable
interface methods, as well as the data attributes each tree will use to store their children.
// binary_search_tree.go
type BinarySearchTree struct {
parent BinarySearchable
left BinarySearchable
right BinarySearchable
value interface{}
less comparators.Less
}
func (tree *BinarySearchTree) Parent() BinarySearchable {
return tree.parent
}
func (tree *BinarySearchTree) SetParent(parent BinarySearchable) {
tree.parent = parent
}
// ...setters and getters for left, right, value, less, etc.
func (tree *BinarySearchTree) Insert(value interface{}) BinarySearchable {
// Pass `insert()` a constructor that creates a `*BinarySearchTree`
constructor := func(parent BinarySearchable, value interface{}) BinarySearchable {
return &BinarySearchTree{value: value, less: tree.less, parent: parent}
}
return insert(tree, value, constructor).(*BinarySearchTree)
}
func (tree *BinarySearchTree) Find(value interface{}) BinarySearchable {
return find(tree, value)
}
RedBlackTree
This embeds BinarySearchTree
and passes a custom constructor to insert()
. The balancing code is omitted for brevity; you can see the whole file here.
// red_black_tree.go
type RedBlackTree struct {
*BinarySearchTree
color RedBlackTreeColor
}
func NewRedBlackTree(value interface{}, less comparators.Less) *RedBlackTree {
return &RedBlackTree{&BinarySearchTree{value: value, less: less}, Black}
}
func (tree *RedBlackTree) Insert(value interface{}) BinarySearchable {
constructor := func(parent BinarySearchable, value interface{}) BinarySearchable {
return &RedBlackTree{&BinarySearchTree{value: value, less: tree.less, parent: parent}, Red}
}
inserted := insert(tree, value, constructor).(*RedBlackTree)
inserted.balance()
return inserted
}
func (tree *RedBlackTree) balance() {
// ...omitted for brevity
}
If anyone has a more idiomatic design, or suggestions to improve this design, please post an answer and I will accept it.