平衡二叉树(AVL)

二叉搜索树如果持续插入最大值或者最小值等情况，会导致搜索树出现向一边长的结构。这样查找效率是以来树的高度的。

平衡二叉树在搜索树基础上用来平衡树的高度， 尽量保证节点树的高度一致。

• 左右子树高度差绝对值不超过 1，|BF| <= 1
• 平衡因子(Balance Factor)， BF = Hl - Hr， 即左右子树高度差

知识点

衡量一颗二叉树的查找效率：平均查找长度（ASL），所有节点查找判断次数平均值。

ASL 越大查找效率越低，ASL 越小查找效率越高！

平衡二叉树的调整

需要调整以满足平衡二叉搜索树要求

• 破坏节点 即插入的新节点。
• 被破坏节点 即原来该节点满足 |BF| <= 1，插入新节点后，|BF| > 1，不满足要求。

插入可能情况：

1. 破坏节点插入在被破坏节点的左子树的左子树（LL）
2. 破坏节点插入在被破坏节点的左子树的右子树（LR）
3. 破坏节点插入在被破坏节点的右子树的左子树（RL）
4. 破坏节点插入在被破坏节点的右子树的右子树（RR）

调整思路：

1. LL 插入，被破坏节点值最大，将被破坏者左子树位置提升，被破坏者移动到原来左子树右边。

2. LR 插入，

3. RL 插入

4. RR 插入，被破坏节点值最小，将被破坏者右子树位置提升，被破坏者移动到原来右子树的右边。

代码实现

class BinTree {
  constructor() {
    this.bf = 0;
    this.data = null;
    this.left = null;
    this.right = null;
  }
  // 计算BF值
  calcBF() {
    let left = 0;
    let right = 0;
    if (this.left) left = Math.abs(this.left.calcBF()) + 1;
    if (this.right) right = Math.abs(this.right.calcBF()) + 1;
    this.bf = left - right;
    return this.bf;
  }
}

class AVL {
  constructor() {
    this.head = null;
  }

  // 插入节点并进行平衡调整
  _insert(data, bintree) {
    if (!bintree) {
      bintree = new BinTree();
      bintree.data = data;
    } else {
      if (data < bintree.data) {
        bintree.left = this._insert(data, bintree.left);
        const bf = bintree.calcBF();
        // bf 大于0 说明左子树高度大，反过来，bf === 2 说明破坏者只会在左子树里面。
        if (bf === 2) {
          if (data < bintree.left.data) {
            // data 小于左子树值，说明破坏者在左子树的左子树里面。进行 LL 调整。
            bintree = this.rotationLL(bintree);
          } else {
            // data 大于左子树值，说明破坏者在左子树的右子树里面。进行 LR 调整。
            bintree = this.rotationLR(bintree);
          }
        }
      } else if (data > bintree.data) {
        bintree.right = this._insert(data, bintree.right);
        const bf = bintree.calcBF();
        // BF小于0 右子树高度大， 反过来， bf === -2 说明破坏者只会在右子树里面
        if (bf === -2) {
          if (data > bintree.right) {
            // data 大于右子树值，说明破坏者在右子树的右子树里面。进行 RR 调整。
            bintree = this.rotationRR(bintree);
          } else {
            // data 小于右子树值，说明破坏者在右子树的右子树里面。进行 RL 调整。
            bintree = this.rotationRL(bintree);
          }
        }
      }
      // else 存在该数据，什么都不做
    }
    return bintree;
  }

  insert(data) {
    this.head = this._insert(data, this.head);
  }

  rotationLL(bintree) {
    const tmp = bintree.left;
    // 注意： 如果tmp右子树为空，一定要将bintree.left值设置为空，否则bintree.left会指向tmp，造成堆栈溢出
    bintree.left = tmp.right;
    tmp.right = bintree;
    return tmp;
  }

  rotationLR(bintree) {
    bintree.left = this.rotationRR(bintree.left);
    return this.rotationLL(bintree);
  }

  rotationRR(bintree) {
    const tmp = bintree.right;
    // 注意： 如果tmp左子树为空，一定要将bintree.right值设置为空，否则bintree.right会指向tmp，造成堆栈溢出
    bintree.right = tmp.left;
    tmp.left = bintree;
    return tmp;
  }

  rotationRL(bintree) {
    bintree.right = this.rotationLL(bintree.right);
    return this.rotationRR(bintree);
  }
}

const avl = new AVL();
avl.insert(10);
avl.insert(1);
avl.insert(2);
avl.insert(8);
avl.insert(12);
console.log(avl);