数据结构-平衡二叉树（AVL Tree）

梦里梦外; 2022-07-24 06:16 224阅读 0赞

在[ 数据结构-二叉树(binary tree)-二叉查找树(binary search tree)][_-_binary tree_-_binary search tree] 的最后面，提到过在二叉树中增加或者删除节点，可能导致树的左右子树高度相差很多，即导致树不平衡。为了解决这个问题，规定在插入或者删除节点的时候，必须保证每一个节点的左右子树的高度差的绝对值不超过1，| height(left) - height(right) | <= 1。这样的二叉树称为平衡二叉树（AVL Tree）。定义左右子树的高度差的绝对值为**平衡因子**。

![这里写图片描述][311739112822613.png]  
来源：[http://www.cnblogs.com/zhuwbox/p/3636783.html][http_www.cnblogs.com_zhuwbox_p_3636783.html]

## 判断AVL Tree ##

根绝平衡二叉树的定义，可以很容易实现判断二叉树是否为平衡二叉树

bool IsBalanced1 (Node *root)
    {
        if (root == NULL) return true;
    
        int left = TreeHeight(root->left);
        int right = TreeHeight(root->right);
        int diff = left - right;
        if (diff < -1 || diff > 1)
            return false;
        else
            return (IsBalanced1(root->left) && IsBalanced1(root->left));
    }

这个方法通过先计算左右子树的高度，再判断二叉树是否为二叉树。方便理解，但是这种方法访问了很多次某些节点，特别是越接近叶节点的节点。在计算整棵树的高度时访问了所有的节点，接着又分别计算以根节点的左右子节点为根节点的二叉树高度，再次访问了除根节点以外的所有节点，如此导致大量重复访问。一棵平衡二叉树的任意一个子树也都是一个平衡二叉树，因此可以考虑从下往上遍历，如果发现一棵子树不是平衡二叉树，那么整棵树肯定不是平衡二叉树，如此减少大量的重复访问。

bool IsBalanced2 (Node *root, int& depth)
    {
        if (root == NULL) {
            depth = 0;
            return true;
        }
    
        int left, right;
        if (IsBalanced2(root->left, left) && IsBalanced2(root->right, right)) {
            int diff = left - right;
            if (diff >= -1 && diff <= 1) {
                depth = 1 + (left > right ? left : right);
                return true;
            }
        }
        return false;
    }

当插入或者删除操作破坏了二叉树的平衡性，需要进行一些相关操作，将其调整为平衡二叉树，相关操作包括：单旋转和双旋转。

## 单旋转-右旋（RR） ##

![右旋][20160515221812260]

在B的左子树中插入新元素后，导致A节点的平衡因子变为2，二叉树不再平衡。以B节点为中心向右旋转，使得B节点上升一层，A节点下降一层，从而将二叉树重新调整为平衡二叉树。

Node* SingleRotateRight (Node* node1) {
    
        Node *node2 = node1->right;
        node1->right = node2->left;
        node2->left = node1;
    
        node1->height = max ( Height (node1->left), Height (node1->right)) + 1;
        node2->height = max ( Height (node2->right), node1->height) + 1;
    
        return node2;
    }

## 单旋转-左旋（LL） ##

左旋操作与右旋操作相似：  
![这里写图片描述][20160516194102503]

//node1: node which is not balanced
    Node* SingleRotateLeft (Node* node1) {
    
        Node *node2 = node1->left;
        node1->left = node2->right;
        node2->right = node1;
    
        node1->height = max ( Height (node1->left), Height (node1->right)) + 1;
        node2->height = max ( Height (node2->left), node1->height) + 1;
    
        return node2;
    }

### 双旋-左旋+右旋(LR) ###

考虑如下图的情况，此时右单旋转不能解决问题，问题从A节点不平衡转移到了B节点不平衡。

![这里写图片描述][20160516195609663]

所以要进行**左右双旋转(LR)**。  
![这里写图片描述][20160516201855215]

// LR rotate
    Node* DoubleRotateRight (Node *node1) {
    
        node1->right = SingleRotateLeft (node1->right);
    
        return SingleRotateright (node1);
    
    }

### 双旋-右旋+左旋（RL） ###

与上述情况类似，在某些情况下需要进行RL操作。  
![这里写图片描述][20160516203613942]

//RL rotate
    Node* DoubleRotateLeft (Node *node1) {
    
        node1->left = SingleRotateRight (node1->left);
    
        return SingleRotateLeft (node1);
    
    }

综合所有操作

typedef struct node
    {
        int val;
        int height;
        struct node *left;
        struct node *right;
    } Node;
    
    bool IsBalanced1 (Node *root)
    {
        if (root == NULL) return true;
    
        int left = TreeHeight(root->left);
        int right = TreeHeight(root->right);
        int diff = left - right;
        if (diff < -1 || diff > 1)
            return false;
        else
            return (IsBalanced1(root->left) && IsBalanced1(root->left));
    }
    
    bool IsBalanced2 (Node *root, int& depth)
    {
        if (root == NULL) {
            depth = 0;
            return true;
        }
    
        int left, right;
        if (IsBalanced2(root->left, left) && IsBalanced2(root->right, right)) {
            int diff = left - right;
            if (diff >= -1 && diff <= 1) {
                depth = 1 + (left > right ? left : right);
                return true;
            }
        }
        return false;
    }
    
    
    void Insert (Node* root, int val) {
    
        if (root == NULL) {
    
            root = (Node*)malloc(sizeof(Node));
            if (root == NULL) {
                printf("space error!\n");
                return root;
            } else {
                root->val = val;
                root->left = root->right = NULL;
                root->height = 0;
            }
        } else if (val < root->val){
            root->left  = Insert (root->left, val);
            if (Height (root->left) - Height (root->right) == 2) {
                if (val < root->left->val)
                    root = SingleRotateLeft (root);
                else
                    root = DoubleRotateLeft (root);
            }
    
        } else if (val > root->val) {
            root->right = Insert (root->right, val);
            if (Height(root->right) - Height (root->left) == 2) {
                if (val > root->right->val)
                    root = SingleRotateRight (root);
                else
                    root = DoubleRotateRight (root);
            }
        }
    }
    
    int Height (Node* root) {
        if(root == NULL)
            return -1;
        else
            return root->height;
    }
    
    //node1: node which is not balanced
    Node* SingleRotateLeft (Node* node1) {
    
        Node *node2 = node1->left;
        node1->left = node2->right;
        node2->right = node1;
    
        node1->height = max ( Height (node1->left), Height (node1->right)) + 1;
        node2->height = max ( Height (node2->left), node1->height) + 1;
    
        return node2;
    }
    
    //RL rotate
    Node* DoubleRotateLeft (Node *node1) {
    
        node1->left = SingleRotateRight (node1->left);
    
        return SingleRotateLeft (node1);
    
    }
    
    Node* SingleRotateRight (Node* node1) {
    
        Node *node2 = node1->right;
        node1->right = node2->left;
        node2->left = node1;
    
        node1->height = max ( Height (node1->left), Height (node1->right)) + 1;
        node2->height = max ( Height (node2->right), node1->height) + 1;
    
        return node2;
    }
    
    // LR rotate
    Node* DoubleRotateRight (Node *node1) {
    
        node1->right = SingleRotateLeft (node1->right);
    
        return SingleRotateright (node1);
    
    }

[_-_binary tree_-_binary search tree]: http://blog.csdn.net/juanqinyang/article/details/51363644
[311739112822613.png]: /images/20220722/c16a5ff1541344e99cc091c8a22ed904.png
[http_www.cnblogs.com_zhuwbox_p_3636783.html]: http://www.cnblogs.com/zhuwbox/p/3636783.html
[20160515221812260]: /images/20220722/3d61dcce57714753b4ffd071f7cd9915.png
[20160516194102503]: /images/20220722/51a0ca75e1334e3caaeaf0cf2d5caae0.png
[20160516195609663]: /images/20220722/938590822c3b42bbae35e2151b00ea57.png
[20160516201855215]: /images/20220722/4c20a50dff3d4c4193c94f6dd43718c2.png
[20160516203613942]: /images/20220722/7cfebfb461d3423f809e33cca266a93f.png