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 otherBinarySearchTree
structs, aRedBlackTree
that "extends"BinarySearchTree
still has pointers toBinarySearchTree
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.