go - 在 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 结构的指针定义的，因此“扩展”BinarySearchTree 的 RedBlackTree 仍然有指向 BinarySearchTree 对象的指针。
• 无法“覆盖”.Insert()。我唯一的选择是定义另一种方法，例如 .BalancedInsert()。

正在尝试

我目前正在尝试的一个想法是定义一个这样的接口(interface):

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 将实现这些接口(interface)。然而，一个问题是如何共享 .Insert() 逻辑。也许定义每个结构将使用的私有(private)函数？

欢迎提出任何建议。

Answer 1

这是我想出来的。我宁愿接受另一个答案，但这是迄今为止最好的答案。

BinarySearchable 接口(interface)

BinarySearchTree 和RedBlackTree 都符合这个接口(interface)。该文件还定义了所有二进制可搜索结构共有的函数，包括 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 接口(interface)方法的默认实现，以及每棵树将用于存储其子树的数据属性。

// 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()。为简洁起见，省略了平衡代码；你可以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
}

如果有人有更地道的设计，或改进此设计的建议，请发表答案，我会采纳。