What's an idiomatic way to implement a red-black tree in Go?

I'm new to Go and have implemented a binary search tree. The tree can store any value (specifically, anything that implements interface{}).

I'd like to build upon this implementation to create a self-balancing red-black tree. In an object-oriented language, I'd define a subclass of BinarySearchTree that adds a color data member, then override the Insert method to perform a balancing operation.

Question: How can I implement a binary search tree and red-black tree in Go without duplicating code?

Current Binary Search Tree Implementation

Here's my binary search tree implementation:

package trees
import (
"github.com/modocache/cargo/comparators"
"reflect"
)
type BinarySearchTree struct {
Parent *BinarySearchTree
Left   *BinarySearchTree
Right  *BinarySearchTree
Value  interface{}      // Can hold any value
less   comparators.Less // A comparator function to determine whether
// an inserted value is placed left or right
}
func NewBinarySearchTree(value interface{}, less comparators.Less) *BinarySearchTree {
return &BinarySearchTree{Value: value, less: less}
}
func (tree *BinarySearchTree) Insert(value interface{}) *BinarySearchTree {
if tree.less(value, tree.Value) {
return tree.insertLeft(value)
} else {
return tree.insertRight(value)
}
}
func (tree *BinarySearchTree) insertLeft(value interface{}) *BinarySearchTree {
if tree.Left == nil {
tree.Left = &BinarySearchTree{Value: value, Parent: tree, less: tree.less}
return tree.Left
} else {
return tree.Left.Insert(value)
}
}
func (tree *BinarySearchTree) insertRight(value interface{}) *BinarySearchTree {
if tree.Right == nil {
tree.Right = &BinarySearchTree{Value: value, Parent: tree, less: tree.less}
return tree.Right
} else {
return tree.Right.Insert(value)
}
}
func (tree *BinarySearchTree) Find(value interface{}) *BinarySearchTree {
if reflect.DeepEqual(value, tree.Value) {
return tree
} else if tree.less(value, tree.Value) {
return tree.findLeft(value)
} else {
return tree.findRight(value)
}
}
func (tree *BinarySearchTree) findLeft(value interface{}) *BinarySearchTree {
if tree.Left == nil {
return nil
} else {
return tree.Left.Find(value)
}
}
func (tree *BinarySearchTree) findRight(value interface{}) *BinarySearchTree {
if tree.Right == nil {
return nil
} else {
return tree.Right.Find(value)
}
}

Here's an example of how this struct may be used:

tree := NewBinarySearchTree(100, func(value, treeValue interface{}) bool {
return value.(int) < treeValue.(int)
})
tree.Insert(200)
tree.Insert(300)
tree.Insert(250)
tree.Insert(150)
tree.Insert(275)
tree.Find(250) // Returns tree.Right.Right.Left

Desired (But Impossible) Red-Black Tree Implementation

I'd like to "extend" the BinarySearchTree struct like so:

type RedBlackTree struct {
Parent *RedBlackTree     // These must be able to store
Left   *RedBlackTree     // pointers to red-black trees
Right  *RedBlackTree
Value  interface{}
less   comparators.Less
color RedBlackTreeColor  // Each tree must maintain a color property
}

And then "override" the .Insert() method like so:

func (tree *RedBlackTree) Insert(value interface{}) *RedBlackTree {
var inserted *RedBlackTree
// Insertion logic is identical to BinarySearchTree
if tree.less(value, tree.Value) {
inserted = tree.insertLeft(value)
} else {
inserted tree.insertRight(value)
}
// .balance() is a private method on RedBlackTree that balances
// the tree based on each node's color
inserted.balance()
// Returns a *RedBlackTree
return inserted
}

I don't think this is idiomatic Go code, however.

• Since BinarySearchTree is defined with pointers to other BinarySearchTree structs, a RedBlackTree that "extends" BinarySearchTree still has pointers to BinarySearchTree objects.
• There's no way to "override" .Insert(). My only option is to define another method, such as .BalancedInsert().

Currently Trying

One idea I'm currently trying is to define an interface such as this one:

type BinarySearchable interface {
Parent() *BinarySearchable
SetParent(searchable *BinarySearchable)
Left() *BinarySearchable
SetLeft(searchable *BinarySearchable)
Right() *BinarySearchable
SetRight(searchable *BinarySearchable)
Value() interface{}
Less() comparators.Less
Insert(searchable *BinarySearchable) *BinarySearchable
Find(value interface{}) *BinarySearchable
}

The BinarySearchTree and RedBlackTree will then implement these interfaces. One problem is how to share the .Insert() logic, however. Perhaps define a private function that each struct will use?

Any and all suggestions welcome.

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.

You could use embedding for example :

type A struct{}
func (a *A) fn()  { fmt.Println("A.fn") }
func (a *A) fn1() { fmt.Println("A.fn1") }
type B struct{ *A }
func (a *B) fn() { fmt.Println("B.fn") }
func main() {
b := &B{&A{}}
b.fn()
b.fn1()
}

This should override the BST's Insert but keep all the other functions:

type RedBlackTree struct {
*BinarySearchTree
color RedBlackTreeColor // This is the only new attribute
}
func (tree *RedBlackTree) Insert(value interface{}) *RedBlackTree {}

http://golang.org/doc/effective_go.html#embedding

//edit

Rereading the question you will have to change the logic a little

type RedBlackTree struct {
*BinarySearchTree
}
type rbtValue struct {
value interface{}
Color RedBlackTreeColor
}
func (tree *RedBlackTree) Insert(value interface{}) (inserted *RedBlackTree) {
if tree.less(value, tree.Value) {
inserted = tree.insertLeft(&rbt{value, Red})
} else {
inserted = tree.insertRight(&rbt{value, Black})
}
inserted.balance()
return inserted
}

Then make a comparator that works on tree.Value.(rbtValue).Value