如何用Go语言实现红黑树的惯用方法？

Question

我刚开始学习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

期望（但不可能）的红黑树实现

我希望可以像这样“扩展”BinarySearchTreestruct：

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()逻辑。也许可以定义一个每个结构体都会使用的私有函数？

欢迎任何建议。

- Brian Gesiak

Answer 1

这是我想到的方案。我更愿意接受其他答案，但这个是目前最好的。

BinarySearchable 接口

BinarySearchTree 和 RedBlackTree 都符合这个接口。该文件还定义了所有二分搜索结构共有的函数，包括 insert()、.find()、leftRotate() 等等。

为了动态创建各种类型的对象，insert() 函数带有一个 childConstructor 函数参数。这个函数被 BinarySearchTree 和 RedBlackTree 用来创建任意类型的子树。

// 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)
        }
    }
}

二叉搜索树

这是嵌入其他树结构的“基础”结构。它提供了BinarySearchable接口方法的默认实现，以及每个树将用于存储其子节点的数据属性。

// 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)
}

红黑树

这里嵌入了 二叉搜索树（BinarySearchTree），并向 insert() 方法传递一个自定义构造函数。为了简洁起见，平衡代码被省略掉了；您可以 在此处查看整个文件。

// 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
}

如果有更符合习惯用语的设计或者改进建议，请回答并且我会采纳。

- Brian Gesiak

Answer 2

你可以使用嵌入来实现示例：

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()
}

这应该覆盖BST的Insert函数，但保留所有其他功能。

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

//编辑

重新阅读问题，您需要稍微改变一下逻辑。

（Translated from Chinese）

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
}

然后创建一个比较器，使其能够对 tree.Value.(rbtValue).Value 进行操作。

- OneOfOne

---

我认为这个不起作用。我知道Go中的嵌入，但问题是.insertLeft()设置了 tree.Left = NewBinarySearchTree()。我需要它为tree.Left = NewRedBlackTree()，因为红黑树中的每个节点都必须维护一个颜色属性。但是，由于“Left”被定义为*BinarySearchTree，所以我无法将其设置为*RedBlackTree的实例。我的原始帖子包括对type RedBlackTree struct 的定义，其中包含指向*BinarySearchTree的指针，这是不正确的。我已更新原始帖子。 - Brian Gesiak

我意识到在看到回答后，检查了编辑，然而你的回答是正确的方式。 - OneOfOne

谢谢你的回答，它帮助我找到了正确的方向。顺便问一下，我想知道：你是使用指针嵌入的，即：*BinarySearchTree。在搜索互联网时，我发现了一个不使用指针嵌入的示例，即：BinarySearchTree。这两种方式有什么区别吗？ - Brian Gesiak

好吧，我使用指针来避免副本，这是一个不好的习惯，除非它是本地类型或者一个非常简单的结构体。 - OneOfOne