文心一言 VS 讯飞星火 VS chatgpt （163）-- 算法导论13.1 3题

package main
import (
    "fmt"
)
const (
    RED   = true
    BLACK = false
)
type Node struct {
    color       bool
    value       int
    left, right *Node
}
func NewNode(value int) *Node {
    return &Node{value: value}
}
func (n *Node) IsRed() bool {
    return n.color == RED
}
func (n *Node) IsBlack() bool {
    return n.color == BLACK
}
// 插入和删除操作会违反性质4和5，需要额外的修复操作
// 这里只是定义了节点结构，并没有实现插入和删除的修复逻辑

在Go语言中，我们可以通过定义结构和方法来实现一个松弛红黑树。下面是一个简单的实现示例：

package main

import "fmt"

// 节点颜色常量
const (
    Red   = true
    Black = false
)

// 松弛红黑树节点结构
type Node struct {
    key         int
    color       bool  // 节点颜色
    left, right *Node // 左右子节点
}

// 创建新节点
func NewNode(key int) *Node {
    return &Node{
        key:   key,
        color: Red, // 默认为红色
    }
}

// 判断节点是否为红色
func isRed(node *Node) bool {
    if node == nil {
        return false
    }
    return node.color == Red
}

// 左旋转
func rotateLeft(node *Node) *Node {
    x := node.right
    node.right = x.left
    x.left = node
    x.color = node.color
    node.color = Red
    return x
}

// 右旋转
func rotateRight(node *Node) *Node {
    x := node.left
    node.left = x.right
    x.right = node
    x.color = node.color
    node.color = Red
    return x
}

// 颜色翻转
func flipColors(node *Node) {
    node.color = !node.color
    node.left.color = !node.left.color
    node.right.color = !node.right.color
}

// 插入节点
func insert(root *Node, key int) *Node {
    if root == nil {
        return NewNode(key)
    }

    if key < root.key {
        root.left = insert(root.left, key)
    } else if key > root.key {
        root.right = insert(root.right, key)
    }

    // 调整节点颜色和结构
    if isRed(root.right) && !isRed(root.left) {
        root = rotateLeft(root)
    }
    if isRed(root.left) && isRed(root.left.left) {
        root = rotateRight(root)
    }
    if isRed(root.left) && isRed(root.right) {
        flipColors(root)
    }

    return root
}

// 中序遍历
func inorderTraversal(node *Node) {
    if node != nil {
        inorderTraversal(node.left)
        fmt.Printf("%d ", node.key)
        inorderTraversal(node.right)
    }
}

func main() {
    // 创建一个松弛红黑树
    root := NewNode(10)
    root = insert(root, 5)
    root = insert(root, 15)
    root = insert(root, 3)
    root = insert(root, 7)
    root = insert(root, 13)
    root = insert(root, 17)

    fmt.Println("中序遍历结果:")
    inorderTraversal(root)
}

package main

import (
    "fmt"
)

type Color int

const (
    RED   Color = 0
    BLACK Color = 1
)

type Node struct {
    value       int
    color       Color
    left, right *Node
}

type RedBlackTree struct {
    root *Node
}

func NewRedBlackTree() *RedBlackTree {
    return &RedBlackTree{}
}

// 左旋转操作
func (t *RedBlackTree) leftRotate(node *Node) {
    rightChild := node.right
    node.right = rightChild.left

    if rightChild.left != nil {
        rightChild.left = node.right
    }

    if node.parent == nil {
        t.root = rightChild
    } else if node == node.parent.left {
        node.parent.left = rightChild
    } else {
        node.parent.right = rightChild
    }
    rightChild.left = node

    node.parent, rightChild.parent = rightChild, node.parent
}

// 右旋转操作
func (t *RedBlackTree) rightRotate(node *Node) {
    leftChild := node.left
    node.left = leftChild.right

    if leftChild.right != nil {
        leftChild.right.parent = node
    }

    if node.parent == nil {
        t.root = leftChild
    } else if node == node.parent.left {
        node.parent.left = leftChild
    } else {
        node.parent.right = leftChild
    }
    leftChild.right, leftChild.pare

package main

import (
    "fmt"
)

type Node struct {
    key   int
    color int // 0: black, 1: red
    left  *Node
    right *Node
}

func (n *Node) isRed() bool {
    return n.color == 1
}

func (n *Node) isBlack() bool {
    return n.color == 0
}

func (n *Node) flipColors() {
    if n.isRed() {
        n.color = 0
    } else {
        n.color = 1
    }
}

func insertNode(root *Node, key int) *Node {
    if root == nil {
        return &Node{key: key, color: 1}
    }

    if key < root.key {
        root.left = insertNode(root.left, key)
    } else {
        root.right = insertNode(root.right, key)
    }

    // 翻转颜色
    root.flipColors()

    return root
}

func main() {
    root := &Node{key: 1, color: 1} // 根节点为红色
    root = insertNode(root, 2)
    root = insertNode(root, 3)

    fmt.Println("Original Tree:")
    printTree(root, 0)

    // 将根节点颜色改为黑色
    root.color = 0

    fmt.Println("\nTree after changing root color to black:")
    printTree(root, 0)
}

func printTree(node *Node, depth int) {
    if node != nil {
        printTree(node.left, depth+1)
        for i := 0; i < depth; i++ {
            fmt.Printf("  ")
        }
        if node.color == 0 {
            fmt.Printf("%d(B)\n", node.key)
        } else {
            fmt.Printf("%d(R)\n", node.key)
        }
        printTree(node.right, depth+1)
    }
}