平衡树

平衡树是计算机科学中的一类数据结构，为改进的二叉查找树。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡树。

在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。

不平衡的树结构：

平衡的树结构：

基本操作

旋转（rotate）：几乎所有平衡树的操作都基于树旋转操作（也有部分基于重构，如替罪羊树），通过旋转操作可以使得树趋于平衡。对一棵查找树（search tree）进行查询、新增、删除等动作，所花的时间与树的高度 h 成比例，并不与树的容量 n 成比例。如果可以让树维持平衡，也就是让 h 维持在$O(\log{n})$ 的左右，就可以在$O(\log{n})$ 的复杂度内完成各种基本操作。

插入（insert）：在树中插入一个新值。

删除（delete）：在树中删除一个值。

查询前驱（predecessor）：前驱定义为小于 x，且最大的数。

查询后继（successor）：后继定义为大于 x，且最小的数。

在维护节点大小（size）后，可以支持以下操作：

查询排名（rank）：排名定义为比 x 小的数的个数加一。

查询第 k 大：即排名为 k 的数。

树旋转

在数据结构中，树旋转（英语：Tree rotation）是对二叉树的一种操作，不影响元素的顺序，但会改变树的结构，将一个节点上移、一个节点下移。树旋转会改变树的形状，因此常被用来将较小的子树下移、较大的子树上移，从而降低树的高度、提升许多树操作的效率。

理解树旋转过程的关键，在于理解其中不变的约束。旋转操作不会导致叶节点顺序的改变（可以理解为旋转操作前后，树的中序遍历结果是一致的），旋转过程中也始终受二叉搜索树的主要性质约束：右子节点比父节点大、左子节点比父节点小。尤其需要注意的是，进行右旋转时，旋转前根的左节点的右节点会变成根的左节点，根本身则在旋转后会变成新的根的右节点，而在这一过程中，整棵树一直遵守着前面提到的几个约束。相反的左旋转操作亦然。

中序不变：二叉树旋转前后，中序遍历的结果不变。

各种平衡树

• AVL 树：是最早被发明的自平衡二叉查找树。在 AVL 树中，任一节点对应的两棵子树的最大高度差为 1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是$O(\log{n})$。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。
• 树堆（Treap）：是有一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为 O (\log {n})。相对于其他的平衡二叉搜索树，Treap 的特点是实现简单，且能基本实现随机平衡的结构。
• 伸展树（Splay tree）：能在均摊$O(\log{n})$ 的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法，在每次查找之后对树进行调整，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。 它的优势在于不需要记录用于平衡树的冗余信息。
• 红黑树 （Red–black tree）：被称为 " 对称二叉 B 树 "。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在$O(\log{n})$ 时间内完成查找，插入和删除，这里的 n 是树中元素的数目。
• 加权平衡树（Weight balanced tree）：加权平衡树的每个结点储存这个结点下子树的大小，可以用来实现顺序统计树操作。优势在于占用空间相对较小。
• 2-3 树：其内部节点（存在子节点的节点）要么有 2 个孩子和 1 个数据元素，要么有 3 个孩子和 2 个数据元素，叶子节点没有孩子，并且有 1 个或 2 个数据元素。2–3 树和 AA 树是等距同构的，换句话说，对于每个 2–3 树，都至少有 1 个 AA 树和它的元素排列是相同的。
• AA 树：AA 树是红黑树的一种变种，设计的目的是减少红黑树考虑的不同情况，区别于红黑树的是，AA 树的红节点只能作为右叶子，从而大大简化了维护 2-3 树的模拟。
• 替罪羊树：其平衡基于部分重建，在非平衡的二叉搜索树中，每次操作以后检查操作路径，找到最高的满足左右子树大小大于平衡因子（alpha）乘以自身大小的结点，重建整个子树。这样就得到了替罪羊树，而被重建的子树的原来的根就被称为替罪羊节点。

应用

用于表示有序的线性数据结构，如优先队列、关联数组、键 (key)- 值 (value) 的映射等。自平衡的二叉查找树与哈希表的相比，各有优缺。平衡树在按序遍历所有键值时是量级最优的，哈希表不能。自平衡二叉查找树在查找一个键值时，最坏情况下时间复杂度优于哈希表， $O(\log n)$ 对比$O(n)$；但平均时间复杂度逊于 hash 表，$O(\log n)$ 对比$O(1)$。

平衡树的排序方法，虽然在平均时间复杂度上也是${\displaystyle O(n\log n)}$，但由于 cache 性能、树的调整操作等，性能上不如快速排序、堆排序、归并排序等同为${\displaystyle O(n\log n)}$ 复杂度的排序。

AVL 树

AVL 树（Adelson-Velsky and Landis Tree）是计算机科学中最早被发明的自平衡二叉查找树。在 AVL 树中，任一节点对应的两棵子树的最大高度差为 1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是$O(\log{n})$。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。

节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

操作

AVL 树的基本操作一般涉及运作同在不平衡的二叉查找树所运作的同样的算法。但是要进行预先或随后做一次或多次所谓的 "AVL 旋转 "。

以下图表以四列表示四种情况，每行表示在该种情况下要进行的操作。在左左和右右的情况下，只需要进行一次旋转操作；在左右和右左的情况下，需要进行两次旋转操作。

• 删除：从 AVL 树中删除，可以通过把要删除的节点向下旋转成一个叶子节点，接着直接移除这个叶子节点来完成。因为在旋转成叶子节点期间最多有$log n$ 个节点被旋转，而每次 AVL 旋转耗费固定的时间，所以删除处理在整体上耗费$O(log n)$ 时间。
• 搜寻：可以像普通二叉查找树一样的进行，所以耗费$O(log n)$ 时间，因为 AVL 树总是保持平衡的。不需要特殊的准备，树的结构不会由于查找而改变。（这是与伸展树搜寻相对立的，它会因为搜寻而变更树结构。）

实现

JavaScript

const { BinarySearchTree } = require('./binarySearchTree');
const { BinarySearchTreeNode } = require('./binarySearchTreeNode');

/**
 * @class AvlTreeNode
 * @extends BinarySearchTreeNode
 */
class AvlTreeNode extends BinarySearchTreeNode {
  constructor(key, value) {
    super(key, value);
    this._height = 1;
  }

  /**
   * Rotate-self left (counter-clockwise)
   * @public
   * @returns {AvlTreeNode}
   */
  rotateLeft() {
    const right = this._right; // this._right will be re-assigned

    // set the node as a left child of its right child
    if (right !== null) {
      if (right.hasLeft()) {
        right.getLeft().setParent(this);
      }

      // rebase right child to node's right left child.
      this._right = right.getLeft();

      right.setLeft(this);
      right.setParent(this._parent);
    }

    // rebase parent's child to node's right child
    if (this.hasParent() && right !== null) {
      if (this._parent.getKey() < right.getKey()) {
        this._parent.setRight(right);
      } else {
        this._parent.setLeft(right);
      }
    }

    // rebase parent to node's right child
    this._parent = right;

    this.updateHeight();
    if (this.hasParent()) {
      this._parent.updateHeight();
    }

    return this;
  }

  /**
   * Rotate-self right (clockwise)
   * @public
   * @returns {AvlTreeNode}
   */
  rotateRight() {
    const left = this._left; // this._left will be re-assigned

    // set the node as a right child of its left child
    if (left !== null) {
      if (left.hasRight()) {
        left.getRight().setParent(this);
      }

      // rebase left child to node's left right child.
      this._left = left.getRight();

      left.setRight(this);
      left.setParent(this._parent);
    }

    // rebase parent's child to node's left child
    if (this.hasParent() && left !== null) {
      if (this._parent.getKey() > left.getKey()) {
        this._parent.setLeft(left);
      } else {
        this._parent.setRight(left);
      }
    }

    // rebase parent to node's left child
    this._parent = left;

    this.updateHeight();
    if (this.hasParent()) {
      this._parent.updateHeight();
    }

    return this;
  }

  /**
   * Rotate-self to right after rotating left child to left
   * @public
   * @returns {AvlTreeNode}
   */
  rotateLeftRight() {
    if (this.hasLeft()) {
      this._left.rotateLeft();
    }
    this.rotateRight();
    return this;
  }

  /**
   * Rotate-self to left after rotating right child to right
   * @public
   * @returns {AvlTreeNode}
   */
  rotateRightLeft() {
    if (this.hasRight()) {
      this._right.rotateRight();
    }
    this.rotateLeft();
    return this;
  }

  /**
   * @public
   * @return {number}
   */
  getLeftHeight() {
    return this.hasLeft() ? this.getLeft().getHeight() : 0;
  }

  /**
   * @public
   * @return {number}
   */
  getRightHeight() {
    return this.hasRight() ? this.getRight().getHeight() : 0;
  }

  /**
   * Updates self height based on the max height of children
   * @public
   * @returns {AvlTreeNode}
  */
  updateHeight() {
    this._height = Math.max(this.getLeftHeight(), this.getRightHeight()) + 1;
    return this;
  }

  /**
   * @public
   * @return {number}
   */
  getHeight() {
    return this._height;
  }

  /**
   * Gets the balance of a node as the diff between left & right heights
   * @public
   * @return {number}
   */
  getBalance() {
    return this.getLeftHeight() - this.getRightHeight();
  }

  /**
   * Checks if the node is balanced
   * @public
   * @return {boolean}
   */
  isBalanced() {
    const balance = this.getBalance();
    return balance >= -1 && balance <= 1;
  }
}

class AvlTree extends BinarySearchTree {
  /**
   * Applies the proper rotation on a node
   * @private
   * @param {AvlTreeNode} node
   */
  _balanceNode(node) {
    if (!node) return;

    node.updateHeight();
    const balance = node.getBalance();
    if (balance > 1) {
      if (node.getLeft().hasLeft()) {
        node.rotateRight();
      } else if (node.getLeft().hasRight()) {
        node.rotateLeftRight();
      }
    } else if (balance < -1) {
      if (node.getRight().hasRight()) {
        node.rotateLeft();
      } else if (node.getRight().hasLeft()) {
        node.rotateRightLeft();
      }
    }

    // check if root was rotated
    if ((balance < -1 || balance > 1) && node === this._root) {
      // replace root when rotated with the child (now parent of root)
      this._root = node.getParent();
    }
  }

  /**
   * Inserts a node with a key/value into tree
   * and maintains the tree balanced by applying the necessary rotations
   *
   * @public
   * @param {number|string} key
   * @param {any} value
   * @return {AvlTree}
   */
  insert(key, value) {
    const newNode = new AvlTreeNode(key, value);
    const insertRecursive = (current) => {
      if (key < current.getKey()) {
        if (current.hasLeft()) {
          insertRecursive(current.getLeft());
          this._balanceNode(current); // backward-tracking
        } else {
          newNode.setParent(current);
          current.setLeft(newNode).updateHeight();
          this._count += 1;
        }
      } else if (key > current.getKey()) {
        if (current.hasRight()) {
          insertRecursive(current.getRight());
          this._balanceNode(current); // backward-tracking
        } else {
          newNode.setParent(current);
          current.setRight(newNode).updateHeight();
          this._count += 1;
        }
      } else {
        current.setValue(value);
      }
    };

    if (this._root === null) {
      this._root = newNode;
      this._count += 1;
    } else {
      insertRecursive(this._root);
    }

    return newNode;
  }

  /**
   * Removes a node by its key
   * and maintains the tree balanced by applying the necessary rotations
   *
   * @public
   * @param {number|string} key
   * @return {boolean}
   */
  remove(key) {
    const removeRecursively = (k, current) => {
      if (current === null) {
        return false;
      }

      if (k < current.getKey()) {
        const removed = removeRecursively(k, current.getLeft());
        this._balanceNode(current);
        return removed;
      }

      if (k > current.getKey()) {
        const removed = removeRecursively(k, current.getRight());
        this._balanceNode(current);
        return removed;
      }

      // current node is the node to remove

      // case 1: node has no children
      if (current.isLeaf()) {
        if (current.isRoot()) {
          this._root = null;
        } else if (k < current.getParent().getKey()) {
          current.getParent().setLeft(null).updateHeight();
        } else {
          current.getParent().setRight(null).updateHeight();
        }
        this._count -= 1;
        return true;
      }

      // case 2: node has a left child and no right child
      if (!current.hasRight()) {
        if (current.isRoot()) {
          this._root = current.getLeft();
        } else if (k < current.getParent().getKey()) {
          current.getParent().setLeft(current.getLeft()).updateHeight();
        } else {
          current.getParent().setRight(current.getLeft()).updateHeight();
        }
        current.getLeft().setParent(current.getParent());
        this._count -= 1;
        return true;
      }

      // case 3: node has a right child and no left child
      if (!current.hasLeft()) {
        if (current.isRoot()) {
          this._root = current.getRight();
        } else if (k < current.getParent().getKey()) {
          current.getParent().setLeft(current.getRight()).updateHeight();
        } else {
          current.getParent().setRight(current.getRight()).updateHeight();
        }
        current.getRight().setParent(current.getParent());
        this._count -= 1;
        return true;
      }

      // case 4: node has left and right children
      const minRight = this.min(current.getRight());
      current.setKey(minRight.getKey()).setValue(minRight.getValue());
      return removeRecursively(minRight.getKey(), minRight);
    };

    return removeRecursively(key, this._root);
  }
}

参考

• 平衡树 - Wikiwand (opens new window)
• 树旋转 - Wikiwand (opens new window)
• AVL 树 - Wikiwand (opens new window)