AVL Tree Implementation in C#

1. Introduction

An AVL Tree is a type of binary search tree that self-balances to maintain an approximately logarithmic height. Named after its inventors, Adelson-Velsky and Landis, the AVL tree ensures that the heights of the two child subtrees for any node differ by at most one. This balancing ensures efficient performance for operations like insertion, deletion, and lookup.

2. Implementation Steps

1. Define a Node class to represent individual items in the AVL tree. Each node will have attributes: Value, Height, Left, and Right.

2. Create an AVLTree class to manage the nodes and operations.

3. Implement basic operations:

- Insert: Add a node and ensure the tree remains balanced.

- Delete: Remove a node and balance the tree.

4. Implement balancing methods:

- RotateRight: Perform right rotation.

- RotateLeft: Perform left rotation.

- GetBalanceFactor: Calculate the difference in heights between left and right subtrees.

5. Test the AVL Tree with various operations.

3. Implementation in C#

using System;
public class Node {
    public int Value;
    public int Height;
    public Node Left;
    public Node Right;
    public Node(int value) {
        Value = value;
        Height = 1;
        Left = null;
        Right = null;
    }
}
public class AVLTree {
    public Node Root;
    public Node Insert(Node node, int value) {
        if (node == null) {
            return new Node(value);
        }
        if (value < node.Value) {
            node.Left = Insert(node.Left, value);
        } else if (value > node.Value) {
            node.Right = Insert(node.Right, value);
        } else {
            return node;  // Duplicate values not allowed
        }
        // Update height of the current node
        node.Height = 1 + Math.Max(GetHeight(node.Left), GetHeight(node.Right));
        // Balance the tree
        int balanceFactor = GetBalanceFactor(node);
        // Left Heavy
        if (balanceFactor > 1) {
            if (value < node.Left.Value) {
                return RotateRight(node);
            } else {
                node.Left = RotateLeft(node.Left);
                return RotateRight(node);
            }
        }
        // Right Heavy
        if (balanceFactor < -1) {
            if (value > node.Right.Value) {
                return RotateLeft(node);
            } else {
                node.Right = RotateRight(node.Right);
                return RotateLeft(node);
            }
        }
        return node;
    }
    private int GetHeight(Node node) {
        if (node == null) return 0;
        return node.Height;
    }
    private int GetBalanceFactor(Node node) {
        if (node == null) return 0;
        return GetHeight(node.Left) - GetHeight(node.Right);
    }
    private Node RotateRight(Node y) {
        Node x = y.Left;
        Node T3 = x.Right;
        x.Right = y;
        y.Left = T3;
        y.Height = 1 + Math.Max(GetHeight(y.Left), GetHeight(y.Right));
        x.Height = 1 + Math.Max(GetHeight(x.Left), GetHeight(x.Right));
        return x;
    }
    private Node RotateLeft(Node x) {
        Node y = x.Right;
        Node T2 = y.Left;
        y.Left = x;
        x.Right = T2;
        x.Height = 1 + Math.Max(GetHeight(x.Left), GetHeight(x.Right));
        y.Height = 1 + Math.Max(GetHeight(y.Left), GetHeight(y.Right));
        return y;
    }
    public void Display(Node root) {
        if (root != null) {
            Display(root.Left);
            Console.WriteLine(root.Value);
            Display(root.Right);
        }
    }
}
public class Program {
    public static void Main() {
        AVLTree tree = new AVLTree();
        Node root = null;
        root = tree.Insert(root, 30);
        root = tree.Insert(root, 20);
        root = tree.Insert(root, 40);
        root = tree.Insert(root, 50);
        tree.Display(root);  // Should print: 20 30 40 50
    }
}

Output:

20
30
40
50

Explanation:

1. The Node class represents each node in the AVL tree. It holds a Value, Height, and references to Left and Right child nodes.

2. The AVLTree class manages tree operations. Nodes are inserted with balance in mind, ensuring the AVL property is maintained.

3. The Insert method adds nodes, updating the height of each node on the way up and checking the balance factor.

4. Depending on the balance factor, rotations are performed to balance the tree. There are four possible scenarios: left-left, left-right, right-left, and right-right. Each scenario requires either one or two rotations.

5. The RotateRight and RotateLeft methods implement rotations.

6. The GetBalanceFactor method calculates the difference in heights between the left and right child