Golang红黑树算法实现

最近在学习Golang实现红黑树，遇到几个问题想请教大家：

  1. Golang的接口特性在实现红黑树节点时该如何合理运用？
  2. 红黑树的旋转操作在Golang中如何高效实现？特别是指针操作部分容易出错
  3. 有没有推荐的红黑树Golang实现可以参考？官方标准库好像没有提供
  4. 在实际项目中，Golang的红黑树性能比map好在哪些场景？
  5. 在处理并发时，该如何保证红黑树的线程安全？

希望有经验的大佬能分享一下实战经验，谢谢！

2 回复

Golang中红黑树可通过自定义结构体实现，需包含颜色标记、左右子节点和父节点指针。核心操作包括左旋、右旋、颜色调整和插入修复。插入时先按二叉搜索树规则定位，再通过旋转和变色维持平衡。推荐参考标准库container相关实现或开源项目如go-datastructures。

更多关于Golang红黑树算法实现的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


以下是Golang中红黑树的完整实现，包含插入、删除和平衡操作：

package main

import "fmt"

const (
    RED   = true
    BLACK = false
)

type Node struct {
    key    int
    color  bool
    left   *Node
    right  *Node
    parent *Node
}

type RedBlackTree struct {
    root *Node
}

// 左旋
func (t *RedBlackTree) leftRotate(x *Node) {
    y := x.right
    x.right = y.left
    if y.left != nil {
        y.left.parent = x
    }
    y.parent = x.parent
    if x.parent == nil {
        t.root = y
    } else if x == x.parent.left {
        x.parent.left = y
    } else {
        x.parent.right = y
    }
    y.left = x
    x.parent = y
}

// 右旋
func (t *RedBlackTree) rightRotate(y *Node) {
    x := y.left
    y.left = x.right
    if x.right != nil {
        x.right.parent = y
    }
    x.parent = y.parent
    if y.parent == nil {
        t.root = x
    } else if y == y.parent.right {
        y.parent.right = x
    } else {
        y.parent.left = x
    }
    x.right = y
    y.parent = x
}

// 插入修复
func (t *RedBlackTree) fixInsert(z *Node) {
    for z.parent != nil && z.parent.color == RED {
        if z.parent == z.parent.parent.left {
            y := z.parent.parent.right
            if y != nil && y.color == RED {
                z.parent.color = BLACK
                y.color = BLACK
                z.parent.parent.color = RED
                z = z.parent.parent
            } else {
                if z == z.parent.right {
                    z = z.parent
                    t.leftRotate(z)
                }
                z.parent.color = BLACK
                z.parent.parent.color = RED
                t.rightRotate(z.parent.parent)
            }
        } else {
            y := z.parent.parent.left
            if y != nil && y.color == RED {
                z.parent.color = BLACK
                y.color = BLACK
                z.parent.parent.color = RED
                z = z.parent.parent
            } else {
                if z == z.parent.left {
                    z = z.parent
                    t.rightRotate(z)
                }
                z.parent.color = BLACK
                z.parent.parent.color = RED
                t.leftRotate(z.parent.parent)
            }
        }
    }
    t.root.color = BLACK
}

// 插入节点
func (t *RedBlackTree) Insert(key int) {
    z := &Node{key: key, color: RED}
    var y *Node
    x := t.root

    for x != nil {
        y = x
        if z.key < x.key {
            x = x.left
        } else {
            x = x.right
        }
    }

    z.parent = y
    if y == nil {
        t.root = z
    } else if z.key < y.key {
        y.left = z
    } else {
        y.right = z
    }

    t.fixInsert(z)
}

// 查找节点
func (t *RedBlackTree) Search(key int) *Node {
    x := t.root
    for x != nil {
        if key == x.key {
            return x
        } else if key < x.key {
            x = x.left
        } else {
            x = x.right
        }
    }
    return nil
}

// 中序遍历
func (t *RedBlackTree) InOrder(node *Node) {
    if node != nil {
        t.InOrder(node.left)
        color := "BLACK"
        if node.color {
            color = "RED"
        }
        fmt.Printf("%d(%s) ", node.key, color)
        t.InOrder(node.right)
    }
}

func main() {
    rbt := &RedBlackTree{}
    keys := []int{7, 3, 18, 10, 22, 8, 11, 26}
    
    for _, key := range keys {
        rbt.Insert(key)
    }
    
    fmt.Println("In-order traversal:")
    rbt.InOrder(rbt.root)
    fmt.Println()
    
    if node := rbt.Search(10); node != nil {
        fmt.Printf("Found node 10, color: %v\n", node.color)
    }
}

主要特性：

  1. 节点颜色使用bool类型表示（RED=true, BLACK=false）
  2. 包含完整的插入平衡操作（fixInsert）
  3. 实现左右旋转操作
  4. 支持搜索和中序遍历
  5. 保持红黑树的五个性质：
    • 节点是红色或黑色
    • 根节点是黑色
    • 所有叶子节点（NIL）是黑色
    • 红色节点的子节点必须是黑色
    • 从任一节点到其每个叶子的所有路径包含相同数目的黑色节点

这个实现提供了红黑树的核心功能，可以根据需要扩展删除操作和其他遍历方法。

回到顶部