【C++进阶4-AVLTree】尽可能条理清晰地为你讲解比普通BST更强的——AVLTree

今天，带来AVLTree的讲解。文中不足错漏之处望请斧正！

是什么

AVLTree是一种自平衡的二叉搜索树。

它通过控制左右子树的高度差不超过1来调节平衡，从而提高搜索，插入和删除的效率。

实现

结构

AVLTree为了能自动调节平衡，引入了平衡因子(balance factor)的概念，平衡因子由左右子树高度差得来，能衡量当前子树是否平衡。

*平衡因子bf = 右子树高度 - 左子树高度

可得结构。

AVLTree的结点：

• 键值对
• 平衡因子
• 指向左子树的指针
• 指向右子树的指针
• 指向父节点的指针

当平衡因子的绝对值大于1时，就需要进行旋转操作来调整树的平衡。

template<class K, class V>
struct AVLTreeNode
{
    pair<K, V> _kv;
	  int _bf; //balance factor = h_rightTree - h_leftTree
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;
  
    AVLTreeNode(const pair<K, V>& kv)
    :_left(nullptr),
    _right(nullptr),
    _parent(nullptr),
    _kv(kv),
    _bf(0)
    {}
};

作为学习，AVLTree的insert性价比最高。我们可以通过insert的实现，了解AVLTree是如何调节平衡的，这就够了。

template<class K, class V>
class AVLTree
{
    typedef AVLTreeNode<K, V> Node;
public:
	bool Insert(pair<K, V> kv)
	{
			//TODO
	}

	void InOrder()
    {
        InOrder(_root);
    }
    
    void InOrder(Node* root)
    {
        if(root == nullptr) return;
        
        InOrder(root->_left);
        cout << root->_kv.first << ":" << root->_kv.second << endl;
        InOrder(root->_right);
    }
private:
		Node* _root = nullptr;

insert

和以往的二叉搜索树一样，AVLTree插入需要找位置并利用parent指针插入，不过多了更新bf和调节平衡的步骤。

1. 找位置
2. 插入
3. 更新bf
4. 需要则调整平衡

1. 找位置

	bool Insert(pair<K, V> kv)
    {
        if(_root == nullptr)
        {
            _root = new Node(kv);
            return true;
        }
        
        //找位置：小走左，大走右
        Node* cur = _root; 
        Node* parent = nullptr; 
        while(cur)
        {
            if(kv.first < cur->_kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if(kv.first > cur->_kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(kv.first == cur->_kv.first)
            {
                return false;
            }
            else
            {
                assert(false);
            }
        }
        
        //插入
		//TODO
        
        //更新bf
		//TODO

		//需要则调整平衡
        
        return true;
    }

2. 插入

	bool Insert(pair<K, V> kv)
    {
        if(_root == nullptr)
        {
            _root = new Node(kv);
            return true;
        }
        
        //找位置：小走左，大走右
        Node* cur = _root; 
        Node* parent = nullptr; 
        while(cur)
        {
            if(kv.first < cur->_kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if(kv.first > cur->_kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(kv.first == cur->_kv.first)
            {
                return false;
            }
            else
            {
                assert(false);
            }
        }
        
        //插入
		cur = new Node(kv);
        if(kv.first < parent->_kv.first)
        {
            parent->_left = cur;
            cur->_parent = parent;
        }
        else//cur == parent->_left
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
        
        //更新bf
		//TODO

		//需要则调整平衡
        
        return true;
    }

3. 更新bf

• 在某个结点parent的左边插入，则--parent→_bf
• 在某个结点parent的右边插入，则++parent→_bf

3.1 向上调整

这还没完，因为此次插入可能引起当前子树的高度变化，且当前子树的根结点可能并不是整棵树的根结点，所以当前子树高度变化是很有可能向上影响的。

• 插入后高度不变，不会向上影响：插入结束
• 插入后高度变化，会向上影响：向上更新bf

且插入后可能已经将AVLTree的规则破坏——左右子树高度差超过1。

• 插入后高度差过大：调整平衡（规则破坏）

那如何判断当前子树高度是否变化呢？

• 插入后bf为0（左右高度一样） = 插入前bf为1/-1（一边高一边矮）
  • 即此情况插入新结点后，把矮的一边填上了，不影响当前子树高度
• 插入后bf为1/-1（一边高一边矮） = 插入前bf为0（左右高度一样）
  • 即此情况插入新结点后，使得当前子树高度增加了
• 插入后bf为2/-2（有一边已经过高） = 需要调节平衡

参考代码如下：

		while(parent)
        {
            if(cur == parent->_right)
                ++parent->_bf;
            else
                --parent->_bf;

            //高度不变
            if(parent->_bf == 0)
            {
                break;
            }
            //高度变化
            else if(parent->_bf == 1 || parent->_bf == -1)
            {
                //向上调整
                cur = parent;
                parent = cur->_parent;
            }
            //高度差过大
            else if(parent->_bf == 2 || parent->_bf == -2)
            {
                //调平衡
				//TODO
            }
        }

现在就到了最关键的问题：如何调平衡。

既然是高度差大，那我就解决你的高度问题，把价格打下来！不是，把高度降下来！

怎么降？

4. 旋转调平衡

旋转能够很好地降低子树高度，调节平衡。插入结点后树的状态有无数种，但对其整理分类后，可以抽象出4种情况。每种状态使用1-2种旋转解决。

注：我们称某棵子树的

• 根结点为parent
• 左子树为subL
• 左子树的右子树为subLR
• 右子树为subR
• 右子树的左子树为subRL

不平衡有四种情况：

1. 整体左高：parent的左子树高 + subL的左子树高
2. 整体右高：parent的右子树高 + subR的右子树高
3. 整体左高+局部右高：parent的左子树高 + subL的右子树高
4. 整体右高+局部左高：parent的右子树高 + subR的左子树高

分别对应共四种旋转：

右单旋

R单旋可以解决纯左高的情况。

事出有因

来看看parent的左子树高，subL的左子树高是怎么样的。

插入前：

插入后：

*a、b、c都是抽象的一棵树，它们各自有无限种状态，但高度为h

*结点旁的数字是当前节点的bf

见见猪跑

我们先不纠结R单旋是什么，而是来见见猪跑，意会。

我们把subL看成准备加冕的王子，parent看成准备隐退的国王。

抽象旋转图（体现链接变化）

抽象旋转图（体现位置变化）

*我们还需要考虑subL变成整棵树的根的情况，这会在L单旋侧重讲解，现在理解好连接关系和位置变化。

我们发现，就按照这样旋转：subL的右子树变成parent的左子树，parent变成subL的右子树，subL变成当前子树的根。恰好就能降低左子树的高度，而且不打破BST规则！

• 降低高度：左子树整体向上走了
• 不打破BST规则：subL的右子树是subL为根的子树中，最大的一个；在旋转后，恰好可以当做parent中最小的一个

在旋转后，我们还需要更新一下被动过的子树的bf：subL和parent的bf都变为0。

具象旋转图

h==0

parent→_bf == -2 ，需要旋转。

理解旋转时的位置变化：

旋转完毕。

h==1

理解旋转时的链接变化

理解旋转时的位置变化

参考代码

	void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        
        //1.subLR变成parent的左
        //subLR可能是空
        parent->_left = subLR;
        if(subLR)
            subLR->_parent = parent;
        
        //2.parent变成subL的右
        //考虑到parent可能不是根而是parent->_parent的子树，所以保存grandParent，以便上层可以链当前子树
        Node* grandParent = parent->_parent;
        subL->_right = parent;
        parent->_parent = subL;
        
        //3.subR变成根
				...
        
        //adjust bf
        subL->_bf = parent->_bf = 0;
    }

左单旋

L单旋可以解决纯右高的情况。

事出有因

来看看parent的右子树高 + subR的右子树高怎么来的。

插入前：

插入后：

*不管是在b抽象树下插入，还是在c抽象树插入，用L单旋都能解决。这里就不一一演示了。

见见猪跑

抽象旋转图

1. subR把右子树b托付给parent：b变成parent的右子树

2.subR加冕、parent隐退：parent变成subR的左子树

1. subR变成根

有两种情况：

在旋转后，我们还需要更新一下被动过的子树的bf：subR和parent的bf都变为0。

具象旋转图就不画了，其他和R单旋的讲解一样，主要是子树变为新的根，需要注意有两种情况。

参考代码

	void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        
        //1. subRL变成parent的右子树
        parent->_right = subRL;
        if(subRL) subRL->_parent = parent;
        
        //2. parent变成subR的左子树
        Node* pParent = parent->_parent;
        subR->_left = parent;
        parent->_parent = subR;
        
        //3. subR变成根
        if(pParent == nullptr)
        {
            _root = subR;
            _root->_parent = nullptr;
        }
        else
        {
            if(parent == pParent->_left)
                pParent->_left = subR;
            else
                pParent->_right = subR;
            
            subR->_parent = pParent;
        }
        
        //adjust bf
        parent->_bf = subR->_bf = 0;
    }

右左双旋

事出有因

局部(subR)左子树高，整体(parent)右子树高，需要RL双旋：以subR为根进行R单旋；再以parent为根L单旋。

插入前：

插入后：

见见猪跑

1. subRL本身就是新增

即subRL->bf = 0。

这种情况，bf的变化为：

• parent->_bf = 0;
• subR->_bf = 0;
• subRL->_bf = 0;

2. 在subRL的左子树(b)新增

即subRL->bf = -1。

抽象：

具象：

这种情况，bf的变化为：

• parent->_bf = 0;
• subR->_bf = 1;
• subRL->_bf = 0;

3. 在subRL的右子树(c)新增

即subRL->bf = 1。

抽象：

这种情况，bf的变化为：

• parent->_bf = -1;
• subR->_bf = 0;
• subRL->_bf = 0;

参考代码

	void RotateRL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subRL->_bf;
        
        RotateR(subR);
        RotateL(parent);
        
        //1. subLR就是新增
        if(bf == 0)
        {
            parent->_bf = 0;
            subR->_bf = 0;
            subRL->_bf = 0;
        }
        //2. 在subLR的左新增
        else if(bf == -1)
        {
            parent->_bf = 0;
            subR->_bf = 1;
            subRL->_bf = 0;
        }
        //3. 在subLR的右新增
        else if(bf == 1)
        {
            parent->_bf = -1;
            subR->_bf = 0;
            subRL->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

左右双旋

事出有因

插入后局部(subL)右子树高，整体(parent)左子树高，需要LR双旋：以subL为根进行L单旋；再以parent为根R单旋。

插入前：

插入后：

见见猪跑

1. subLR本身就是新增

即subLR→_bf == 0：

bf变化：

• parent: 0→0
• subL: 1→0
• subLR: 0→0

2. 在subLR的左边(b)新增

即subLR→_bf == -1：

bf变化：

• parent: -2→1
• subL: 1→0
• subLR: -1→0

3. 在subLR的右边(c)新增

即subLR→_bf == 1：

bf变化：

• parent: -2→0
• subL: 1→-1
• subLR: -1→0

参考代码

	void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        int bf = subLR->_bf;
        
        //局部右高，先对subL左单旋
        RotateL(subL);
        //整体纯左高，对parent右单旋
        RotateR(parent);
        
        //更新bf
        //1. subLR就是新增
        if(bf == 0)
        {
            parent->_bf = 0;
            subL->_bf = 0;
            subLR->_bf = 0;
        }
        //2. 在subLR的左新增
        else if(bf == -1)
        {
            parent->_bf = 1;
            subL->_bf = 0;
            subLR->_bf = 0;
        }
        //3. 在subLR的右新增
        else if(bf == 1)
        {
            parent->_bf = 0;
            subL->_bf = -1;
            subLR->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

旋转为什么能降高度？

根据整体和局部的子树过高情况，我们会选择用某种旋转。比如在这里，是整体左高，那么选择右单旋：subL的右子树托付给parent，parent隐退，subL加冕。subL从原来的parent→left，变为新的parent，subL的左子树变成了新的subL。

这样一来，左子树整体向上移动，高度降了，而原来subL的右子树是subL局部子树中最大的，恰好是位置轮换后parent局部子树中最小的，也不打破BST规则。

整体参考代码（附测试方法）

//
// Created by Bacon on 2023/4/21.
//

#ifndef MAP_SET_AVLTREE_H
#define MAP_SET_AVLTREE_H

template <class K, class V>
struct AVLTreeNode {
    AVLTreeNode<K, V> *_parent;
    AVLTreeNode<K, V> *_left;
    AVLTreeNode<K, V> *_right;
    pair<K, V> _kv;
    int _bf;

    AVLTreeNode(const pair<K, V> &kv)
            :_parent(nullptr),
             _left(nullptr),
             _right(nullptr),
             _kv(kv),
             _bf(0)
    {}
};

template <class K, class V>
class AVLTree {
    typedef AVLTreeNode<K, V> Node;
public:
    bool insert(const pair<K, V> &kv) {
        if (_root == nullptr) {
            _root = new Node(kv);
            return true;
        }

        //1. 找位置
        Node *cur = _root;
        Node *parent = nullptr;
        while (cur) {
            parent = cur;
            if (kv.first < cur->_kv.first) {
                cur = cur->_left;
            } else if (kv.first > cur->_kv.first) {
                cur = cur->_right;
            } else if (kv.first == cur->_kv.first) {
                return false;
            } else { assert(false);}
        }

        //2. 插入
        cur = new Node(kv);
        cur->_parent = parent;
        if (kv.first < parent->_kv.first)
            parent->_left = cur;
        else
            parent->_right = cur;

        //3. 调整bf，需要则旋转
        while (parent) {
            if (cur == parent->_left)
                --parent->_bf;
            else
                ++parent->_bf;

            if (parent->_bf == 0) {
                break; //不向上影响则不调整
            } else if (parent->_bf == 1 || parent->_bf == -1) {
                cur = parent;
                parent = cur->_parent;
            } else if (parent->_bf == 2 || parent->_bf == -2) {
                if (parent->_bf ==  2 && cur->_bf ==  1) rotateL(parent);
                if (parent->_bf == -2 && cur->_bf == -1) rotateR(parent);
                if (parent->_bf == -2 && cur->_bf ==  1) rotateLR(parent);
                if (parent->_bf ==  2 && cur->_bf == -1) rotateRL(parent);
                break;
            } else { assert(false);}
        }
        return true;
    }

private:
    void rotateL(Node *parent) {
        Node *subR = parent->_right;
        Node *subRL = subR->_left;
        Node *grandParent = parent->_parent;

        //1. subRL变成parent的右子树
        parent->_right = subRL;
        if (subRL) subRL->_parent = parent;

        //2. parent变成subR的左子树
        subR->_left = parent;
        parent->_parent = subR;

        //3. subR变成局部根或整体根
        if (grandParent == nullptr) { //整体根
            _root = subR;
            _root->_parent = nullptr;
        } else { //局部根
            subR->_parent = grandParent;
            if (parent == grandParent->_left) grandParent->_left = subR;
            if (parent == grandParent->_right) grandParent->_right = subR;
        }
        parent->_bf = subR->_bf = 0;
    }

    void rotateR(Node *parent) {
        Node *subL = parent->_left;
        Node *subLR = subL->_right;
        Node *grandParent = parent->_parent;

        //1. subLR变成parent的左
        parent->_left = subLR;
        if (subLR) subLR->_parent = parent;

        //2. parent变成subL的右
        subL->_right = parent;
        parent->_parent = subL;

        //3. subL变成局部根或整体根
        if (grandParent == nullptr) { //整体根
            _root = subL;
            _root->_parent = nullptr;
        } else { //局部根
            subL->_parent = grandParent;
            if (parent == grandParent->_left) grandParent->_left = subL;
            if (parent == grandParent->_right) grandParent->_right = subL;
        }
        parent->_bf = subL->_bf = 0;
    }

    void rotateLR(Node *parent) {
        Node *subL = parent->_left;
        Node *subLR = subL->_right;
        int bf = subLR->_bf; //旋转后subLR的bf会变，我们就没法判断了，所以提前保存

        rotateL(subL);
        rotateR(parent);

        if (bf == 0) {
            parent->_bf = 0;
            subL->_bf = 0;
            subLR->_bf = 0;
        } else if (bf == -1) {
            parent->_bf = 1;
            subL->_bf = 0;
            subLR->_bf = 0;
        } else if (bf == 1) {
            parent->_bf = 0;
            subL->_bf = -1;
            subLR->_bf = 0;
        } else { assert(false);}
    }

    void rotateRL(Node *parent) {
        Node *subR = parent->_right;
        Node *subRL = subR->_left;
        int bf = subRL->_bf;

        rotateR(subR);
        rotateL(parent);

        if (bf == 0) {
            parent->_bf = 0;
            subR->_bf = 0;
            subRL->_bf = 0;
        } else if (bf == -1) {
            parent->_bf = 0;
            subR->_bf = 1;
            subRL->_bf = 0;
        } else if(bf == 1) {
            parent->_bf = -1;
            subR->_bf = 0;
            subRL->_bf = 0;
        } else { assert(false);}
    }

public:
    void InOrder() { InOrder(_root);}
    bool IsBalanceTree() { return IsBalanceTree(_root);}
private:
    void InOrder(Node* root) {
        if(root == nullptr) return;

        InOrder(root->_left);
        cout << root->_kv.first << ":" << root->_kv.second << endl;
        InOrder(root->_right);
    }

    int Height(Node* root) {
        if(root == nullptr) return 0;

        int leftH = Height(root->_left);
        int rightH = Height(root->_right);

        return leftH > rightH ? leftH + 1 : rightH + 1;
    }

    bool IsBalanceTree(Node* root) {
        if(root == nullptr) return true;

        int leftH = Height(root->_left);
        int rightH = Height(root->_right);

        if(rightH - leftH != root->_bf) {
            cout << root->_kv.first <<"的平衡因子异常" << endl;
            return false;
        }

        return abs(leftH - rightH) <= 1
               && IsBalanceTree(root->_left)
               && IsBalanceTree(root->_right);
    }
private:
    Node *_root = nullptr;
};

void testAVLTree()
{
//    int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
    int a[] = {0, 4, 2, 3, 1, 9, 6, 7, 8, 5};
    AVLTree<int, int> t;
    for(auto e : a) {
//        if(e == 7) //调试技巧：若7的平衡因子有问题，就这么写
//            int x;
        t.insert(make_pair(e, e));
        printf("insert %d:%d\n", e, e);
        t.InOrder();
        cout << t.IsBalanceTree() << endl;
    }
    t.InOrder();
    cout << t.IsBalanceTree() << endl;
}

#endif //MAP_SET_AVLTREE_H

今天的分享就到这里了，感谢您能看到这里。

这里是培根的blog，期待与你共同进步！文章来源地址https://www.toymoban.com/news/detail-466427.html

到了这里，关于【C++进阶4-AVLTree】尽可能条理清晰地为你讲解比普通BST更强的——AVLTree的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！