AVL Tree Implementation in Swift

1. Introduction

An AVL Tree is a self-balancing binary search tree. In an AVL Tree, the height difference (or balance factor) between the left and right subtrees of any node is no more than one, ensuring that the tree remains approximately balanced. As a result, the tree maintains logarithmic height, ensuring fast operations like insertion, deletion, and look-up.

2. Implementation Steps

1. Define a Node class with additional attributes for height and balance factor.

2. Define an AVLTree class that will manage the nodes.

3. Implement rotation methods: left, right, left-right, and right-left rotations to maintain balance.

4. Implement the insert method, ensuring that the tree remains balanced after each insertion.

3. Implementation in Swift

// 1. Definition of the Node class
class AVLNode<T: Comparable> {
    var value: T
    var left: AVLNode?
    var right: AVLNode?
    var height: Int
    init(value: T) {
        self.value = value
        self.height = 1  // New node is a leaf node with height 1
    }
}
// 2. Definition of the AVLTree class
class AVLTree<T: Comparable> {
    var root: AVLNode<T>?
    // Helper function to get the height of a node
    private func height(_ node: AVLNode<T>?) -> Int {
        return node?.height ?? 0
    }
    // Helper function to get the balance factor of a node
    private func getBalance(_ node: AVLNode<T>?) -> Int {
        return height(node?.left) - height(node?.right)
    }
    // 3. Implementing rotations
    // Right rotation
    private func rightRotate(_ y: AVLNode<T>) -> AVLNode<T> {
        let x = y.left!
        let T3 = x.right
        x.right = y
        y.left = T3
        y.height = max(height(y.left), height(y.right)) + 1
        x.height = max(height(x.left), height(x.right)) + 1
        return x
    }
    // Left rotation
    private func leftRotate(_ x: AVLNode<T>) -> AVLNode<T> {
        let y = x.right!
        let T2 = y.left
        y.left = x
        x.right = T2
        x.height = max(height(x.left), height(x.right)) + 1
        y.height = max(height(y.left), height(y.right)) + 1
        return y
    }
    // 4. Insert method
    func insert(value: T) {
        root = insert(node: root, value: value)
    }
    private func insert(node: AVLNode<T>?, value: T) -> AVLNode<T> {
        if node == nil {
            return AVLNode(value: value)
        }
        if value < node!.value {
            node!.left = insert(node: node!.left, value: value)
        } else if value > node!.value {
            node!.right = insert(node: node!.right, value: value)
        } else {
            return node!  // Duplicates are not allowed
        }
        node!.height = 1 + max(height(node!.left), height(node!.right))
        let balance = getBalance(node)
        // Left heavy
        if balance > 1 {
            if value < node!.left!.value {
                return rightRotate(node!)
            } else {
                node!.left = leftRotate(node!.left!)
                return rightRotate(node!)
            }
        }
        // Right heavy
        if balance < -1 {
            if value > node!.right!.value {
                return leftRotate(node!)
            } else {
                node!.right = rightRotate(node!.right!)
                return leftRotate(node!)
            }
        }
        return node!
    }
}
// Example Usage
let avlTree = AVLTree<Int>()
avlTree.insert(value: 10)
avlTree.insert(value: 20)
avlTree.insert(value: 30)
// After these insertions, a right rotation occurs to balance the tree.

Output:

The AVL tree is balanced after each insertion, ensuring that the height difference between the left and right subtrees of any node is at most one.

Explanation:

1. The AVLNode class represents each node in the AVL tree. In addition to the value and child references, each node has a height attribute to store its height in the tree.

2. The AVLTree class manages the root node and provides methods to interact with the tree.

3. For the AVL tree to remain balanced, rotations are implemented. The rotation needed depends on whether the left or right subtrees are heavy.

- rightRotate is used when the left subtree is heavy.

- leftRotate is used when the right subtree is heavy.

4. The insert method adds a node to the tree. After each insertion, it checks the balance factor of each node and performs necessary rotations.

The primary advantage of an AVL tree over a regular binary search tree is that it ensures a balanced tree, which guarantees O(log n) time complexities for insertions, deletions, and look-ups.