js实现平衡二叉树

平衡二叉树的实现

平衡二叉树（AVL树）是一种自平衡二叉搜索树，确保树的高度差不超过1。在JavaScript中，可以通过类结构实现AVL树，包括节点插入、删除和平衡操作。

定义节点类

每个节点包含值、左子树、右子树和高度属性。

class AVLNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
        this.height = 1;
    }
}

定义AVL树类

AVL树类需要实现插入、删除和平衡方法。

class AVLTree {
    constructor() {
        this.root = null;
    }

    // 获取节点高度
    getHeight(node) {
        return node ? node.height : 0;
    }

    // 更新节点高度
    updateHeight(node) {
        node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1;
    }

    // 计算平衡因子
    getBalanceFactor(node) {
        return this.getHeight(node.left) - this.getHeight(node.right);
    }
}

旋转操作

AVL树通过旋转操作保持平衡，包括左旋和右旋。

右旋操作：

rightRotate(y) {
    const x = y.left;
    const T2 = x.right;

    x.right = y;
    y.left = T2;

    this.updateHeight(y);
    this.updateHeight(x);

    return x;
}

左旋操作：

leftRotate(x) {
    const y = x.right;
    const T2 = y.left;

    y.left = x;
    x.right = T2;

    this.updateHeight(x);
    this.updateHeight(y);

    return y;
}

插入节点

插入节点后检查平衡并进行旋转。

insert(value) {
    this.root = this._insert(this.root, value);
}

_insert(node, value) {
    if (!node) return new AVLNode(value);

    if (value < node.value) {
        node.left = this._insert(node.left, value);
    } else if (value > node.value) {
        node.right = this._insert(node.right, value);
    } else {
        return node; // 不允许重复值
    }

    this.updateHeight(node);
    const balance = this.getBalanceFactor(node);

    // 左左情况
    if (balance > 1 && value < node.left.value) {
        return this.rightRotate(node);
    }

    // 右右情况
    if (balance < -1 && value > node.right.value) {
        return this.leftRotate(node);
    }

    // 左右情况
    if (balance > 1 && value > node.left.value) {
        node.left = this.leftRotate(node.left);
        return this.rightRotate(node);
    }

    // 右左情况
    if (balance < -1 && value < node.right.value) {
        node.right = this.rightRotate(node.right);
        return this.leftRotate(node);
    }

    return node;
}

删除节点

删除节点后同样需要检查平衡。

delete(value) {
    this.root = this._delete(this.root, value);
}

_delete(node, value) {
    if (!node) return null;

    if (value < node.value) {
        node.left = this._delete(node.left, value);
    } else if (value > node.value) {
        node.right = this._delete(node.right, value);
    } else {
        if (!node.left || !node.right) {
            node = node.left || node.right;
        } else {
            const minRight = this.findMin(node.right);
            node.value = minRight.value;
            node.right = this._delete(node.right, minRight.value);
        }
    }

    if (!node) return null;

    this.updateHeight(node);
    const balance = this.getBalanceFactor(node);

    // 左左情况
    if (balance > 1 && this.getBalanceFactor(node.left) >= 0) {
        return this.rightRotate(node);
    }

    // 左右情况
    if (balance > 1 && this.getBalanceFactor(node.left) < 0) {
        node.left = this.leftRotate(node.left);
        return this.rightRotate(node);
    }

    // 右右情况
    if (balance < -1 && this.getBalanceFactor(node.right) <= 0) {
        return this.leftRotate(node);
    }

    // 右左情况
    if (balance < -1 && this.getBalanceFactor(node.right) > 0) {
        node.right = this.rightRotate(node.right);
        return this.leftRotate(node);
    }

    return node;
}

findMin(node) {
    while (node.left) {
        node = node.left;
    }
    return node;
}

使用示例

const avlTree = new AVLTree();
avlTree.insert(10);
avlTree.insert(20);
avlTree.insert(30);
avlTree.insert(40);
avlTree.insert(50);
avlTree.insert(25);

avlTree.delete(40);

通过以上实现，可以构建一个功能完整的AVL树，支持动态插入和删除操作，同时自动维护树的平衡性。