Red-Black Tree Implementation in Go
A Red-Black Tree is a self-balancing binary search tree in which each node contains an extra bit for denoting the color of the node, either red or black. The balancing of the tree is ensured by a set of properties that result in the tree having a height of O(log n), making operations like search, insert, and delete efficient.
Program Structure
The Go program implementing the Red-Black Tree is structured into the following components:
- Node Struct: This struct represents a node in the Red-Black Tree, containing fields for the key, color, parent, left child, and right child.
- RedBlackTree Struct: This struct represents the Red-Black Tree itself, containing the root node and a sentinel nil node (NIL) to represent leaves.
- NewRedBlackTree Function: This function initializes a new Red-Black Tree with a NIL sentinel node.
- Insert Method: This method inserts a new key into the Red-Black Tree and ensures the tree properties are maintained.
- InsertFixup Method: This helper method is called after insertion to restore the Red-Black properties if they are violated.
- LeftRotate and RightRotate Methods: These methods perform rotations on the tree to maintain balance during insertion and deletion.
Go Code Implementation
package main
import "fmt"
// Color constants for Red-Black Tree
const (
RED = true
BLACK = false
)
// Node represents a node in the Red-Black Tree
type Node struct {
key int
color bool
left *Node
right *Node
parent *Node
}
// RedBlackTree represents the Red-Black Tree structure
type RedBlackTree struct {
root *Node
NIL *Node
}
// NewRedBlackTree creates a new Red-Black Tree
func NewRedBlackTree() *RedBlackTree {
nilNode := &Node{color: BLACK}
return &RedBlackTree{
root: nilNode,
NIL: nilNode,
}
}
// Insert inserts a new key into the Red-Black Tree
func (t *RedBlackTree) Insert(key int) {
newNode := &Node{
key: key,
color: RED, // New nodes are always red initially
left: t.NIL,
right: t.NIL,
parent: nil,
}
y := t.NIL
x := t.root
for x != t.NIL {
y = x
if newNode.key < x.key {
x = x.left
} else {
x = x.right
}
}
newNode.parent = y
if y == t.NIL {
t.root = newNode
} else if newNode.key < y.key {
y.left = newNode
} else {
y.right = newNode
}
t.InsertFixup(newNode)
}
// InsertFixup restores the Red-Black Tree properties after insertion
func (t *RedBlackTree) InsertFixup(z *Node) {
for z.parent.color == RED {
if z.parent == z.parent.parent.left {
y := z.parent.parent.right
if y.color == RED {
z.parent.color = BLACK
y.color = BLACK
z.parent.parent.color = RED
z = z.parent.parent
} else {
if z == z.parent.right {
z = z.parent
t.LeftRotate(z)
}
z.parent.color = BLACK
z.parent.parent.color = RED
t.RightRotate(z.parent.parent)
}
} else {
y := z.parent.parent.left
if y.color == RED {
z.parent.color = BLACK
y.color = BLACK
z.parent.parent.color = RED
z = z.parent.parent
} else {
if z == z.parent.left {
z = z.parent
t.RightRotate(z)
}
z.parent.color = BLACK
z.parent.parent.color = RED
t.LeftRotate(z.parent.parent)
}
}
}
t.root.color = BLACK
}
// LeftRotate performs a left rotation on the node x
func (t *RedBlackTree) LeftRotate(x *Node) {
y := x.right
x.right = y.left
if y.left != t.NIL {
y.left.parent = x
}
y.parent = x.parent
if x.parent == t.NIL {
t.root = y
} else if x == x.parent.left {
x.parent.left = y
} else {
x.parent.right = y
}
y.left = x
x.parent = y
}
// RightRotate performs a right rotation on the node y
func (t *RedBlackTree) RightRotate(y *Node) {
x := y.left
y.left = x.right
if x.right != t.NIL {
x.right.parent = y
}
x.parent = y.parent
if y.parent == t.NIL {
t.root = x
} else if y == y.parent.right {
y.parent.right = x
} else {
y.parent.left = x
}
x.right = y
y.parent = x
}
// InOrderTraversal prints the tree nodes in in-order
func (t *RedBlackTree) InOrderTraversal(node *Node) {
if node != t.NIL {
t.InOrderTraversal(node.left)
fmt.Printf("%d ", node.key)
t.InOrderTraversal(node.right)
}
}
func main() {
rbt := NewRedBlackTree()
// Insert nodes into the Red-Black Tree
for _, key := range []int{20, 15, 25, 10, 5, 1, 30, 35, 40} {
rbt.Insert(key)
}
// Perform in-order traversal of the tree
fmt.Println("In-order traversal of the Red-Black Tree:")
rbt.InOrderTraversal(rbt.root)
fmt.Println()
}
Explanation of the Code
Here’s a breakdown of the code:
- Node Struct: The
Nodestruct represents each node in the Red-Black Tree. It includes the key, color (red or black), and pointers to the left, right, and parent nodes. - RedBlackTree Struct: The
RedBlackTreestruct represents the entire tree, containing the root node and a sentinel nil node (NIL) used to represent leaves. - NewRedBlackTree Function: This function initializes a new Red-Black Tree with a sentinel NIL node that is black and used as the leaf node in the tree.
- Insert Method: This method inserts a new key into the Red-Black Tree. New nodes are always inserted as red, and the tree is balanced afterward using the
InsertFixupmethod. - InsertFixup Method: This method restores the Red-Black properties after insertion by performing rotations and color changes as necessary.
- LeftRotate and RightRotate Methods: These methods perform left and right rotations, respectively, to maintain the tree’s balance. Rotations are a key part of maintaining the Red-Black Tree properties.
Usage Example
Here’s an example of how you might use this Red-Black Tree implementation in a Go program:
func main() {
rbt := NewRedBlackTree()
// Insert nodes into the Red-Black Tree
for _, key := range []int{20, 15, 25, 10, 5, 1, 30, 35, 40} {
rbt.Insert(key)
}
// Perform in-order traversal of the tree
fmt.Println("In-order traversal of the Red-Black Tree:")
rbt.InOrderTraversal(rbt.root)
fmt.Println()
}
Conclusion
This Go program demonstrates a basic implementation of a Red-Black Tree, a powerful self-balancing binary search tree that ensures O(log n) time complexity for insertion, deletion, and search operations. Red-Black Trees are widely used in database indexing, file systems, and other systems where efficient data retrieval and update operations are critical.
