CLRS滑稽导论 (1) : AVL树

  在二叉树的学习中，我们会接触到很多不同的树。其中，用得最为普遍的，是二叉搜索树。而为提升二叉树搜索的效率，又引入自平衡二叉树的概念。自平衡二叉搜索树是指通过处理可以实现子树相对平衡，即不极端地偏向一边的二叉搜索树。由于相对平衡的特性，树可以实现查询、插入、删除操作在时间上的优化。

  AVL树是最早被构造出来的自平衡二叉搜索树。它的构成比较简单，维护的只有树的高度一个因子。同时，对该因子进行修饰，可以演变成维护树的高差。但是……其实，作者提出了这个模型，但并没有指定某种实现。实现的方法很多，但都是在维护它的定义。可以对每个树高进行记录，也可以用平衡因子的方法来标记偏移方向。这里利用树的高差进行处理。其实绝大多数的说法都是平衡因子，但维护的方式不同。只是实现的不同技巧罢了。

一、定义

AVL树的递归定义是，对于每一个节点的左右子树，他们的高差不超过1。
$$
x.h = max(x.left.h, x.right.h)+1
$$
即：
$$
|h_l-h_r| \le 1
$$
这样做的好处是，可以实现树高仅为$O(log\ n)$ 。那么，查询、插入、删除的时间复杂度都类似地为$O(log\ n)$。

下面我们来证明时间复杂度应该为$O(log\ n)$。

如果一棵树是动的，那他的高度就不好处理了。但如果假设是静态的，一切都会好处理得多。我们假设树高为$h$， 则设高为$h$的树的节点数为$N_h$。

我们定义：$N_h$ 是高为 h 的树中所含有最少的节点（$N_h$ is the min number nodes in an tree of high h），同时假设左子树比右子树永远高1。则得出：

（1）当高度为常数时，时间、空间复杂度也为常数。即：

$$
N_{o(1)} = O(1)
$$

（2）当树的高度为$h$时，

$$
N_h = 1 + N_{h-1}+N_{h-2}
$$

(3) 我们用它和斐波那契数列进行比较，并利用斐波那契数列的特性进行化简：

$$
N_h = F_h + 1 (F_h \ is\ the \ Fib\ sequence)
$$

$$
N_h > N_{h-1} + N_{h-2} = F_h \ (F_h \ is\ the \ Fib\ sequence)
$$

而我们知道，斐波那契数列是指数级增长的函数，$F(n) = O(2^n)$

依据它的指数边界：

$$
N_h > F_h = \frac{\varphi^h}{\sqrt{5}} = O(2^n)
$$

$$\lim _{h \rightarrow \infty}{N_h} > F_h = \varphi^h$$

$$
log\ N_h = h
$$

that is:

$$
h = O(log\ n)
$$

自此，AVL树是平衡树的证明结束。只要他是平衡的，那他的查询(query)、删除(delete)、插入(insert)都是对数时间复杂度的。

---

然后，我们来一步步用最基础的方式实现它

既然为二叉搜索树，那么他的搜索过程和普通的搜索树是一样的。作为平衡树，他的关键点在于他的插入与删除。因为插入与删除会改变树的形态。所以，这里我们只描述插入与删除。查询部分，请参阅CLRS v3的第12章。

首先，我们开始构造一棵树。树的节点要有如下的关键词：左子树、右子树、亲代的指针，树高的平衡因子，节点的权值。树要包含有根节点，空节点（为了方便实现与保护不越界）。

一个直观的演示：位于visualgo的链接 (要手动调到AVL🌲部分)

struct node {
  int key;               // Key
  int avlK;              // load balance factor
  node *left, *right, *p;// respective pointers
  node() : key(0), avlK(0), left(NULL), right(NULL), p(NULL) {}
  node(int key, int level = 0)
      : key(key), avlK(level), left(NULL), right(NULL), p(NULL) {}
};

struct AVLtree {
  node *root;
  node *nil;
  AVLtree() {
    nil = new node(-1, -1);
    root = nil;
    nil->right = nil;
    nil->left = nil;
  }
};

同时，我们需要一些公用的函数：

int max(int a, int b) { return a > b ? a : b; }

int inOrder(AVLtree &T, node *x) {
    if (x != T.nil) {
        inOrder(T, x->left);
        printf("%d : %d\n", x->key, x->avlK);
        inOrder(T, x->right);
    }
    return 1;
}

node *getMinPointer(AVLtree &T, node *x) {
    node *t = x;
    while (t->left != T.nil) {
        t = t->left;
    }
    return t;
}

然后我们来定义旋转。

旋转是为了降低树的高度，以达到平衡局部的需求。平衡树中的关键步骤都是与旋转有关。旋转包括左旋和右旋，两种方法是对称的。同时，由于AVL树中平衡因子的特性，我们需要修饰旋转后节点的平衡因子。对于AVL树来说，他的平衡可以用平衡因子来调控。

而这里平衡因子的维护方法是，$ v.h = max(v.left.h,\ v.right.h)+1 $。所以，它左右子树高差差区间为$[-2, 2]$。如果恰好遇到有些节点abs(x) == 2，则证明，树的高度需要调节。于是乎通过旋转来达到目的。

以下是旋转部分的代码：（和CLRS v3红黑树的旋转几乎无异没有差别）

// This is the left version. Reverse the direction will be the right version.
int leftRotate(AVLtree &T, node *x) {
    node *y = x->right;
    x->right = y->left;
    if (y->left != T.nil) {
        y->left->p = x;
    }
    y->p = x->p;

    if (x->p == T.nil) {
        T.root = y;
    } else if (x == x->p->left) {
        x->p->left = y;
    } else {
        x->p->right = y;
    }
    y->left = x;
    x->p = y;
    return 1;
}

右旋：（其实差不多的，就是左旋的逆）

int rightRotate(AVLtree &T, node *x) {
    node *y = x->left;
    x->left = y->right;
    if (y->right != T.nil) {
        y->right->p = x;
    }
    y->p = x->p;

    if (x->p == T.nil) {
        T.root = y;
    } else if (x == x->p->right) {
        x->p->right = y;
    } else {
        x->p->left = y;
    }
    y->right = x;
    x->p = y;
    return 1;
}

然后处理插入部分。插入部分的开始跟普通二叉搜索树一致，只不过到了插入完毕以后，要向后轮询其平衡因子以修正树的平衡性。

/**
 * Procedure Insert:
 * TODO: insert the target node into one tree.
 * param:
 * T: the target tree
 * ins: the node to be inserted
 */
int Insert(AVLtree &T, node *ins) {
  // y: trace x's parent;
  // x: trace y's parent;
  node *x, *y;

  // initalize x, y
  y = T.nil;
  x = T.root;
  while (x != T.nil) { // trace the pos
    y = x;
    if (ins->key < x->key) {
      x = x->left;
    } else
      x = x->right;
  }                 // Go as routinue;
  ins->p = y;       // Bind its parent
  if (y == T.nil) { // Case of only one node
    T.root = ins;
    y = T.root;
  } else if (ins->key < y->key) {
    y->left = ins;
  } else {
    y->right = ins;
  }
  ins->left = T.nil;
  ins->right = T.nil;
  insertFix(T, ins); // Invoke the fix procedure.
  return 0;          // Status code. Just persional convention.
}

  上面的第34行，转到了修正树的结构的部分。插入之后，树可能遇到平衡问题：左子树比右子树高2（反过来亦然），这样就打破了树的平衡性。可能的情况如下图：

又如：

那么，我们就通过向上追溯平衡因子，进而旋转使之平衡。

对于第一种，我们采用这样的方式：

然后，我们又发现，第二种情况可以转换变成第一种。

嗯。很好。多节点的时候，其实也是相近的。

这里最困难的地方在于维护平衡因子。既要是其正确表达当前状态下倾斜的方向，又要对相应节点进行旋转。

所以我们来fix它。

int insertFix(AVLtree &T, node *x) {
    // 务必要小心
    bool Flag = 0;
    node *z = NULL;
    int highTmp = 0;

    node *y = NULL;
    while (x != T.root) {
        Flag = 0;
        y = x->p;
        highTmp++;
        if (highTmp > y->avlK) {
            y->avlK = highTmp;
        }
        if (y->left->avlK - y->right->avlK >= 2) {
            Flag = 1;
            if (x->right->avlK > x->left->avlK) {
                leftRotate(T, x);
                x->avlK = max(x->left->avlK, x->right->avlK) + 1;
                y->avlK = max(y->left->avlK, y->right->avlK) + 1;
                x = y->left;
            }

            rightRotate(T, y);
            y->avlK = max(y->left->avlK, y->right->avlK) + 1;
            x->avlK = max(x->left->avlK, x->right->avlK) + 1;
            // DO Sth

        } else if (y->right->avlK - y->left->avlK >= 2) {
            Flag = 1;
            if (x->left->avlK > x->right->avlK) {
                rightRotate(T, x);
                x->avlK = max(x->left->avlK, x->right->avlK) + 1;
                y->avlK = max(y->left->avlK, y->right->avlK) + 1;
                x = y->right;
            }

            leftRotate(T, y);

            y->avlK = max(y->left->avlK, y->right->avlK) + 1;
            x->avlK = max(x->left->avlK, x->right->avlK) + 1;
        }
        highTmp = Flag ? x->avlK : highTmp;
        if (x == T.root) {
            break;
        }
        x = x->p;
    }
    return 1;
}

这就。。Fix完了。233

---

然后就是delete部分，参考红黑树的实现

  delete部分其实是插入的逆。首先使用正常的二叉搜索树插入，然后再从被抽取的位置开始对其进行fix。
  贴代码：

/**
 * Procedure: AVL_Delete
 * @param T : AVLtree &
 * @param z : node *
 * @return  : int
 */

// Now is part of original RB-delete
void AVL_Delete(AVLtree &T, node *z) {
  node *x;
  node *y = z;
  int yAVLK = z->avlK;
  if (z->left == T.nil) {
    x = z->right;
    AVL_Transplant(T, z, z->right);
  } else if (z->right == T.nil) {
    x = z->left;
    AVL_Transplant(T, z, z->left);
  } else {
    y = getMinPointer(T, z->right);
    x = y->right;    // Get the right next pointer & ready to transplant
    if (y->p == z) { // If y & z are adjacant
      x->p = y;
    } else {
      AVL_Transplant(T, y, y->right);
      y->right = z->right;
      y->right->p = y;
    }
    AVL_Transplant(T, z, y);
    y->left = z->left;
    y->left->p = y;
    y->avlK = z->avlK;
  }
  AVLDeleteFix(T, x);
}

同样地，从被削减的那个点开始修复。逐步向上更新🌲高。

void AVLDeleteFix(AVLtree &T, node *x) {
  int highFix = x->avlK;
  node *y;

  do {
    y = x;
    x = x->p;
    x->avlK = max(x->left->avlK, x->right->avlK) + 1;
    if (x->left->avlK - x->right->avlK >= 2) {
      if (y->right->avlK > y->left->avlK) {
        leftRotate(T, y);
        y->avlK = max(y->left->avlK, y->right->avlK) + 1;
        x->avlK = max(x->left->avlK, x->right->avlK) + 1;
        y = x->left;
      }
      rightRotate(T, x);
      x->avlK = max(x->left->avlK, x->right->avlK) + 1;
      y->avlK = max(y->left->avlK, y->right->avlK) + 1;
      x = x->p; // update pointer
    } else if (x->right->avlK - x->left->avlK >= 2) {
      if (y->left->avlK > y->right->avlK) {
        rightRotate(T, y);
        y->avlK = max(y->right->avlK, y->left->avlK) + 1;
        x->avlK = max(x->left->avlK, x->right->avlK) + 1;
        y = x->right;
      }
      leftRotate(T, x);
      x->avlK = max(x->left->avlK, x->right->avlK) + 1;
      y->avlK = max(y->left->avlK, y->right->avlK) + 1;
      x = x->p; // update pointer
    }
  } while (x != T.root);
}

  删除的fix和插入的fix几乎一致，不断向上搜索，更新avl平衡因子，遇到过度倾斜的时候就立刻修复。

～完啦！～

转载请联系作者