10、平衡二叉搜索树BBST

平衡二叉搜索树(Balanced Binary Search Tree BBST)是一种自平衡的二叉搜索树。所以自平衡意味着会自行调整，以保持较低(对数)的高度，从而允许更快的操作，例如插入和删除。

10.1、树旋转

大多数BBST算法核心组成部分是：树不变式和树旋转的巧妙用法。

树不变式：是在每次操作后必须满足的属性/规则。为了确保始终满足不变式，通常会应用一系列树旋转。

在树旋转的过程中需要确保保持BST的不变式：左子树比较小，右子树比较大。

10.1.1、更新单向指针的BBST

为此，我们可以使用以下操作实现右旋转，注意观察宣传前后，BST的不变式：

public void rightRotate(Node a) {
  Node b = a.left;
  a.left = b.right;
  b.right = a;
  return b;
}

如下图，我们准备执行rightRotate(a)：

为什么可以这样变换呢？

还是那个原则：BST不变式。

所有BBST都是BST，因此对于每个节点n，都有：n.left <n && n < n.right。(这里的前提是没有重复元素)

我们在变换操作的时候只要确保这个条件成立即可，即保持BST不变性成立的前提下，我们可以对树中的值和节点进行随机变换/旋转。

注意，如上图，如果a节点还有父节点p，那么就把p节点原来指向a节点变更为指向b节点。

10.1.2、更新双向指针的BBST

在某些需要经常方位父节点或者同级节点的BBST中，我们就不是像上面那样最多更新3个指针，而是必须更新6个指针了，操作会复制些许。

以下是代码实现：

public void rightRotate(Node a) {
  Node p = a.parent
  Node b = a.left;
  a.left = b.right;
  if (b.right != null) {
    b.right.parent = a;
  }
  b.right = a;
  a.parent = b;
  b.parent = p;
  // 更新父指针
  if (p != null) {
    if (p.left == a) {
      p.left = b;
    } else {
      p.right = b;
    }
  }
  return b;
}