Golang 定义红黑树

在Go语言中，我们可以通过提供适当的结构和方法来创建红黑树。在本文中，我们将编写Go语言程序来定义一个红黑树。在这里，根节点始终是黑色的，其他节点可以是红色或黑色，这取决于它所拥有的属性。它用于各种操作，如高效的搜索、插入和删除。

步骤

• 步骤1 - 根据需要导入fmt和“main”包

• 步骤2 - 创建一个RedBlackTree结构，其中包含一个字段，该字段提供对根节点的引用。

• 步骤3 - 然后，创建一个“Node”结构，其中包含四个字段，类型为int的值，类型为字符串的颜色，指向左右子节点的指针，以及指向父节点的指针。

• 步骤4 - 实现插入函数将节点插入到树中。

• 步骤5 - 实现fixInsert方法来修复红黑树属性的任何违规情况。

• 步骤6 - 实现getUncle和getGrandparent方法分别返回叔节点和祖父节点

• 步骤7 - 在main函数中，创建一个Red Black树的对象，并使用该对象在树中插入值

• 步骤8 - 最后，调用InorderTraversal方法按排序顺序显示值

示例

在这个示例中，我们将编写一个Go语言程序，通过使用多个插入操作来定义一个红黑树，并展示它保持颜色属性的特性，最后我们还对树执行了“Inorder遍历”。

package main

import "fmt"

type Node struct {
   value       int
   color       string
   left, right *Node
   parent      *Node
}
type RedBlackTree struct {
   root *Node
}
func NewRedBlackTree() *RedBlackTree {
   return &RedBlackTree{}
}
func (t *RedBlackTree) Insert(value int) {
   if t.root == nil {
      t.root = &Node{value: value, color: "black"}
   } else {
      t.root.insert(value)
   }
}
func (n *Node) insert(value int) {
   if value < n.value {
      if n.left == nil {
         n.left = &Node{value: value, color: "red", parent: n}
         n.left.fixInsert()
      } else {
         n.left.insert(value)
      }
   } else if value > n.value {
      if n.right == nil {
         n.right = &Node{value: value, color: "red", parent: n}
         n.right.fixInsert()
      } else {
         n.right.insert(value)
      }
   }
}
func (n *Node) fixInsert() {
   if n.parent == nil {
      n.color = "black"
      return
   }

   if n.parent.color == "black" {
      return
   }

   uncle := n.getUncle()
   grandparent := n.getGrandparent()

   if uncle != nil && uncle.color == "red" {
      n.parent.color = "black"
      uncle.color = "black"
      grandparent.color = "red"
      grandparent.fixInsert()
      return
   }

   if n == n.parent.right && n.parent == grandparent.left {
      grandparent.rotateLeft()
      n = n.left
   } else if n == n.parent.left && n.parent == grandparent.right {
      grandparent.rotateRight()
      n = n.right
   }

   n.parent.color = "black"
   grandparent.color = "red"

   if n == n.parent.left {
      grandparent.rotateRight()
   } else {
      grandparent.rotateLeft()
   }
}

func (n *Node) getUncle() *Node {
   if n.parent == nil || n.parent.parent == nil {
      return nil
   }

   grandparent := n.parent.parent
   if n.parent == grandparent.left {
      return grandparent.right
   }

   return grandparent.left
}

func (n *Node) getGrandparent() *Node {
   if n.parent != nil {
      return n.parent.parent
   }

   return nil
}

func (n *Node) rotateLeft() {
   child := n.right
   n.right = child.left

   if child.left != nil {
      child.left.parent = n
   }

   child.parent = n.parent

   if n.parent == nil {
      n.parent = child
   } else if n == n.parent.left {
      n.parent.left = child
   } else {
      n.parent.right = child
   }

   child.left = n
   n.parent = child
}

func (n *Node) rotateRight() {
   child := n.left
   n.left = child.right

   if child.right != nil {
      child.right.parent = n
   }

   child.parent = n.parent

   if n.parent == nil {
      n.parent = child
   } else if n == n.parent.left {
      n.parent.left = child
   } else {
      n.parent.right = child
   }

   child.right = n
   n.parent = child
}

func (t *RedBlackTree) InorderTraversal() {
   if t.root != nil {
      t.root.inorderTraversal()
   }
   fmt.Println()
}

func (n *Node) inorderTraversal() {
   if n != nil {
      n.left.inorderTraversal()
      fmt.Printf("%d ", n.value)
      n.right.inorderTraversal()
   }
}

func main() {
   tree := NewRedBlackTree()

   tree.Insert(7)
   tree.Insert(3)
   tree.Insert(18)
   tree.Insert(10)
   tree.Insert(22)
   tree.Insert(8)
   tree.Insert(11)
   tree.Insert(26)
   tree.Insert(2)
   tree.Insert(6)
   tree.Insert(13)

   fmt.Println("The inorder traversal of this tree is:")
   tree.InorderTraversal()
}

输出

The inorder traversal of this tree is:
6 7 8 10 11 13

结论

在本文中，我们通过使用插入的示例来检查了如何在 Go 语言中定义红黑树。在这里，我们探讨了红黑树的结构和操作。我们还使用中序遍历遍历了树。红黑树是一种自平衡的二叉搜索树，具有红色和黑色属性。