AVL树

在多次插入和删除操作后，二叉搜索树可能退化为链表。在这种情况下，所有操作的时间复杂度将从$O(\log n)$劣化为$O(n)$。

而AVL树确保在持续添加和删除节点后其不会退化，从而使得各种操作的时间复杂度保持在$O(\log n)$级别。

AVL 树既是二叉搜索树，也是平衡二叉树，同时满足这两类二叉树的所有性质。

由于 AVL 树的相关操作需要获取节点高度，因此我们需要为节点类添加 height 变量：

typedef struct TreeNode{
    int val;
    int height;
    struct TreeNode *left;
    struct TreeNode *right;
}TreeNode;

// 构造函数
TreeNode *newTreeNode(int val){
    TreeNode *node;
    node=(TreeNode*)malloc(sizeof(TreeNode));
    node->val=val;
    node->height=0;
    node->left=NULL;
    node->right=NULL;
    return node;
}

“节点高度”是指从该节点到它的最远叶节点的距离，即所经过的“边”的数量。需要特别注意的是，叶节点的高度为0，而空节点的高度为-1。我们将创建两个工具函数，分别用于获取和更新节点的高度：

int height(TreeNode*node){
    if(node!=NULL){
        return node->height;
    }
    return -1;
}
void updateHeight(TreeNode*node){
    int lh=height(node->left);
    int rh=height(node->right);
    if(lh>rh){
        node->height=lh+1;
    }
    else{
        node->height=rh+1;
    }
}

节点的平衡因子（balance factor）定义为节点左子树的高度减去右子树的高度，同时规定空节点的平衡因子为0。我们同样将获取节点平衡因子的功能封装成函数，方便后续使用：

int balanceFactor(TreeNode*node){
    if(node==NULL){
        return 0;
    }
    // 节点平衡因子 = 左子树高度 - 右子树高度
    return height(node->left)-height(node->right);
}

设平衡因子为$f$，则一棵AVL树的任意节点的平衡因子皆满足$-1<f<1$。

AVL树常用操作

AVL树旋转

AVL树相比普通的二叉搜索树能保持平衡而不退化是通过旋转操作实现的。它能够在不影响二叉树的中序遍历序列的前提下，使失衡节点重新恢复平衡。换句话说，旋转操作既能保持“二叉搜索树”的性质，也能使树重新变为“平衡二叉树”。

我们将平衡因子绝对值>1的节点称为“失衡节点”。根据节点失衡情况的不同，旋转操作分为四种：右旋、左旋、先右旋后左旋、先左旋后右旋。下面详细介绍这些旋转操作。

右旋

首先找到首个失衡节点，将该节点记作node，其左节点记作child，然后以child为原点将node向右旋转，再用child代替以前node的位置即可。而当child有右节点（记作grand_child）时需要将grand_child作为node的左子节点。

通过修改节点指针可以实现这一操作：

TreeNode *rightRotate(TreeNode*node){
    TreeNode*child,*grandChild;
    child=node->left;
    grandChild=child->right;
    // 以 child 为原点，将 node 向右旋转
    child->right=node;
    node->left=grandChild;
    // 更新节点高度
    updateHeight(node);
    updateHeight(child);
    // 返回旋转后子树的根节点
    return child;
}

左旋

右旋和左旋操作在逻辑上是镜像对称的，它们分别解决的两种失衡情况也是对称的。

TreeNode*leftRotate(TreeNode*node){
    TreeNode*child,*grandChild;
    child=node->right;
    // 以 child 为原点，将 node 向右旋转
    child->left=node;
    node->left=grandchild;
    // 更新节点高度
    updateHeight(node);
    updateHeight(child);
    // 返回旋转后子树的根节点
    return child;
}

旋转的选择

失衡节点的平衡因子	子节点的平衡因子	应采用的旋转方法
>1	>=0	右旋
>1	<0	先左旋后右旋
<-1	<=0	左旋
<-1	>0	右旋

为了便于使用，我们将旋转操作封装成一个函数。有了这个函数，我们就能对各种失衡情况进行旋转，使失衡节点重新恢复平衡。代码如下所示：

TreeNode*rotate(TreeNode*node){
    int bf=balanceFactor(node);
    if(bf>1){
        if(banlanceFactor(node->left)>=0){
            return rightRotate(node);
        }else{
            node->left=leftRotate(node->left);
            return rightRotate(node);
        }
    }
    if(bf<-1){
        if(balanceFactor(node->right)<=0){
            return leftRotate(node);
        }else{
            node->right=rightRotate(node->right);
            return leftRotate(node);
        }
    }
    return node;
}

插入节点

AVL 树的节点插入操作与二叉搜索树在主体上类似。唯一的区别在于，在 AVL 树中插入节点后，从该节点到根节点的路径上可能会出现一系列失衡节点。因此，我们需要从这个节点开始，自底向上执行旋转操作，使所有失衡节点恢复平衡。代码如下所示：

void insert(AVLTree*tree,int val){
    tree->root=insertHelper(tree->root,val);
}
TreeNode*insertHelper(TreeNode,int val){
    if(node=NULL){
        return newTreeNode(val);
    }
    // 查找插入位置并插入节点
    if(val<node->val){
        node->left=insertHelper(node->left,val);
    }else if(val>ndoe->val){
        node->right=insertHelper(node->right,val);
    }else{
        // 重复节点不插入，直接返回
        return node;
    }

    updateHeight(node);
    node=rotate(node);
    return node;
}

删除节点

类似地，在二叉搜索树的删除节点方法的基础上，需要从底至顶执行旋转操作，使所有失衡节点恢复平衡：

void removeItem(AVLTree *tree, int val) {
    TreeNode *root = removeHelper(tree->root, val);
}
TreeNode *removeHelper(TreeNode *node, int val) {
    TreeNode *child, *grandChild;
    if (node == NULL) {
        return NULL;
    }
    
    if (val < node->val) {
        node->left = removeHelper(node->left, val);
    } else if (val > node->val) {
        node->right = removeHelper(node->right, val);
    } else {
        if (node->left == NULL || node->right == NULL) {
            child = node->left;
            if (node->right != NULL) {
                child = node->right;
            }
            // 子节点数量 = 0 ，直接删除 node 并返回
            if (child == NULL) {
                return NULL;
            } else {
                // 子节点数量 = 1 ，直接删除 node
                node = child;
            }
        } else {
            // 子节点数量 = 2 ，则将中序遍历的下个节点删除，并用该节点替换当前节点
            TreeNode *temp = node->right;
            while (temp->left != NULL) {
                temp = temp->left;
            }
            int tempVal = temp->val;
            node->right = removeHelper(node->right, temp->val);
            node->val = tempVal;
        }
    }
    // 更新节点高度
    updateHeight(node);
    node = rotate(node);

    return node;
}

查找节点

AVL 树的节点查找操作与二叉搜索树一致，在此不再赘述。

AVL树典型应用

AVL树适用于高频查找、低频增删的场景。

注：本文是作者阅读《hello算法》一书的读书笔记，内容会与原书有重合，特此声明。