在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

期望的(但不可能)红黑树实施

我想"延伸" 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结构的指针定义RedBlackTree,"扩展" BinarySearchTree仍然具有指向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()逻辑.也许定义每个结构将使用的私有函数？

任何和所有建议欢迎.

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

BinarySearchTree

这是嵌入其他树结构中的“基本”结构。它提供了接口方法的默认实现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)
}

RedBlackTree

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

如果有人有更惯用的设计，或者改进此设计的建议，请发布答案，我会接受。