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

Question

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.

Answer 1

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.

Answer 2

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