Golang 在红黑树中执行左旋

红黑树是一种平衡的二叉搜索树。左旋是自平衡树的基本操作之一，用于在向树中插入和删除节点时保持树的性质。本文将编写一个语言程序，使用指针和节点值来执行红黑树中的左旋操作。

红黑树的性质

每个节点要么是红色，要么是黑色
根节点始终为黑色
每个叶节点都视作黑色
如果一个节点是红色，则它的两个子节点是黑色的

步骤

第1步 - 导入main和fmt包。
第2步 - 检查输入的节点和右子节点是否已存在。如果不存在，则退出函数。
第3步 - 将节点的右子节点赋值给pivot变量。
第4步 - 现在将节点的右子节点更新为pivot的左子节点。
第5步 - 如果pivot的左子节点已经存在，则将pivot的左子节点的父节点更新为节点。
第6步 - 现在将pivot的父节点更新为节点的父节点。如果节点是根节点，则更新根引用。

示例1：使用指针和交换节点

左旋是红黑树的基本方法，用于在保持元素顺序的同时平衡树。在这种方法中，我们将使用指针操作和节点引用交换来进行左旋操作。

package main

import (
   "fmt"
)

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

var root *Node

func leftRotate(node *Node) {
   if node == nil || node.right == nil {
      return
   }

   pivot := node.right
   node.right = pivot.left

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

   pivot.parent = node.parent

   if node.parent == nil {
      // If the node was the root, update the root reference
      root = pivot
   } else if node == node.parent.left {
      node.parent.left = pivot
   } else {
      node.parent.right = pivot
   }

   pivot.left = node
   node.parent = pivot
}

func main() {
   // Sample usage of leftRotate function
   root = &Node{
      key:   15,
      color: false,
      left:  nil,
      right: nil,
   }

   node1 := &Node{
      key:   25,
      color: true,
      left:  nil,
      right: nil,
   }

   node2 := &Node{
      key:   35,
      color: true,
      left:  nil,
      right: nil,
   }

   root.right = node1
   node1.parent = root
   node1.right = node2
   node2.parent = node1

   fmt.Println("Before left rotation:")
   fmt.Println("Rootkey:", root.key)
   fmt.Println("right child key of Root :", root.right.key)
   fmt.Println(" right child key of right child key of root:", root.right.right.key)

   leftRotate(root)

   fmt.Println("\nAfter left rotation:")
   fmt.Println("Rootkey:", root.key)
   fmt.Println("left child key of Root's :", root.left.key)
}

输出

Before left rotation: 
Rootkey: 15 
right child key of Root : 25
right child key of right child key of root: 35

After left rotation:
Rootkey: 25 
left child key of Root's : 15

示例2：使用节点值

左旋是红黑树的一种基本方法，用于在维持元素顺序的同时平衡树。在这种方法中，我们将使用左旋来通过拷贝节点的值而不是直接操作指针来实现。

package main

import (
   "fmt"
)

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

var root *Node

func leftRotate(node *Node) {
   if node == nil || node.right == nil {
      return
   }

   pivot := &Node{
      key:    node.right.key,
      color:  node.right.color,
      left:   node.left,
      right:  node.right.left,
      parent: node,
   }

   if pivot.left != nil {
      pivot.left.parent = pivot
   }

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

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

   pivot.parent = node.parent
   node.parent = pivot
}

func main() {
   root = &Node{
      key:   15,
      color: false,
      left:  nil,
      right: nil,
   }

   node1 := &Node{
      key:   25,
      color: true,
      left:  nil,
      right: nil,
   }

   node2 := &Node{
      key:   35,
      color: true,
      left:  nil,
      right: nil,
   }

   root.right = node1
   node1.parent = root
   node1.right = node2
   node2.parent = node1

   fmt.Println("Before left rotation:")
   fmt.Println("Root key:", root.key)
   fmt.Println("Right child key of Root:", root.right.key)
   fmt.Println("Right child key of right child key of Root:", root.right.right.key)

   leftRotate(root)

   fmt.Println("\nAfter left rotation:")
   fmt.Println("Root key:", root.key)
}

输出

Before left rotation: 
Rootkey: 15 
right child key of Root : 25
right child key of right child key of root: 35

After left rotation:
Rootkey: 25 
left child key of Root's : 15