How do I implement a AVL tree in Swift?

An AVL tree is a self-balancing binary search tree where the difference in heights between the left and right subtrees (the balance factor) is no more than one for all nodes. It automatically adjusts itself during insertions and deletions to maintain this balanced condition, ensuring O(log n) time complexity for search, insertion, and deletion operations.

AVL Tree Implementation in Swift

Below is an example of how to implement an AVL tree in Swift:


        struct AVLNode {
            var key: Int
            var height: Int
            var left: AVLNode?
            var right: AVLNode?

            init(key: Int) {
                self.key = key
                self.height = 1
                self.left = nil
                self.right = nil
            }
        }

        class AVLTree {
            private var root: AVLNode?

            // Function to get height of the node
            private func height(_ node: AVLNode?) -> Int {
                return node?.height ?? 0
            }

            // Function to balance the tree
            private func balanceFactor(of node: AVLNode?) -> Int {
                return height(node?.left) - height(node?.right)
            }

            // Right rotation
            private func rightRotate(y: AVLNode) -> AVLNode {
                let x = y.left!
                let T2 = x.right

                // Perform rotation
                x.right = y
                y.left = T2

                // Update heights
                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) -> AVLNode {
                let y = x.right!
                let T2 = y.left

                // Perform rotation
                y.left = x
                x.right = T2

                // Update heights
                x.height = max(height(x.left), height(x.right)) + 1
                y.height = max(height(y.left), height(y.right)) + 1

                return y
            }

            // Insert a key into the AVL tree
            func insert(key: Int) {
                root = insert(root, key)
            }

            private func insert(_ node: AVLNode?, _ key: Int) -> AVLNode {
                // Perform regular BST insertion
                guard let node = node else {
                    return AVLNode(key: key)
                }

                if key < node.key {
                    node.left = insert(node.left, key)
                } else if key > node.key {
                    node.right = insert(node.right, key)
                } else {
                    return node // Duplicate keys are not allowed
                }

                // Update height of this ancestor node
                node.height = 1 + max(height(node.left), height(node.right)))

                // Balance the node
                let balance = balanceFactor(of: node)

                // Left Left Case
                if balance > 1 && key < node.left!.key {
                    return rightRotate(y: node)
                }

                // Right Right Case
                if balance < -1 && key > node.right!.key {
                    return leftRotate(x: node)
                }

                // Left Right Case
                if balance > 1 && key > node.left!.key {
                    node.left = leftRotate(x: node.left!)
                    return rightRotate(y: node)
                }

                // Right Left Case
                if balance < -1 && key < node.right!.key {
                    node.right = rightRotate(y: node.right!)
                    return leftRotate(x: node)
                }

                return node
            }
        }

How do I implement a AVL tree in Swift?

AVL Tree Implementation in Swift

Popular Topics

Recent Languages

How do I implement a AVL tree in Swift?

AVL Tree Implementation in Swift

Related Questions

Popular Topics

Recent Languages