# 1. Introduction

In this tutorial, we will learn how to implement a simple Red-Black Tree structure using Kotlin programming language.

A Red-Black Tree is a self-balancing binary search tree where each node has an extra bit for denoting the color of the node, either red or black.

A Red-Black Tree satisfies the following properties:

1. Every node is either red or black.

2. The root is black.

3. All leaves (NIL nodes) are black.

4. If a red node has a child, the child is always black.

5. Every path from a node to its descendant NIL nodes contains the same number of black nodes.

These properties ensure that the tree remains approximately balanced, resulting in O(log n) time for most of its operations.

# 2. Implementation Steps

1. Define a Node class to represent individual nodes in the Red-Black Tree, containing the data, color, parent, left child, and right child.

2. Implement rotation methods (leftRotate and rightRotate) to maintain the Red-Black Tree properties.

3. Implement the insert and delete methods which will handle the tree's self-balancing.

4. Provide methods for tree traversal and other common operations.

# 3. Implementation in Kotlin Programming

``````enum class Color {
RED, BLACK
}

class Node(var key: Int, var color: Color, var parent: Node? = null) {
var left: Node? = null
var right: Node? = null
}

class RedBlackTree {
private var root: Node? = null

private fun leftRotate(x: Node) {
val y = x.right!!
x.right = y.left
if (y.left != null) {
y.left!!.parent = x
}
y.parent = x.parent
if (x.parent == null) {
root = y
} else if (x == x.parent!!.left) {
x.parent!!.left = y
} else {
x.parent!!.right = y
}
y.left = x
x.parent = y
}

private fun rightRotate(y: Node) {
val x = y.left!!
y.left = x.right
if (x.right != null) {
x.right!!.parent = y
}
x.parent = y.parent
if (y.parent == null) {
root = x
} else if (y == y.parent!!.right) {
y.parent!!.right = x
} else {
y.parent!!.left = x
}
x.right = y
y.parent = x
}

fun insert(key: Int) {
var z = Node(key, Color.RED)
var y: Node? = null
var x = root
while (x != null) {
y = x
if (z.key < x.key) {
x = x.left
} else {
x = x.right
}
}
z.parent = y
if (y == null) {
root = z
} else if (z.key < y.key) {
y.left = z
} else {
y.right = z
}
if (z.parent == null) {
z.color = Color.BLACK
return
}
if (z.parent!!.parent == null) {
return
}
fixViolations(z)
}

private fun fixViolations(z: Node) {
var z = z
while (z.parent != null && z.parent!!.color == Color.RED) {
var y: Node? = null
if (z.parent == z.parent!!.parent!!.left) {
y = z.parent!!.parent!!.right
if (y != null && y.color == Color.RED) {
z.parent!!.color = Color.BLACK
y.color = Color.BLACK
z.parent!!.parent!!.color = Color.RED
z = z.parent!!.parent!!
} else {
if (z == z.parent!!.right) {
z = z.parent!!
leftRotate(z)
}
z.parent!!.color = Color.BLACK
z.parent!!.parent!!.color = Color.RED
rightRotate(z.parent!!.parent!!)
}
} else {
y = z.parent!!.parent!!.left
if (y != null && y.color == Color.RED) {
z.parent!!.color = Color.BLACK
y.color = Color.BLACK
z.parent!!.parent!!.color = Color.RED
z = z.parent!!.parent!!
} else {
if (z == z.parent!!.left) {
z = z.parent!!
rightRotate(z)
}
z.parent!!.color = Color.BLACK
z.parent!!.parent!!.color = Color.RED
leftRotate(z.parent!!.parent!!)
}
}
}
root!!.color = Color.BLACK
}

fun inorder() = inorderHelper(root)
private fun inorderHelper(root: Node?) {
if (root == null) return
inorderHelper(root.left)
println("\${root.key} - \${root.color}")
inorderHelper(root.right)
}
}

// client code to test Red-Black Tree Implementation in Kotlin
fun main() {
val tree = RedBlackTree()
tree.insert(7)
tree.insert(6)
tree.insert(5)
tree.insert(4)
tree.insert(3)
tree.insert(2)
tree.insert(1)
tree.inorder()
}
``````

### Output:

```1 - BLACK
2 - RED
3 - BLACK
4 - RED
5 - BLACK
6 - RED
7 - BLACK
```

### Explanation:

1. A Red-Black Tree ensures that the tree remains balanced after every insertion and deletion operation.

2. Each Node contains a key, color, and references to parent, left, and right child.

3. The tree class (RedBlackTree) provides utility functions:

- Rotation methods (leftRotate and rightRotate) to help in re-balancing.

- fixViolations method ensures that the Red-Black Tree properties are maintained after each insertion.

4. insert is a recursive function that places the new node in the correct position and then uses fixViolations to correct any color imbalances.

5. The inorder function is used for in-order traversal to display the tree's nodes.

6. The main function demonstrates the insertion of several nodes and then displays them using in-order traversal.