How do I implement a generic AVL tree in Swift?

An AVL tree is a self-balancing binary search tree where the difference between the heights of left and right subtrees cannot be more than one for all nodes. This example illustrates how to implement a generic AVL tree in Swift, allowing it to store any data type that conforms to the Comparable protocol.


    // AVL Tree implementation in Swift
    class AVLNode {
        var value: T
        var left: AVLNode?
        var right: AVLNode?
        var height: Int

        init(value: T) {
            self.value = value
            self.height = 1
        }
    }

    class AVLTree {
        private var root: AVLNode?

        private func height(node: AVLNode?) -> Int {
            return node?.height ?? 0
        }

        private func updateHeight(node: AVLNode) {
            node.height = max(height(node: node.left), height(node: node.right)) + 1
        }

        private func balanceFactor(node: AVLNode?) -> Int {
            return height(node: node?.left) - height(node: node?.right)
        }

        private func rotateRight(y: AVLNode) -> AVLNode {
            let x = y.left!
            y.left = x.right
            x.right = y
            updateHeight(y)
            updateHeight(x)
            return x
        }

        private func rotateLeft(x: AVLNode) -> AVLNode {
            let y = x.right!
            x.right = y.left
            y.left = x
            updateHeight(x)
            updateHeight(y)
            return y
        }

        private func rebalance(node: AVLNode) -> AVLNode {
            updateHeight(node)
            let balance = balanceFactor(node)

            if balance > 1 {
                if balanceFactor(node.left) < 0 {
                    node.left = rotateLeft(x: node.left!)
                }
                return rotateRight(y: node)
            }
            if balance < -1 {
                if balanceFactor(node.right) > 0 {
                    node.right = rotateRight(y: node.right!)
                }
                return rotateLeft(x: node)
            }
            return node
        }

        func insert(value: T) {
            root = insert(node: root, value: value)
        }

        private func insert(node: AVLNode?, value: T) -> AVLNode {
            guard let node = node else {
                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 // No duplicates allowed
            }

            return rebalance(node: node)
        }

        func inOrderTraversal() -> [T] {
            var elements: [T] = []
            inOrderTraversal(node: root, elements: &elements)
            return elements
        }

        private func inOrderTraversal(node: AVLNode?, elements: inout [T]) {
            guard let node = node else { return }
            inOrderTraversal(node: node.left, elements: &elements)
            elements.append(node.value)
            inOrderTraversal(node: node.right, elements: &elements)
        }
    }

    // Example usage
    let avlTree = AVLTree()
    avlTree.insert(value: 10)
    avlTree.insert(value: 20)
    avlTree.insert(value: 30)
    avlTree.insert(value: 5)
    avlTree.insert(value: 3)
    let sortedElements = avlTree.inOrderTraversal()
    print(sortedElements) // Output: [3, 5, 10, 20, 30]

How do I implement a generic AVL tree in Swift?

Popular Topics

Recent Languages

How do I implement a generic AVL tree in Swift?

Related Questions

Popular Topics

Recent Languages