AVL Tree Implementation in Kotlin

1. Introduction

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

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if they differ by more than one at any time, rebalancing is done to restore this property. AVL trees are named after their inventors, Adelson-Velsky and Landis. Due to their balancing property, they guarantee O(log n) time complexity for insert, delete, and search operations.

2. Implementation Steps

1. Define a Node class to represent individual nodes in the AVL tree, containing information about data, height, and left/right children.

2. Create an AVLTree class that will provide methods for common operations.

3. Implement rotation methods (leftRotate, rightRotate, leftRightRotate, rightLeftRotate) to maintain the AVL tree balance.

4. Implement methods such as insert, delete, search, findMin, findMax, and tree traversal methods.

3. Implementation in Kotlin Programming

class Node(var key: Int) {
    var height: Int = 1
    var left: Node? = null
    var right: Node? = null
}

class AVLTree {
    private fun height(node: Node?): Int {
        return node?.height ?: 0
    }
    
    private fun updateHeight(node: Node) {
        node.height = 1 + maxOf(height(node.left), height(node.right))
    }
    
    private fun balanceFactor(node: Node?): Int {
        return height(node?.left) - height(node?.right)
    }
    
    private fun leftRotate(x: Node): Node {
        val y = x.right!!
        val T2 = y.left
        y.left = x
        x.right = T2
        updateHeight(x)
        updateHeight(y)
        return y
    }
    
    private fun rightRotate(y: Node): Node {
        val x = y.left!!
        val T2 = x.right
        x.right = y
        y.left = T2
        updateHeight(y)
        updateHeight(x)
        return x
    }
    
    fun insert(root: Node?, key: Int): Node {
        if (root == null) return Node(key)
        if (key < root.key) root.left = insert(root.left, key)
        else if (key > root.key) root.right = insert(root.right, key)
        else return root
        updateHeight(root)
        val balance = balanceFactor(root)
        if (balance > 1) {
            if (key < root.left!!.key) {
                return rightRotate(root)
            } else {
                root.left = leftRotate(root.left!!)
                return rightRotate(root)
            }
        }
        if (balance < -1) {
            if (key > root.right!!.key) {
                return leftRotate(root)
            } else {
                root.right = rightRotate(root.right!!)
                return leftRotate(root)
            }
        }
        return root
    }
    
    fun delete(root: Node?, key: Int): Node? {
        if (root == null) return root
        if (key < root.key) {
            root.left = delete(root.left, key)
        } else if (key > root.key) {
            root.right = delete(root.right, key)
        } else {
            if (root.left == null || root.right == null) {
                var temp: Node? = null
                temp = root.left ?: root.right
                if (temp == null) {
                    temp = root
                    root = null
                } else {
                    root = temp
                }
            } else {
                val temp = minValueNode(root.right!!)
                root.key = temp.key
                root.right = delete(root.right, temp.key)
            }
        }
        if (root == null) return root
        updateHeight(root)
        val balance = balanceFactor(root)
        if (balance > 1) {
            if (balanceFactor(root.left) >= 0) {
                return rightRotate(root)
            } else {
                root.left = leftRotate(root.left!!)
                return rightRotate(root)
            }
        }
        if (balance < -1) {
            if (balanceFactor(root.right) <= 0) {
                return leftRotate(root)
            } else {
                root.right = rightRotate(root.right!!)
                return leftRotate(root)
            }
        }
        return root
    }
    
    private fun minValueNode(node: Node): Node {
        var current = node
        while (current.left != null) current = current.left!!
        return current
    }
    
    fun preOrder(root: Node?) {
        if (root != null) {
            println(root.key)
            preOrder(root.left)
            preOrder(root.right)
        }
    }
}

// client code to test AVL Tree Implementation in Kotlin
fun main() {
    var tree: Node? = null
    val avlTree = AVLTree()
    tree = avlTree.insert(tree, 10)
    tree = avlTree.insert(tree, 20)
    tree = avlTree.insert(tree, 30)
    tree = avlTree.insert(tree, 40)
    tree = avlTree.insert(tree, 50)
    tree = avlTree.insert(tree, 25)
    println("Preorder traversal of constructed AVL tree:")
    avlTree.preOrder(tree)
    tree = avlTree.delete(tree, 10)
    println("\nPreorder traversal after deleting 10:")
    avlTree.preOrder(tree)
}

Output:

Preorder traversal of constructed AVL tree:
30
20
10
25
40
50
Preorder traversal after deleting 10:
30
25
20
40
50

Explanation:

1. An AVL Tree is a self-balancing Binary Search Tree. The key property is that the balance factor (difference in height between left and right subtrees) of any node is either -1, 0, or 1.

2. Each Node contains data (key), height, and references to left and right children.

3. The AVLTree class contains several utility functions:

- height to get the height of a node.

- updateHeight to update the height of a node.

- balanceFactor to compute the balance factor of a node.

- Rotation methods (leftRotate, rightRotate, leftRightRotate, rightLeftRotate) to handle imbalances.

4. insert and delete methods recursively maintain the AVL property after insertion or deletion.

5. The main function demonstrates insertion and deletion operations and their effects on tree balance.