二叉平衡树(AVL)-构造解释

概念
- AVL树中任何节点的两个子树的高度最大差为1，因此非常平衡
平衡的好处
- 可以让查找、插入、删除在平均或最坏情况下都是O(logN)

定义

class AVLNode {
    constructor(key) {
        this.key = key;
        this.height = 0;
        this.left = null;
        this.right = null;
    }
}

四种情况
- LL 左左
  - 添加元素到左子节点的左子节点上，导致二叉树失衡
  - 需要做一次顺时针单旋恢复平衡，针对根节点、左子节点、左子节点的右子节点
```
function leftLeftRotation(root) {
    const left = root.left;
    root.left = left.right;
    left.right = root;

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

    return left;
}
```
- RR 右右
  - 添加元素到右子节点的右子节点上，导致二叉树失衡
  - 需要做一次逆时针单旋恢复平衡，针对根节点、右子节点、右子节点的左子节点
```
function rightRightRotation(root) {
    const right = root.right;
    root.right = right.left;
    lright.left = root;

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

    return right;
}
```
- LR 左右
  - 添加元素到左子节点的右子节点上，导致二叉树失衡
  - 需要做两次旋转
    - 一次RR逆时针，其中RR的根节点就是原左子节点
    - 一次LL顺时针，其中LL的根节点就是原根节点
```
function leftRightRotation(root) {
    root.left = rightRightRotation(root.left);
    return leftLeftRotation(root);
}
```
- RL 右左
  - 添加元素到右子节点的左子节点上，导致二叉树失衡
  - 需要做两次旋转
    - 一次LL顺时针，其中LL的根节点就是原右子节点
    - 一次RR逆时针，其中RR的根节点就是原根节点
```
function rightLeftRotation(root) {
    root.right = leftLeftRotation(root.right);
    return rightRightRotation(root);
}
```

获取高度

function height(root) {
    if (!root) return 0;
    return root.height;
}

获取最值节点

function getMax(root) {
    if (root.right) {
        return getMax(root.right);
    } else {
        return root;
    }
}

function getMin(root) {
    if (root.left) {
        return getMin(root.left);
    } else {
        return root;
    }
}

插入

function insertNode(root, key) {
    if (root == null) {
        root = new AVLNode(key);
    } else {
        if (key < root.key) {
            root.left = insertNode(root.left, key);
            if (root.left.height - root.right.height == 2) {
                if (key < root.left.key) {
                    root = leftLeftRotation(root);
                } else {
                    root = leftRightRotation(root);
                }
            }
        } else if (key > root.key) {
            root.right = insertNode(root.right, key);
            if (root.right.height - root.left.height == 2) {
                if (key < root.right.key) {
                    root = rightLeftRotation(root);
                } else {
                    root = rightRightRotation(root);
                }
            }
        } else {
            console.lgog("insert failed")
        }
    }

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

    return root;
}

删除

function removeNode(root, key) {
    if (root == null) return;
    if (!search(root, key)) return;
    
    if (key < root.key) {
        root.left = removeNode(root.left);
        if (height(root.right) - height(root.left) == 2) {
            if (height(root.right.left) > height(root.right.right)) {
                root = rightLeftRotation(root)
            } else {
                root = rightRightRotation(root);
            }
        }
    } else if (key > root.key) {
        root.right = removeNode(root.right);
        if (height(root.left) - height(root.right) == 2) {
            if(height(root.left.left) > height(root.left.right)) {
                root = leftLeftRotation(root);
            } else {
                root = leftRightRotation(root);
            }
        }
    } else {
        if (!root.left && !root.right) {
            root = null;
        } else if(!root.left) {
            root = root.left;
        } else if(!root.right) {
            root = root.right;
        } else {
            if (height(root.left) > height(root.right)) {
                let max = getMax(root.left);
                root.key = max.key;
                root.left = removeNode(root.left, max);
            } else {
                let min = getMin(root.right);
                root.key = min.key;
                root.right = removeNode(root.right, min);
            }
        }
    }

    return root;
}

Keyboard shortcuts

二叉平衡树(AVL)-构造解释