Golang 搜索红黑树中的节点的程序

在红黑树中搜索节点是为了找到具有特定键或值的节点。在红黑树中进行搜索类似于在标准二叉树中进行搜索。在本文中，我们将编写Go语言程序来在红黑树中搜索节点。它是一种自平衡的二叉搜索树，具有根节点始终为黑色，其他节点按照属性为红色或黑色的特性。该树使用旋转来在插入和删除时保持平衡。

属性

每个节点要么是红色或黑色
根节点始终为黑色
所有叶子节点都是黑色的
如果一个节点是红色的，那么它的两个子节点都是黑色的
从一个节点到其子孙叶节点的每条路径都包含相同数量的黑色节点

语法

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

创建一棵红黑树。

func (t *RedBlackTree) Insert(data int) { // ... }

向树中插入包含数据的新节点。

func (t *RedBlackTree) leftRotate(node *Node) { // ... }

对树进行左旋操作。

func (t *RedBlackTree) Search(key int) *Node { // ... }

搜索具有特定键值的节点。

步骤

导入所需的包
创建一个常量，类型为”Colour”，值为”Red”和”Black”分别赋值为0和1。
定义数据结构：创建一个名为”RedBlackTree”的结构体，有一个指向根节点的字段”root”。
创建一个名为”NewRedBlackTree”的函数，创建并返回一个新的红黑树实例。

示例1

在下面的示例中，使用一个结构体定义了一个红黑树，包括一个根节点。下面的代码展示了红黑树的构造、插入和搜索操作，突出了数据结构的自平衡特性和快速搜索能力。

package main

import "fmt"

type Color int

const (
   Red   Color = 0
   Black Color = 1
)

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

type RedBlackTree struct {
   root *Node
}

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

func (t *RedBlackTree) Insert(data int) {
   newNode := &Node{data: data, color: Red}
   t.insertNode(newNode)

   t.fixInsertion(newNode)
}

func (t *RedBlackTree) insertNode(newNode *Node) {
   if t.root == nil {
      t.root = newNode
      return
   }

   current := t.root
   var parent *Node
   for current != nil {
      parent = current
      if newNode.data < current.data {
         current = current.left
      } else if newNode.data > current.data {
         current = current.right
      } else {

         return
      }
   }

   newNode.parent = parent
   if newNode.data < parent.data {
      parent.left = newNode
   } else {
      parent.right = newNode
   }
}

func (t *RedBlackTree) fixInsertion(node *Node) {
   for node.parent != nil && node.parent.color == Red {
      if node.parent == node.parent.parent.left {
         uncle := node.parent.parent.right

         if uncle != nil && uncle.color == Red {
            node.parent.color = Black
            uncle.color = Black
            node.parent.parent.color = Red
            node = node.parent.parent
         } else {
            if node == node.parent.right {
               node = node.parent
               t.leftRotate(node)
            }

            node.parent.color = Black
            node.parent.parent.color = Red
            t.rightRotate(node.parent.parent)
         }
      } else {
         uncle := node.parent.parent.left

         if uncle != nil && uncle.color == Red {
            node.parent.color = Black
            uncle.color = Black
            node.parent.parent.color = Red
            node = node.parent.parent
         } else {
            if node == node.parent.left {
               node = node.parent
               t.rightRotate(node)
            }

            node.parent.color = Black
            node.parent.parent.color = Red
            t.leftRotate(node.parent.parent)
         }
      }
   }

   t.root.color = Black
}

func (t *RedBlackTree) leftRotate(node *Node) {
   rightChild := node.right
   node.right = rightChild.left

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

   rightChild.parent = node.parent

   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
}

func (t *RedBlackTree) rightRotate(node *Node) {
   leftChild := node.left
   node.left = leftChild.right

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

   leftChild.parent = node.parent

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

   leftChild.right = node
   node.parent = leftChild
}

func (t *RedBlackTree) Search(key int) *Node {
   current := t.root
   for current != nil {
      if key == current.data {
         return current
      } else if key < current.data {
         current = current.left
      } else {
         current = current.right
      }
   }
   return nil
}

func main() {
   tree := NewRedBlackTree()

   tree.Insert(60)
   tree.Insert(40)
   tree.Insert(20)
   tree.Insert(40)
   tree.Insert(30)

   search_key := 40
   result := tree.Search(search_key)
   if result != nil {
      fmt.Printf("Node with value %d found\n", search_key)
   } else {
      fmt.Printf("Node with value %d not found\n", search_key)
   }
}