JS算法与树（二）

前言

        二叉搜索树（BST）存在一个问题：当你添加的节点数够多的时候，树的一边可能会非常的深。而其他的分支却只有几层。

   

AVL树

        为了解决上面的问题，我们提出一种自平衡二叉搜索树。意思是任何一个节点左右两侧子树的高度之差最多为1。

        添加或移除节点时，AVL树会尝试自动保持自平衡，任意一个节点（无论深度）的左右子树高度最多相差1。添加或移除节点时。AVL树会尽可能尝试转换为完全数。

节点的高度

        节点的高度是从节点到其任意子节点的边的最大值。

        那么我们怎么计算某个节点的高度呢？

        因为我们并无法事先知道树的哪一层里的左分支深还是右分支深。所以我们需要进行层层比较，层层返回其左右分支深度的最大值。

getNodeHeight(node) {
    if (node == null) {
      return -1;
    }
    return Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) + 1;
}

递归：

递归后的调用：

平衡因子

        一段能平衡树节点的逻辑。在AVL数中，需要对每个节点计算左子树高度（hl）和右子树高度（hr）。并取其差值。如果差值hr - hl或者hl-hr不为0（一样深），1或-1（只差1个深度）。则需要平衡该AVL树。这就是平衡因子的概念。

        我们一般以hr-hl作为平衡因子。

          可以看到，我们刚才的例子，并不是一颗平衡树。因为节点3的平衡因子为2。也就是节点3的左子树和右子树不平衡。

        计算某个节点的左右子树高度差应该很简单了

getBalanceFactor(node) {
    const heightDifference = 
    this.getNodeHeight(node.left) 
    - this.getNodeHeight(node.right);
}

        当高度差大于1的时候，我们就需要对数进行自平衡了。

树的旋转

        叉树中任意节点的左右子树的高度差都不大于1。当插入或删除一个节点时，我们需要通过一次或多次树的「旋转」来保持二叉树的平衡。

        树的旋转分为「左旋」和「右旋」两种具体操作，这两种操作是完全相反的，互为逆操作。

        左旋是「将该节点的右子树逆时针旋转」，右旋是「将该节点的左子树顺时针旋转」。

        对于一个节点node进行左旋操作时，具体操作为：「将node.right子树取下，node.right节点称为新的根节点newRoot，将node接在newRoot的左节点，newRoot.left取下接在node的右节点上。」

        右旋操作相反：「将node.left子树取下，node.left节点作为新的根节点newRoot，将node接在newRoot的右节点，newRoot.right取下接在node的左节点上。」

        

先看这个树，已知的大小关系存在：R>c > Y> b >X >a  

         右旋RR：【子节点左边多右边少，向右单旋转】   适用于左侧子节点的高度大于右侧子节点的高度，且左侧子节点也是平衡或左侧较重。

        左旋LL:【子节点右边多左边少，向左单旋转。适用于左侧节点高度小于右侧子节点高度，且右侧子节点也是平衡或右侧较重

        看到这里你可能会觉得疑惑，什么叫平衡或较重？不急，后面自然会解释。

         简而言之左旋就是把右树节点放自己头上。右旋就是把左树节点放自己头上

        左旋后右旋，便回到最原本的树结构。

         左旋代码：RR

  rotationRR(node) {
    // node对应的是X X包含了左右树节点，修改后返回出去
    // 拿出右节点Y
    const tmp = node.right;
    // 把Y的左节点b拿出来放到X，即node的右节点
    node.right = tmp.left;
    // 把X放到Y的左树
    tmp.left = node;
    // 返回Y
    return tmp;
  }

        右旋代码：LL

  rotationLL(node) {
    const tmp = node.left;
    node.left = tmp.right;
    tmp.right = node;
    return tmp;
  }

        这样就结束了吗？当然不是。上面的旋转只是向左向右的单旋转。

        AVL不平衡存在四种情况：

        第一种情况：R节点的左侧子节点高度高于右侧节点。且R节点的左侧子节点a的子节点（Y-b)重于a的右侧子节点（无）。此时就可以使用我们上面的右旋做法。

         右旋得到：

        第二种情况：R节点的右侧子节点高度高于左侧节点。且R节点的右侧子节点a的子节点（Y-b)重于a的左侧子节点（无）。此时就可以使用我们上面的左旋做法。

        左旋得到：

        第三种情况：R节点的左侧子节点高度高于右侧节点。且R节点的左侧子节点a的子节点（Y-b)重于a的右侧子节点（无）。

如果此时直接右旋： 

依然不平衡。所以这种情况我们需要做两次旋转。

代码：

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

第四种情况：右侧子节点的高度高于左侧子节点,并且右侧子节点左侧较重。这种情况下我们可以对右侧子节点进行有旋转来修复。然后再对不平衡节点进行一个左旋转来修复。

 

向AVL树中插入节点

        前面讲解了这么多树的旋转，就是为了服务于AVL树中节点的增删。

        步骤很简单，每当我们向AVL树里插入或删除一个节点，便执行平衡性检查。平衡性不通过，便旋转树。

const BalanceFactor = {
  UNBALANCED_RIGHT: 1,
  SLIGHTLY_UNBALANCED_RIGHT: 2,
  BALANCED: 3,
  SLIGHTLY_UNBALANCED_LEFT: 4,
  UNBALANCED_LEFT: 5
};

getBalanceFactor(node) {
    const heightDifference = this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
    switch (heightDifference) {
      case -2:
        return BalanceFactor.UNBALANCED_RIGHT;
      case -1:
        return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
      case 1:
        return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
      case 2:
        return BalanceFactor.UNBALANCED_LEFT;
      default:
        return BalanceFactor.BALANCED;
    }
}

        ·左子树高度-右子树高度。当差值为0（default）或-1或1，都属于平衡范围。而2和-2则已经不平衡。-1和1方便让我们辨别哪侧子树较重。

  insert(key) {
    this.root = this.insertNode(this.root, key);
  }

insertNode(node, key) {
    if (node == null) {
      return new Node(key);
    } else if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      node.left = this.insertNode(node.left, key);
    } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      node.right = this.insertNode(node.right, key);
    } else {
      return node; // duplicated key
    }
    // verify if tree is balanced
    const balanceFactor = this.getBalanceFactor(node);
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
      if (this.compareFn(key, node.left.key) === Compare.LESS_THAN) {
        // Left left case
        node = this.rotationLL(node);
      } else {
        // Left right case
        return this.rotationLR(node);
      }
    }
    if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
      if (this.compareFn(key, node.right.key) === Compare.BIGGER_THAN) {
        // Right right case
        node = this.rotationRR(node);
      } else {
        // Right left case
        return this.rotationRL(node);
      }
    }
    return node;
  }

从AVL树里移除节点

 removeNode(node, key) {
    node = super.removeNode(node, key); // {1}
    if (node == null) {
      return node;
    }
    // verify if tree is balanced
    const balanceFactor = this.getBalanceFactor(node);
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
      // Left left case
      if (
        this.getBalanceFactor(node.left) === BalanceFactor.BALANCED ||
        this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT
      ) {
        return this.rotationLL(node);
      }
      // Left right case
      if (this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
        return this.rotationLR(node.left);
      }
    }
    if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
      // Right right case
      if (
        this.getBalanceFactor(node.right) === BalanceFactor.BALANCED ||
        this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT
      ) {
        return this.rotationRR(node);
      }
      // Right left case
      if (this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
        return this.rotationRL(node.right);
      }
    }
    return node;
  }