我刚开始学习Go语言,并实现了一棵二叉搜索树。该树可以存储任何值(具体而言,是实现了interface{}
接口的任何内容)。
我想在这个实现的基础上创建一个自平衡的红黑树。在面向对象的语言中,我会定义一个BinarySearchTree
的子类,添加一个color
数据成员,然后重写Insert
方法来执行平衡操作。
问题:如何在Go语言中实现二叉搜索树和红黑树而不重复编写代码?
当前的二叉搜索树实现
这是我的二叉搜索树实现:
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)
}
}
以下是这个结构体的一个使用示例:
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
期望(但不可能)的红黑树实现
我希望可以像这样“扩展”BinarySearchTree
struct
:
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
}
然后像这样“覆盖”.Insert()
方法:
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
}
我不认为这是符合惯用的Go代码。
由于BinarySearchTree是使用指向其他BinarySearchTree结构体的指针定义的,因此扩展BinarySearchTree的RedBlackTree仍然具有指向BinarySearchTree对象的指针。
没有办法“覆盖”.Insert()。我唯一的选择是定义另一个方法,例如.BalancedInsert()。
目前正在尝试的一种想法是定义一个接口,如下所示:
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
}
BinarySearchTree
和RedBlackTree
将实现这些接口。问题是如何共享.Insert()
逻辑。也许可以定义一个每个结构体都会使用的私有函数?欢迎任何建议。
.insertLeft()
设置了tree.Left = NewBinarySearchTree()
。我需要它为tree.Left = NewRedBlackTree()
,因为红黑树中的每个节点都必须维护一个颜色属性。但是,由于“Left”被定义为*BinarySearchTree
,所以我无法将其设置为*RedBlackTree
的实例。我的原始帖子包括对type RedBlackTree struct
的定义,其中包含指向*BinarySearchTree
的指针,这是不正确的。我已更新原始帖子。 - Brian Gesiak*BinarySearchTree
。在搜索互联网时,我发现了一个不使用指针嵌入的示例,即:BinarySearchTree
。这两种方式有什么区别吗? - Brian Gesiak