Go语言怎么做红黑树_Go语言红黑树实现教程【推荐】-Golang-PHP中文网

gods的put方法默认设新节点为红色，因仅可能违反红节点子节点须为黑的性质，不破坏黑高平衡；插黑色会直接增加所有路径黑高，修复成本更高。

go语言怎么做红黑树_go语言红黑树实现教程【推荐】

GoDS 的 `Put` 方法为什么默认把新节点设成红色？

因为红色插入对红黑树性质的破坏最小——只可能违反“红色节点子节点必须为黑色”这一条，而不会立刻破坏黑高平衡（即从任一节点到叶子路径的黑色节点数一致）。如果插黑色，会直接导致所有经过该节点的路径黑高 +1，修复成本远高于后续局部变色+旋转。

所有标准实现（包括 GoDS、gods 库、自研版本）都遵循这个约定：Put 创建节点时强制 node.color = RED
例外只出现在根节点：若树为空，Put 后立即调用 insertCase1 把它改成黑色，否则不满足“根必黑”
别手动改颜色再调 Put——Put 内部已封装完整流程，外部干预反而会跳过平衡逻辑

插入后没平衡？检查是否漏了 `insertCase1` 到 `insertCase5` 的链式调用

GoDS 的 Put 不是插完就结束，它在创建红色节点后，会按顺序触发 insertCase1 → insertCase2 …… 直到某 case 无需继续向上修复。常见问题是你自己实现时只写了 case3 或 case5，但没处理 case1（根节点染黑）或 case4（叔父红→祖父变红、父叔变黑，再递归检查祖父）。

insertCase1：仅当 node.parent == nil 时触发，必须把 node.color = BLACK，否则整棵树非法
insertCase4 是关键中转站：父红+叔红→父/叔变黑、祖父变红，然后把当前节点指针上移到祖父，继续调 insertCase1
case5（直线型双红）必须配合旋转：左左/右右情况用 rotateRight/rotateLeft，且旋转后要交换父与祖父的颜色，不是单纯转完就完事

用 `gods` 库时，`NewWithIntComparator` 和自定义 comparator 的区别在哪？

前者开箱即用，后者决定你能否正确排序复合结构（比如内网日志里的 UserID+Timestamp）。NewWithIntComparator 只能比 int，一旦你存的是 struct{Time int; User string}，不写 comparator 就会 panic 或插入错位。

Go语言（Golang）1.26.0

Go语言（Golang）1.26.0版本官方下载，版本号 1.26.0，适合旧项目维护、兼容性测试和指定版本开发环境搭建。

下载

错误现象：tree.Put(123, log) 表面成功，但 tree.InOrder() 遍历顺序乱，或 tree.Get(123) 返回 nil
正确写法：用 gods.Trees 提供的 Comparator 函数，例如按时间戳升序：
```
func(a, b interface{}) int { return a.(LogEntry).Time - b.(LogEntry).Time }
```
性能影响：comparator 调用频次 = 树高，O(log n)，只要别在里面做 IO 或复杂计算，完全可接受

为什么本地测试平衡了，压测时却出现 `panic: runtime error: invalid memory address`？

大概率是并发写没加锁。GoDS 的 redblacktree 不是线程安全的——Put 过程中会修改 parent、left、right 指针，多个 goroutine 同时插入可能让某个节点的 parent 指向已释放内存，或者旋转时左右子树被不同协程同时修改。

别用 sync.Mutex 包一层就以为万事大吉：锁粒度太粗会严重拖慢吞吐；锁太细（比如只锁单个节点）又难保证旋转原子性
生产环境更推荐：用 gods/concurrent 下的线程安全包装器，或直接切到 go.etcd.io/bbolt 这类支持 MVCC 的嵌入式 KV，红黑树更适合单协程高频操作场景
调试技巧：加 go build -race 编译，跑压测时 race detector 会精准报出哪两行代码竞争了哪个字段

红黑树的平衡逻辑不是靠一次旋转“搞定”，而是 case 之间层层传递、向上修复的过程。最容易被忽略的，是 case4 后必须把当前节点指针设为祖父并重新进入 case1——很多人在这里直接 return，导致祖父变红后没人管，整条路径黑高失衡。