Cruyun's Blog

Talk is cheap, show you my code

AVL Tree

• 标签: Algorithm, Data-struture

AVL树又称为平衡二叉树，即Balanced Binary Tree或者Height-Balanced Tree，它或者是一棵空二叉树，或者是具有如下性质的二叉查找树：其左子树和右子树都是高度平衡的二叉树，且左子树和右子树的高度之差的绝对值不超过1。

如何判断一个树是平衡二叉树？

在查阅资料时发现LeetCode上面的这道题，我的 Accepted 代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool isBalanced(TreeNode* root) {
        return depth(root) == -1 ? false : true;
    }
    
    int depth(TreeNode* root) {
       if (root == NULL)
           return 0;
        
        int h1 = depth(root->left);
        if (h1 == -1)
            return -1;
        int h2 = depth(root->right);
        if (h2 == -1)
            return -1;
        
        int diff = abs(h1 - h2);
        
        if (diff > 1) 
            return -1;
        else
            return 1 + max(h1, h2);
    }

使用递归的方式，假如为null的话该节点的depth为-1，遍历得到各节点的左子树和右子树的高度。这里没有写成if (h1 == -1 || h2 == -1) return -1；是因为如果左子树不平衡的话就不必检查右子树了，这棵树一定是不平衡的。

AVL Tree Rotations 平衡二叉树的调整

判断是否为平衡二叉树的重要因素是节点的左子树和右子树的高度差，定义为“平衡因子BF(Balanced Factor）”。

每次插入新节点时，找到离该节点最近的非平衡节点（左右子树的高度差大于1），进行旋转操作。

具体是以下四种旋转方式：

  • Left Rotation 左旋
  • Right Rotation 右旋
  • Left-Right Rotation 左旋后右旋
  • Right-Left Rotation 右旋后左旋

Left Rotation 左旋

LL Rotation.png

当新插入的节点为右子树的右子节点时，找到离3最近的不平衡节点1，以1为轴进行左旋的操作。

1
2
3
4
5
6
7
8
avl_node *avlTree::ll_rotation(avl_node *parent)
{
    avl_node *temp;
    temp = parent->left;
    parent->left = temp->right;
    temp->right = parent;
    return temp;
}

Right Rotation 右旋

RR Rotation.png

当新插入的节点为左子树的左子节点时，找到离1最近的不平衡节点3，以3为轴进行右旋的操作。

1
2
3
4
5
6
7
8
avl_node *avlTree::rr_rotation(avl_node *parent)
{
    avl_node *temp;
    temp = parent->right;
    parent->right = temp->left;
    temp->left = parent;
    return temp;
}

Left-Right Rotation 左旋后右旋

LR Rotation.png

假若某节点被插入到了左子树的右节点，首先以1为轴旋转，然后以3为轴旋转。

1
2
3
4
5
6
7
avl_node *avlTree::lr_rotation(avl_node *parent)
{
    avl_node *temp;
    temp = parent->left;
    parent->left = rr_rotation (temp);
    return ll_rotation (parent);
}

Right-Left Rotation 右旋后左旋

RL Rotation.png

假若某节点被插到右子树的左节点，首先以3为轴旋转，再以1为轴旋转。

1
2
3
4
5
6
7
avl_node *avlTree::rl_rotation(avl_node *parent)
{
    avl_node *temp;
    temp = parent->right;
    parent->right = ll_rotation (temp);
    return rr_rotation (parent);
}

Operations on an AVL Tree 平衡二叉树的操作（查找、插入、删除）

查找 Search Operation

在AVL tree中，查找操作的时间复杂度是O(log n)，它的查找操作类似于二叉查找树。

  1. 读取用户输入的根节点
  2. 对比判断这个节点是否为根节点
  3. 假如相等，则返回
  4. 假如不等，与该节点比较大小，若比根节点小，则与根节点的左子树比较，否则与右子树比较
  5. 重复34过程直到找到或者子树为空

插入 Insertion Operation

在AVL tree中，插入操作的时间复杂度是O(log n)，查找操作一般都是插入为子节点。

  1. 以二叉查找树的插入操作相同的方法插入节点
  2. 插入之后，检查每一个节点的平衡因子
  3. 假如每个平衡因子都是0 -1 或 1，则该树仍平衡
  4. 假如有任意一个节点的平衡因子不是0 -1 或1，说明不平衡，选取上述的四种操作进行调整

比如下图：

insert.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
avl_node *avlTree::insert(avl_node *root, int value)
{
    if (root == NULL)
    {
        root = new avl_node;
        root->data = value;
        root->left = NULL;
        root->right = NULL;
        return root;
    }
    else if (value < root->data)
    {
        root->left = insert(root->left, value);
        root = balance (root);
    }
    else if (value >= root->data)
    {
        root->right = insert(root->right, value);
        root = balance (root);
    }
    return root;
}

删除 Deletion Operation

在AVL tree中，删除的操作同样类似于二叉查找树，与之不同的是，我们需要每次删除之后判断是否为平衡二叉树，假如不平衡的话需要作出调整。

参考资料：