promise96319

Appearance

平衡二叉树（AVL） ​

简介 ​

二叉查找树虽然能够进行快速查找，但是查找速度是不稳定的，在最坏情况下，二叉树的查找相当于单向链表查找。

那么如何解决这个问题呢？此时就需要保证二叉树的层数尽可能的少，叶子结点与根结点之间的距离尽可能平均，这就涉及一个概念 -- 平衡因子（左子树和右子树的高度差值）。平衡二叉树在插入结点时，会判断平衡因子是否符合要求，如果不符合，则会进行相应处理（旋转），保证左右子树高度平衡。下面将介绍一下四种旋转平衡的方法。

结点为左左 ​

javascript
  rotateLeftLeft(rootNode) {
    // 1. 断开左结点与父结点的联系
    const leftNode = rootNode.left;
    rootNode.setLeft(null);

    // 2. 将左结点作为接下来的父结点
    if (rootNode.parent) {
      rootNode.parent.setLeft(leftNode);
    } else if (rootNode === this.root) {
      // If root node is root then make left node to be a new root.
      this.root = leftNode;
    }

    // 3. 如果左结点有右结点，那么将右结点设置为父结点的左结点（因为右结点比父结点小）
    if (leftNode.right) {
      rootNode.setLeft(leftNode.right);
    }

    // 4. 将父结点设置为左结点的右结点
    leftNode.setRight(rootNode);
  }
  rotateLeftLeft(rootNode) {
    // 1. 断开左结点与父结点的联系
    const leftNode = rootNode.left;
    rootNode.setLeft(null);

    // 2. 将左结点作为接下来的父结点
    if (rootNode.parent) {
      rootNode.parent.setLeft(leftNode);
    } else if (rootNode === this.root) {
      // If root node is root then make left node to be a new root.
      this.root = leftNode;
    }

    // 3. 如果左结点有右结点，那么将右结点设置为父结点的左结点（因为右结点比父结点小）
    if (leftNode.right) {
      rootNode.setLeft(leftNode.right);
    }

    // 4. 将父结点设置为左结点的右结点
    leftNode.setRight(rootNode);
  }

结点为左右 ​

javascript
  rotateLeftRight(rootNode) {
    // 1. 父结点和子结点断开联系
    const leftNode = rootNode.left;
    rootNode.setLeft(null);

    // 2. 将左结点与其右结点断开联系
    const leftRightNode = leftNode.right;
    leftNode.setRight(null);

    // 3. 如果左右结点有左结点，将其添加到左结点的右结点上
    if (leftRightNode.left) {
      leftNode.setRight(leftRightNode.left);
      leftRightNode.setLeft(null);
    }

    // 4. 将左右结点设为父结点的左结点
    rootNode.setLeft(leftRightNode);

    // 5. 将左结点设置为左右结点的左结点
    leftRightNode.setLeft(leftNode);
    
    // 6. 以上步骤实质上将结点转换成了左左的情况
    this.rotateLeftLeft(rootNode);
  }
  rotateLeftRight(rootNode) {
    // 1. 父结点和子结点断开联系
    const leftNode = rootNode.left;
    rootNode.setLeft(null);

    // 2. 将左结点与其右结点断开联系
    const leftRightNode = leftNode.right;
    leftNode.setRight(null);

    // 3. 如果左右结点有左结点，将其添加到左结点的右结点上
    if (leftRightNode.left) {
      leftNode.setRight(leftRightNode.left);
      leftRightNode.setLeft(null);
    }

    // 4. 将左右结点设为父结点的左结点
    rootNode.setLeft(leftRightNode);

    // 5. 将左结点设置为左右结点的左结点
    leftRightNode.setLeft(leftNode);
    
    // 6. 以上步骤实质上将结点转换成了左左的情况
    this.rotateLeftLeft(rootNode);
  }

结点为右左 ​

与节点为左右的时候，情况对称。

结点为右右 ​

与节点为左左的时候，情况对称。

参考 ​

鄂ICP备20002086号-1