• 【C++入门到精通】C++入门 —— AVL 树（自平衡二叉搜索树）

    在这里插入图片描述

    阅读导航

    前言

    前面我们讲了C语言的基础知识，也了解了一些初阶数据结构，并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载，引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象’ ，也了解了C++中的模版，以及学习了几个STL的结构也相信大家都掌握的不错，接下来博主将会带领大家继续学习有关C++比较重要的知识点—— AVL 树（自平衡二叉搜索树） 。下面话不多说坐稳扶好咱们要开车了😍

    一、AVL树的概念

    AVL树是一种自平衡的二叉搜索树，它在插入或删除节点时通过旋转操作来保持树的平衡。AVL树的名称来自发明者 Adelson-Velsky 和 Landis 的姓氏的首字母。

    在AVL树中，每个节点都有一个平衡因子（balance factor），表示其左子树高度和右子树高度之间的差值。平衡因子可以是-1、0或1，如果平衡因子的绝对值超过1，则该节点被认为是不平衡的。
    在这里插入图片描述

    ⭕AVL树维护以下性质：

    1. 树的每个节点的平衡因子必须在-1、0和1之间。
    2. 所有左子树的高度与右子树的高度之差的绝对值不超过1。
    3. 如果它有n个结点，其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2​n)，搜索时间复杂度O( l o g 2 n log_2 n log2​n)

    当向AVL树中插入或删除节点时，可能会破坏树的平衡。为了恢复平衡，AVL树使用四种旋转操作：左旋、右旋、左右旋和右左旋。通过这些旋转操作，AVL树可以在插入或删除操作后保持平衡，从而提供较为稳定和高效的搜索、插入和删除操作。

    由于AVL树的自平衡特性，它适用于需要频繁插入和删除操作的场景，尤其是对于需要快速搜索和有序遍历的数据集合。如果一棵二叉搜索树是高度平衡的，它就是AVL树。

    二、AVL树节点的定义

    AVL树的节点定义包括以下几个属性：

    1. 值：每个节点存储的值，可以是任意类型，通常是一个关键字或数据。

    2. 左子节点指针：指向当前节点的左子节点的指针。左子节点的值应该小于或等于当前节点的值。

    3. 右子节点指针：指向当前节点的右子节点的指针。右子节点的值应该大于当前节点的值。

    4. 父节点指针：指向当前节点的父节点的指针。根节点的父节点指针为空。

    5. 平衡因子：表示当前节点的左子树高度和右子树高度之差。平衡因子可以为-1、0或1。

    下面是一个示例代码来定义一个AVL树的节点结构：

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    三、AVL树的插入

    AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

    1. 按照二叉搜索树的方式插入新节点
    2. 调整节点的平衡因子

    下面是AVL树的插入的基本算法：

    • 如果AVL树为空，将新节点作为根节点插入，并更新其高度和平衡因子。
    • 如果插入的值小于当前节点的值，则将其插入到当前节点的左子树中。如果左子节点为空，直接插入；否则，递归执行插入操作。
    • 如果插入的值大于当前节点的值，则将其插入到当前节点的右子树中。如果右子节点为空，直接插入；否则，递归执行插入操作。
    • 在递归返回的过程中，更新每个节点的高度和平衡因子，然后检查平衡因子是否超过了范围。
      如果发现平衡因子超出范围，进行旋转操作来修复平衡。

    下面是一个基于C++实现的AVL树插入算法的伪代码：

    bool Insert(const pair<K, V>& kv)
{
    if (_root == nullptr)
    {
        // 如果根节点为空，创建新节点作为根节点，并返回插入成功
        _root = new Node(kv);
        return true;
    }

    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_kv.first < kv.first)
        {
            // 当前节点的键值小于插入节点的键值，继续向右子树查找
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_kv.first > kv.first)
        {
            // 当前节点的键值大于插入节点的键值，继续向左子树查找
            parent = cur;
            cur = cur->_left;
        }
        else
        {
            // 当前节点的键值等于插入节点的键值，插入失败（不允许键值重复）
            return false;
        }
    }

    // 创建新节点并插入到树中
    cur = new Node(kv);
    if (parent->_kv.first > kv.first)
    {
        parent->_left = cur;
    }
    else
    {
        parent->_right = cur;
    }
    cur->_parent = parent;

    // 更新平衡因子
    while (parent)
    {
        if (cur == parent->_right)
        {
            parent->_bf++; // 右子树增加一个节点，平衡因子加1
        }
        else
        {
            parent->_bf--; // 左子树增加一个节点，平衡因子减1
        }

        if (parent->_bf == 1 || parent->_bf == -1)
        {
            // 平衡因子为1或-1，说明子树高度增加，继续更新父节点的平衡因子
            parent = parent->_parent;
            cur = cur->_parent;
        }
        else if (parent->_bf == 0)
        {
            // 平衡因子为0，说明子树高度没有变化，不需要进行旋转操作，结束循环
            break;
        }
        else if (parent->_bf == 2 || parent->_bf == -2)
        {
            // 平衡因子为2或-2，需要进行旋转处理来恢复平衡

            if (parent->_bf == 2 && cur->_bf == 1)
            {
                RotateL(parent); // 左旋
            }
            else if (parent->_bf == -2 && cur->_bf == -1)
            {
                RotateR(parent); // 右旋
            }
            else if (parent->_bf == -2 && cur->_bf == 1)
            {
                RotateLR(parent); // 先左旋再右旋
            }
            else if (parent->_bf == 2 && cur->_bf == -1)
            {
                RotateRL(parent); // 先右旋再左旋
            }
            else
            {
                assert(false); // 不应该出现的情况
            }

            break;
        }
        else
        {
            assert(false); // 不应该出现的情况
        }
    }

    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102

    ⭕代码解释：

    1. 首先检查根节点是否为空，在空树中直接创建新节点作为根节点。
    2. 如果不是空树，则通过循环在适当的位置找到插入节点应该放置的父节点。
    3. 在插入节点时，根据父节点的键值与插入节点的键值的比较结果，确定插入节点是父节点的左子节点还是右子节点。
    4. 更新插入节点的父指针，并更新父节点及其祖先节点的平衡因子。
    5. 根据平衡因子的变化情况，决定是否需要进行旋转操作来调整树的平衡。
    6. 旋转操作分为左旋、右旋、先左旋再右旋和先右旋再左旋四种情况，具体根据平衡因子的值来确定。

    四、AVL树的旋转（重点）

    1. 右单旋（新节点插入较高左子树的左侧）

    • 右单旋是AVL树的一种旋转操作，用于解决插入节点位于较高左子树的左侧的情况。

    下面是右单旋的具体实现代码：

    void RotateR(Node* parent)
{
    Node* subL = parent->_left;    // 获取父节点的左子节点
    Node* subLR = subL->_right;    // 获取左子节点的右子节点
    Node* ppnode = parent->_parent;    // 获取父节点的父节点

    parent->_left = subLR;    // 将左子节点的右子节点作为父节点的左子节点
    if (subLR)
        subLR->_parent = parent;    // 更新左子节点的右子节点的父指针

    subL->_right = parent;    // 将父节点作为左子节点的右子节点
    parent->_parent = subL;    // 更新父节点的父指针

    if (parent == _root)
    {
        _root = subL;    // 如果原父节点是根节点，更新根节点
        _root->_parent = nullptr;
    }
    else
    {
        if (ppnode->_left == parent)
        {
            ppnode->_left = subL;    // 如果原父节点是其父节点的左子节点，更新父节点的左子节点
        }
        else
        {
            ppnode->_right = subL;    // 如果原父节点是其父节点的右子节点，更新父节点的右子节点
        }
        subL->_parent = ppnode;    // 更新左子节点的父指针
    }
    subL->_bf = parent->_bf = 0;    // 更新平衡因子
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    ⭕具体而言，右单旋的操作步骤如下：

    1. 获取当前节点的左子节点，并将其保存在变量 subL 中。
    2. 获取左子节点的右子节点，并将其保存在变量 subLR 中。
    3. 获取当前节点的父节点，并将其保存在变量 ppnode 中。
    4. 将左子节点的右子节点作为当前节点的左子节点。
    5. 如果左子节点的右子节点存在，则将其父指针更新为当前节点。
    6. 将当前节点作为左子节点的右子节点。
    7. 更新当前节点的父指针为左子节点。
    8. 如果当前节点是根节点，则更新根节点为左子节点，并将根节点的父指针置为空。
    9. 如果当前节点不是根节点，则根据其在父节点的位置，更新父节点的相应子节点为左子节点，并将左子节点的父指针更新为父节点。
    10. 将左子节点和当前节点的平衡因子都设置为0，表示树已经平衡。

    右单旋操作通过对节点间的指针进行调整，重新平衡了AVL树的结构。这样做的目的是保持AVL树的平衡性，从而提高树的查询和插入等操作的效率。

    2. 左单旋（新节点插入较高右子树的右侧）

    • 左单旋是AVL树的一种旋转操作，用于解决插入节点位于较高右子树的右侧的情况。

    下面是左单旋的具体实现代码：

    void RotateL(Node* parent)
{
    // 保存父节点的右子节点
    Node* subR = parent->_right;
    // 保存右子节点的左子节点
    Node* subRL = subR->_left;
    // 保存父节点的父节点
    Node* ppnode = parent->_parent;

    // 将右子节点的左子节点作为父节点的右子节点
    parent->_right = subRL;
    if (subRL)
        subRL->_parent = parent;

    // 将父节点作为右子节点的左子节点
    subR->_left = parent;
    parent->_parent = subR;

    // 判断原父节点是否为根节点
    if (ppnode == nullptr) 
    {
        // 更新根节点为右子节点
        _root = subR;
        // 将新根节点的父指针置为空
        _root->_parent = nullptr;
    }
    else
    {
        // 判断原父节点是其父节点的左子节点还是右子节点
        if (ppnode->_left == parent)
        {
            // 更新父节点的左子节点为右子节点
            ppnode->_left = subR;
        }
        else
        {
            // 更新父节点的右子节点为右子节点
            ppnode->_right = subR;
        }
        // 更新右子节点的父指针为父节点的父节点
        subR->_parent = ppnode;
    }

    // 将父节点和右子节点的平衡因子都设置为0，表示树已经平衡
    parent->_bf = subR->_bf = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    ⭕具体而言，左单旋的操作步骤如下：

    1. 保存了需要进行旋转操作的父节点、父节点的右子节点和右子节点的左子节点。

    2. 更新父节点的右子节点为右子节点的左子节点，并将右子节点的左子节点的父指针指向父节点。

    3. 将父节点的父指针指向右子节点，并将右子节点的左子节点指向父节点。

    4. 判断原父节点是否为根节点，若是，更新根节点为右子节点，并将新根节点的父指针置为空；若不是，根据父节点在其父节点的位置，分别更新其父节点的左子节点或右子节点为右子节点，并将右子节点的父指针指向父节点的父节点。

    5. 最后，将父节点和右子节点的平衡因子都设置为0，表示树已经平衡。

    3. 先左单旋再右单旋（新节点插入较高左子树的右侧）

    在这里插入图片描述
    将双旋变成单旋后再旋转，即：先对30这个节点进行左单旋，然后再对90这个节点进行右单旋，旋转完成后再考虑平衡因子的更新。

    下面是先左单旋再右单旋的具体实现代码：

    void RotateLR(Node* parent)
{
	// 获取节点C的左子节点A和节点A的右子节点D
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	// 获取节点D的平衡因子，以便后续调整平衡因子时使用
	int bf = subLR->_bf;

	// 对节点A进行左单旋，注意此时节点C的左子节点为节点D，节点D的右子节点为节点A
	RotateL(parent->_left);

	// 对节点C进行右单旋，此时节点D成为新的子树头节点，节点C成为节点D的右子节点
	RotateR(parent);

	// 调整平衡因子
	if (bf == 1) // 如果节点D的平衡因子为1，说明节点D的左子树比右子树高
	{
		parent->_bf = 0; // 节点C的平衡因子变为0
		subLR->_bf = 0; // 节点D的平衡因子变为0
		subL->_bf = -1; // 节点A的平衡因子变为-1，因为它的右子树高度比左子树高度大1
	}
	else if (bf == -1) // 如果节点D的平衡因子为-1，说明节点D的右子树比左子树高
	{
		parent->_bf = 1; // 节点C的平衡因子变为1
		subLR->_bf = 0; // 节点D的平衡因子变为0
		subL->_bf = 0; // 节点A的平衡因子变为0，因为它的左右子树高度相等
	}
	else if (bf == 0) // 如果节点D的平衡因子为0，说明节点D的左右子树高度相等
	{
		parent->_bf = 0; // 节点C的平衡因子变为0
		subLR->_bf = 0; // 节点D的平衡因子变为0
		subL->_bf = 0; // 节点A的平衡因子变为0，因为它的左右子树高度相等
	}
	else // 如果节点D的平衡因子不是1、-1或者0，则说明AVL树已经失去了平衡，这是一个不合法的状态，应该立即报错退出程序。
	{
		assert(false);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    ⭕具体而言，先左单旋再右单旋的操作步骤如下：

    • 首先获取节点C的左子节点A（subL）和节点A的右子节点D（subLR）；
    • 然后对节点A进行左单旋（RotateL），此时节点C的左子节点应为节点D，节点D的右子节点应为节点A；
    • 最后对节点C进行右单旋（RotateR），此时节点D成为新的子树头节点，节点C成为节点D的右子节点。

    最后一部分使用了if语句判断旋转后各个节点的平衡因子，并进行相应的调整，以便使AVL树保持平衡。

    • 如果节点D的平衡因子为1，说明节点D的左子树比右子树高，需要进行右旋操作，这一次旋转中节点C和节点A都向右移动了一位，而节点D的平衡因子变为0，节点A和节点C的平衡因子都变为-1；
    • 如果节点D的平衡因子为-1，说明节点D的右子树比左子树高，需要进行左旋操作，这一次旋转中节点C和节点A都向左移动了一位，而节点D的平衡因子变为0，节点A和节点C的平衡因子都变为1；
    • 如果节点D的平衡因子为0，说明节点D的左右子树高度相等，不需要进行旋转操作，各个节点的平衡因子均设置为0；
    • 如果节点D的平衡因子不是1、-1或者0，则说明AVL树已经失去了平衡，这是一个不合法的状态，应该立即报错退出程序。
    • 经过这两次旋转后，AVL树重新保持了平衡性和有序性。

    4. 先右单旋再左单旋（新节点插入较高右子树的左侧）

    在这里插入图片描述
    将双旋变成单旋后再旋转，即：先对90这个节点进行右单旋，然后再对30这个节点进行左单旋，旋转完成后再考虑平衡因子的更新。

    下面是先右单旋再左单旋的具体实现代码：

    void RotateRL(Node* parent)
{
	// 获取节点C的右子节点B和节点B的左子节点E
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	// 获取节点E的平衡因子，以便后续调整平衡因子时使用
	int bf = subRL->_bf;

	// 对节点B进行右单旋，注意此时节点C的右子节点为节点E，节点E的左子节点为节点B
	RotateR(parent->_right);

	// 对节点C进行左单旋，此时节点E成为新的子树头节点，节点C成为节点E的左子节点
	RotateL(parent);

	// 调整平衡因子
	if (bf == 1) // 如果节点E的平衡因子为1，说明节点E的左子树比右子树高
	{
		parent->_bf = -1; // 节点C的平衡因子变为-1
		subRL->_bf = 0; // 节点E的平衡因子变为0
		subR->_bf = 0; // 节点B的平衡因子变为0，因为它的左右子树高度相等
	}
	else if (bf == -1) // 如果节点E的平衡因子为-1，说明节点E的右子树比左子树高
	{
		parent->_bf = 0; // 节点C的平衡因子变为0
		subRL->_bf = 0; // 节点E的平衡因子变为0
		subR->_bf = 1; // 节点B的平衡因子变为1，因为它的右子树高度比左子树高度大1
	}
	else if (bf == 0) // 如果节点E的平衡因子为0，说明节点E的左右子树高度相等
	{
		parent->_bf = 0; // 节点C的平衡因子变为0
		subRL->_bf = 0; // 节点E的平衡因子变为0
		subR->_bf = 0; // 节点B的平衡因子变为0，因为它的左右子树高度相等
	}
	else // 如果节点E的平衡因子不是1、-1或者0，则说明AVL树已经失去了平衡，这是一个不合法的状态，应该立即报错退出程序。
	{
		assert(false);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    具体过程跟先左单旋再右单旋的过程一样，只不过是顺序有所不一样，这里就不多赘述了。

    五、AVL树的删除（了解）

    AVL树节点的删除是一个相对复杂的操作，需要考虑多种情况来保持树的平衡性，下面是对它的步骤简单的介绍：

    1. 首先，按照二叉搜索树的规则找到需要删除的节点。如果目标节点不存在，则删除操作结束。

    2. 如果删除的节点是叶子节点（没有子节点），可以直接删除它。此时，只需将其父节点指向它的指针置为空即可。

    3. 如果删除的节点有一个子节点，可以用子节点替代删除的节点。此时，只需将删除节点的父节点指向删除节点的子节点，并删除删除节点。

    4. 如果删除的节点有两个子节点，需要选择一个合适的替代节点来代替删除的节点。一般可以选择删除节点的中序遍历前驱或后继节点作为替代节点。

    5. 选择中序遍历的前驱节点作为替代节点的一种常见策略是：在删除节点的左子树上找到最大的节点，它将成为替代节点。如果选择后继节点作为替代节点，则在删除节点的右子树上找到最小的节点。

    6. 将选择的替代节点的值复制到删除的节点上，并删除替代节点。这样相当于删除了目标节点，但保持了二叉搜索树的结构。

    7. 此时可能导致树失去平衡，需要进行平衡调整。从替代节点的父节点开始，向上遍历到根节点，在每个遍历的节点上根据需要进行左旋、右旋或双旋转等操作。

    8. 在每个遍历节点上，需要更新其高度和平衡因子。如果删除节点后，遍历节点的平衡因子绝对值大于1，则需要进行旋转操作来恢复平衡。

    9. 最后，验证树是否仍然满足AVL树的平衡性和二叉搜索树的性质。可以从根节点开始递归地检查每个节点的平衡因子是否在[-1, 1]的范围内，且左子树的所有节点值小于节点值，右子树的所有节点值大于节点值。

    🚨🚨注意：AVL树的节点删除可能触发多次旋转以保持树的平衡，这可能导致性能开销较大。因此，在实际应用中，可以考虑使用其他平衡二叉搜索树的变种，如红黑树，它在插入和删除操作上可能更加高效。后面博主也会对红黑树进行详细的介绍。

    六、AVL树的性能

    1. 查找操作：AVL树是一种二叉搜索树，查找操作的平均时间复杂度为O( l o g n log n logn)，其中n是树中节点的数量。由于AVL树保持了平衡性，树的高度较低，因此在大多数情况下，查找操作非常高效。

    2. 插入和删除操作：由于插入和删除操作可能引起树的不平衡，需要进行旋转操作来恢复平衡。这些旋转操作的时间复杂度为O( 1 1 1)或O( l o g n log n logn)，但由于旋转操作只在沿着路径上最多影响O( l o g n log n logn)个节点，所以插入和删除操作的平均时间复杂度仍然是O( l o g n log n logn)。

    3. 空间复杂度：AVL树与普通二叉搜索树相比，需要额外存储平衡因子来维护树的平衡性。平衡因子通常使用一个额外的字节来表示，因此额外的空间消耗也是O( n n n)。

    4. 平衡维护开销：当进行插入和删除操作时，AVL树需要保持树的平衡性，这可能导致一系列旋转操作。这些旋转操作的开销取决于树的深度和失衡点的位置。在最坏情况下，进行插入和删除操作时可能需要进行O( l o g n log n logn)次旋转操作，因此平衡维护的开销相对较高。

    附：详细的AVL模拟代码

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

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(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;
		}

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

		cur = new Node(kv);
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		// 更新平衡因子
		while (parent)
		{
			if (cur == parent->_right)
			{
				parent->_bf++;
			}
			else
			{
				parent->_bf--;
			}

			if (parent->_bf == 1 || parent->_bf == -1)
			{
				// 继续更新
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				// 需要旋转处理 -- 1、让这颗子树平衡 2、降低这颗子树的高度
				if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				else
				{
					assert(false);
				}

				break;
			}
			else
			{
				assert(false);
			}
		}

		return true;
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	bool IsBalance()
	{
		return _IsBalance(_root);
	}

	int Height()
	{
		return _Height(_root);
	}
private:

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}
	int _Height(Node* root)
	{
		if (root == NULL)
			return 0;

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

		return leftH > rightH ? leftH + 1 : rightH + 1;
	}
	bool _IsBalance(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) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);

	}
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* ppnode = parent->_parent;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		subR->_left = parent;
		parent->_parent = subR;
		if (ppnode == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subR;
			}
			else
			{
				ppnode->_right = subR;
			}
			subR->_parent = ppnode;
		}
		parent->_bf = subR->_bf = 0;
	}
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* ppnode = parent->_parent;
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		subL->_right = parent;
		parent->_parent = subL;
		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}
		subL->_bf = parent->_bf = 0;
	}
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);

		if (bf == 1)
		{
			parent->_bf = 0;
			subLR->_bf = 0;
			subL->_bf = -1;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subLR->_bf = 0;
			subL->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subLR->_bf = 0;
			subL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

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

	}


	Node* _root = nullptr;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300

    温馨提示

    感谢您对博主文章的关注与支持！另外，我计划在未来的更新中持续探讨与本文相关的内容，会为您带来更多关于C++以及编程技术问题的深入解析、应用案例和趣味玩法等。请继续关注博主的更新，不要错过任何精彩内容！

    再次感谢您的支持和关注。期待与您建立更紧密的互动，共同探索C++、算法和编程的奥秘。祝您生活愉快，排便顺畅！
    在这里插入图片描述

  • 相关阅读:
    Design Pattern —— 创建型 —— 单例模式（上） ——概念特点、面试常问、具体实践案例、源码解读
    blender UV展开
    【计算机网络】深入理解TCP协议的三次握手和四次挥手 一、前言
    文件操作和IO
    YOLOv5算法进阶改进（5）— 主干网络中引入SCConv | 即插即用的空间和通道维度重构卷积
    连接mysql和索引优化
    谷歌掀桌子！开源Gemma：可商用，性能超过Llama 2！
    C语言字符函数和字符串函数
    抖音店铺列表接口h5
    第四章-并发与同步思考题
  • 原文地址：https://blog.csdn.net/m0_75215937/article/details/133478988