Define a Red-Black Tree in Golang

In go language we can create a red black tree by providing proper structures and methods. In this article we will write Go language programs to define a Red Black tree. Here, the root node is always black and other nodes can be red or black based on the properties it possess. It is used for various operations like efficient search, insertions and deletions.

Algorithm

• Step 1 ? imports fmt and "main" as necessary packages

• Step 2 ? Create a RedBlackTree struct, which contains a field that provides reference to the root node.

• Step 3 ? Then, create a "Node" struct with four fields value of type int, color of type string, pointers to left and right child nodes of type Node and pointer to parent node.

• Step 4 ? Implement insert function to insert nodes to the tree.

• Step 5 ? Implement fixInsert method to fix any violations of the Red-Black Tree's properties.

• Step 6 ? Implement getUncle and getGrandparent method returns the uncle node and grandparent node respectively

• Step 7 ? In the main function, create an object of the Red Black tree and insert values in the tree using the object

• Step 8 ? Finally, call the InorderTraversal method display the values in sorted order

Example

In this example, we will write a Go language program to define a Red Black tree by using several insertions and showing its property of maintaining the color attributes, in the end we also performed "Inorder traversal" on the tree.

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()
}

Output

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

Conclusion

In this article we have checked how we can define a redblack tree in golanguage with the help of an example that uses insertions. Here we have explored the structure and operation of a red black tree. We have also traversed the tree using inorder traversal. Red-black tree is a self-balancing Binary search tree that has colored properties like Red and Back color linked with it.