AVLTree

avl.ts

class AVLNode {
    public left: AVLNode|null = null;
    public right: AVLNode|null = null;
    public height: number = 1;

    constructor(
        public value: number
    ) {}
}

class AVLTree {
    public root: AVLNode|null = null;

    // Inserir valor
    public insert(value: number) {
        this.root = this.insertNode(this.root, value);
    }

    // Inserir nó
    public insertNode(root: AVLNode|null, value: number): AVLNode {
        if (root === null) {
            return new AVLNode(value);
        } else if (value < root.value) {
            root.left = this.insertNode(root.left, value);
        } else {
            root.right = this.insertNode(root.right, value);
        }

        root.height = 1 + Math.max(this.getHeight(root.left), this.getHeight(root.right));

        const balanceFactor = this.getBalanceFactor(root);

        /**
         * Se for maior que 1, rotacionar a direita
         * Caso contrário se for menor que -1, rotacionar a esquerda
         */
        if (balanceFactor > 1) {
            const leftNodeBalanceFactor = this.getBalanceFactor(root.left);

            /**
             * Se o fator de balanceamento do nó esquerdo for maior ou igual que zero, fazer rotação simples
             * Caso contrário, fazer rotação dupla. Rotacionar o nó esquerdo para a esquerda e depois
             * rotacionar a raiz toda para a direita.
             */
            if (leftNodeBalanceFactor >= 0) {
                return this.rightRotate(root);
            } else {
                root.left = this.leftRotate(root.left!);
                return this.rightRotate(root);
            }
        } else if (balanceFactor < -1) {
            const rightNodeBalanceFactor = this.getBalanceFactor(root.right);

            /**
             * Se o fator de balanceamento do nó direito for menor ou igual que zero, fazer rotação simples
             * Caso contrário, fazer rotação dupla. Rotacionar o nó direito para a direita e depois
             * rotacionar a raiz toda para a esquerdq.
             */
            if (rightNodeBalanceFactor <= 0) {
                return this.leftRotate(root);
            } else {
                root.right = this.rightRotate(root.right!);
                return this.leftRotate(root);
            }
        }

        return root;
    }

    // Obter altura do nó
    public getHeight(node: AVLNode|null): number {
        if (node === null) return 0;
        return node.height;
    }

    // Obter fator de balanceamento
    public getBalanceFactor(node: AVLNode|null): number {
        if (node === null) return 0;

        return this.getHeight(node.left) - this.getHeight(node.right);
    }

    // Rotacionar a esquerda
    public leftRotate(node: AVLNode): AVLNode {
        const newRoot = node.right!;
        const subTreeNewLeftRoot = newRoot.left;

        newRoot.left = node;
        node.right = subTreeNewLeftRoot;

        node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
        newRoot.height = 1 + Math.max(this.getHeight(newRoot.left), this.getHeight(newRoot.right));

        return newRoot;
    }

    // Rotacionar a direita
    public rightRotate(node: AVLNode): AVLNode {
        const newRoot = node.left!;
        const subTreeNewLeftRoot = newRoot.right;

        newRoot.right = node;
        node.left = subTreeNewLeftRoot;

        node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
        newRoot.height = 1 + Math.max(this.getHeight(newRoot.left), this.getHeight(newRoot.right));

        return newRoot;
    }

    public search(value: number): AVLNode|null {
        return this.searchNode(this.root, value);
    }

    public searchNode(root: AVLNode|null, value: number): AVLNode|null {
        if (root === null || root.value === value) {
            return root;
        } else if (value < root.value) {
            return this.searchNode(root.left, value);
        } else {
            return this.searchNode(root.right, value);
        }
    }

    public getLowestValueNode(node: AVLNode): AVLNode {
        let current = node;
        while (current.left !== null) current = current.left;
        return current;
    }

    public remove(value: number): AVLNode|null {
        return this.removeNode(this.root, value);
    }

    public removeNode(root: AVLNode|null, value: number): AVLNode|null {
        if (root === null) return root;

        if (value < root.value) {
            root.left = this.removeNode(root.left, value);
        } else if (value > root.value) {
            root.right = this.removeNode(root.right, value);
        } else {
            if (root.left === null) return root.right;
            else if (root.right === null) return root.left;

            const next = this.getLowestValueNode(root.right);

            root.value = next.value;
            root.right = this.removeNode(root.right, next.value);
        }

        root.height = 1 + Math.max(this.getHeight(root.left), this.getHeight(root.right));

        const balanceFactor = this.getBalanceFactor(root);

        /**
         * Se for maior que 1, rotacionar a direita
         * Caso contrário se for menor que -1, rotacionar a esquerda
         */
        if (balanceFactor > 1) {
            const leftNodeBalanceFactor = this.getBalanceFactor(root.left);

            /**
             * Se o fator de balanceamento do nó esquerdo for maior ou igual que zero, fazer rotação simples
             * Caso contrário, fazer rotação dupla. Rotacionar o nó esquerdo para a esquerda e depois
             * rotacionar a raiz toda para a direita.
             */
            if (leftNodeBalanceFactor >= 0) {
                return this.rightRotate(root);
            } else {
                root.left = this.leftRotate(root.left!);
                return this.rightRotate(root);
            }
        } else if (balanceFactor < -1) {
            const rightNodeBalanceFactor = this.getBalanceFactor(root.right);

            /**
             * Se o fator de balanceamento do nó direito for menor ou igual que zero, fazer rotação simples
             * Caso contrário, fazer rotação dupla. Rotacionar o nó direito para a direita e depois
             * rotacionar a raiz toda para a esquerdq.
             */
            if (rightNodeBalanceFactor <= 0) {
                return this.leftRotate(root);
            } else {
                root.right = this.rightRotate(root.right!);
                return this.leftRotate(root);
            }
        }

        return root;
    }

    public print() {
        this.printTree(this.root);
    }

    public printTree(root: AVLNode | null, level: number = 0, prefix: string = "Raiz: ") {
        if (root === null) return;

        console.log(" ".repeat(level * 4) + prefix + String(root.value));

        if (root.left === null && root.right === null) return;
        
        if (root.left !== null) {
            this.printTree(root.left, level + 1, "Esquerda: ");
        } else {
            console.log(" ".repeat((level + 1) * 4) + "Esquerda: null");
        }
        
        if (root.right !== null) {
            this.printTree(root.right, level + 1, "Direita: ");
        } else {
            console.log(" ".repeat((level + 1) * 4) + "Direita: null");
        }
    }
}

const avl = new AVLTree();

for (const value of [10, 20, 5, 4, 8, 15, 25]) {
    avl.insert(value);
}

avl.remove(5);
avl.printTree(avl.search(20));

avl.print();

out.log

[LOG]: Raiz: 20
[LOG]:     Esquerda: 15
[LOG]:     Direita: 25
[LOG]: Raiz: 10
[LOG]:     Esquerda: 8
[LOG]:         Esquerda: 4
[LOG]:         Direita: null
[LOG]:     Direita: 20
[LOG]:         Esquerda: 15
[LOG]:         Direita: 25