devbox
喵喵爱编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】基础：AVL树（平衡二叉树）_avl树 xyz abc

作者：喵喵爱编程 | 2024-07-21 22:54:39

赞

踩

avl树 xyz abc

【数据结构】基础：AVL树（平衡二叉树）

摘要：本文介绍二叉搜索树的改进AVL树（平衡二叉树），将对其概念与实现两部分展开。主要介绍其中的插入过程，其难点主要在于4个旋转过程。这个四个旋转过程，作者从几何特征，平衡因子特征出发，观察其变化情况与细节以及平衡因子的改变。最后进行性能分析的简要介绍。由于删除考察得比较少，因此本文并不对此进行介绍。

文章目录

一、概述

二叉搜索树存在缺点，二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1（需要对树中的结点进行调整），即可降低树的高度，从而减少平均搜索长度。

平衡二叉树（AVL树）可以定义为或者是空树，或者是具有以下性质的二叉搜索树：

  • 它的左右子树都是AVL树
  • 左右子树高度之差（简称平衡因子）的绝对值不超过1（-1/0/1）

使用代码实现时，其定义如下：对于树的节点使用三叉链的方式，其中还包括对应的键值对，在此设计为包括平衡因子，便于后续的实现，代码示例如下：

template<class K,class V>
class AVLTreeNode{
public:
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;

	pair<K, V> _keyValue; // 键值对
	
	int _balanceFactor; // 平衡因子

	AVLTreeNode(const pair<K, V>& keyValue)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_keyValue(keyValue)
		,_balanceFactor(0)
	{}
};

template<class K,class V>
class AVLTree {
	typedef AVLTreeNode<K, V> AVLTreeNode;
private:
	AVLTreeNode* _root;
public:
	AVLTree()
		:_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

二、插入

AVL树的插入是在搜索二叉树的条件下进行改进，从而达到平衡的目的。因此主要基本思想可以分为：

  • 根据二叉搜索树的规则寻找插入位置
  • 调节对应的平衡因子，当平衡因子出现异常时，进行AVL树的修正

2.1 寻找插入位置

该步的方法与搜索二叉树的插入过程相似，首先找出键值对的键找出插入位置，其中记录parent和cur指针，便于在找到后简单的找出与父节点连接的方向以及完成插入节点的parent指针的连接。

if (_root == nullptr) {
    _root = new AVLTreeNode(kv);
    return true;
}
// 根据二叉搜索树的规则寻找插入位置
AVLTreeNode* parent = nullptr;
AVLTreeNode* cur = _root;
while (cur) {
    if (cur->_keyValue.first > kv.first) {
        parent = cur;
        cur = cur->_left;
    }
    else if (cur->_keyValue.first < kv.first) {
        parent = cur;
        cur = cur->_right;
    }
    else {
        return false;
    }
}
// 插入新节点
cur = new AVLTreeNode(kv);
if (parent->_keyValue.first > cur->_keyValue.first) {
    parent->_left = cur;
    cur->_parent = parent;
}
else {
    parent->_right = cur;
    cur->_parent = parent;
}

  • 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

2.2 更新平衡因子

在插入完新节点后，需要对平衡因子进行更新，平衡因子的概念为：左右之树之差，当左子树高时为-1，右子树高时为1，相等为0，其他情况皆为异常状况。

插入新节点后，会影响到的节点，就是新插入节点的祖先们，因为新插入节点改变了这些祖先们子树的高度关系，因此可以通过parent指针来完成更新平衡因子的工作，规则如下：

  • 根据cur插入的位置，对于parent的平衡因子进行更新，当插入在parent的左子树时，balanceFactor需要减少，插入在右子树时需要增加balanceFactor

  • 更新以后，如果parent的平衡因子为0，更新结束。因为平衡因子更新前，parent树只有左子树或者只有右子树，插入新节点后，将空的一边填补，parent的高度不变，对于其祖先没有影响，图示如下：

  • 更新以后，如果parent的平衡因子为±1，说明插入前parent的平衡因子一定为0，插入后被更新成±1，此 时以parent为根的树的高度增加，需要继续向上更新

  • 更新以后，如果parent的平衡因子为±2，则parent的平衡因子违反平衡树的性质，需要对其进行旋转处理

过程代码如下：通过while循环以及parent的更新来完成对祖先的访问

// 更新平衡因子
while (parent){
    //根据cur插入的位置，对于parent的平衡因子进行更新，
    //当插入在parent的左子树时，balanceFactor需要减少，
    //插入在右子树时需要增加balanceFactor
    if (parent->_left == cur) {
        parent->_balanceFactor--;
    }
    else {
        parent->_balanceFactor++;
    }
    if (parent->_balanceFactor == 0) {
        break
    }
    // 继续往上更新
    else if (parent->_balanceFactor == 1 || parent->_balanceFactor == -1) {
        cur = parent;
        parent = parent->_parent;
    }
    else if (parent->_balanceFactor == 2 || parent->_balanceFactor == -2)
        // 对于AVL树平衡因子异常处理
    }
    else{
        // 说明插入更新平衡因子之前，树中平衡因子就有问题了
        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

2.3 异常处理（旋转）

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

  • 新节点插入较高左子树的左侧：右单旋
  • 新节点插入较高右子树的右侧：左单旋
  • 新节点插入较高左子树的右侧：先左单旋再右单旋
  • 新节点插入较高右子树的左侧：先右单旋再左单旋

而这四种的旋转方式，需要符合两个规则分别为：保持搜索树的特性，并且控制平衡，以下对于这四种情况进行分别讲解：

2.3.1 右单旋(RotateR)

几何特征：当新节点插入较高左子树的左侧时，将其需要将其像右旋转，图示如下：

平衡因子特征：parent->_balanceFactor == -2 && cur->_balanceFactor == -1

修改平衡因子：cur->_balanceFactor = parent->_balanceFactor = 0;

旋转意义：将高度较高的子树的最大节点上提为根，将原来的根下移为子树的根，使得高度平衡。如此原来高度为H+2的子树降低为H+1，原来H的子树提高为H+1。

实现过程：

  • 从总体上观察，是将cur的右子树作为了parent的左子树，再将cur的右子树指向parent

    void RotateR(AVLTreeNode* parent) {
    AVLTreeNode* cur = parent->_left;
    AVLTreeNode* curR = cur->_right;

    parent->_left = curR;
    curR->_parent = parent;

    cur->_right = parent;
    parent->_parent = cur;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

  • 对于整棵树的整体已经变化完毕了，但是还需要对树外的指针进行操作，即对于parent的parent也要进行连接。如果parent是根节点就不需要连接，将cur作为根，否则就需要找出链接的子树，并完成相互链接。

    void RotateR(AVLTreeNode* parent) {
    // cur一定存在 无需判断空
    AVLTreeNode* cur = parent->_left;
    AVLTreeNode* curR = cur->_right;
    // 对于parent的parent也要进行连接
    AVLTreeNode* parentParent = parent->_parent;

    parent->_left = curR;
	curR->_parent = parent;

    cur->_right = parent;
    parent->_parent = cur;
	// 如果parent是根节点就不需要连接，将cur作为根
    if (parent == _root) {
        _root = cur;
        _root->_parent == nullptr;
    }
    // 将cur作为根，否则就需要找出链接的子树，并完成相互链接
    else{
        if (parentParent->_left == parent) {
            parentParent->_left = cur;
            cur->_parent = parentParent;
        }
        else {
            parentParent->_right = cur;
            cur->_parent = parentParent;
        }
    }
}

    • 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

  • 由于存在空指针的情况，因此需要对节点的子树进行判断

    void RotateR(AVLTreeNode* parent) {
    AVLTreeNode* cur = parent->_left;
    AVLTreeNode* curR = cur->_right;
    // 对于parent的parent也要进行连接
    AVLTreeNode* parentParent = parent->_parent;

    parent->_left = curR;
    // curR可能为空，因此需要对其进行空指针的判断
    if (curR != nullptr) {
        curR->_parent = parent;
    }
    cur->_right = parent;
    parent->_parent = cur;
	// 如果parent是根节点就不需要连接，将cur作为根
    if (parent == _root) {
        _root = cur;
        _root->_parent == nullptr;
    }
    // 将cur作为根，否则就需要找出链接的子树，并完成相互链接
    else{
        if (parentParent->_left == parent) {
            parentParent->_left = cur;
            cur->_parent = parentParent;
        }
        else {
            parentParent->_right = cur;
            cur->_parent = parentParent;
        }
    }
}

    • 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

  • 最后对平衡因子进行相应的修改

    cur->_balanceFactor = parent->_balanceFactor = 0;

    • 1

  • 完整代码

    void RotateR(AVLTreeNode* parent) {
    AVLTreeNode* cur = parent->_left;
    AVLTreeNode* curR = cur->_right;
    // 对于parent的parent也要进行连接
    AVLTreeNode* parentParent = parent->_parent;

    parent->_left = curR;
    // curR可能为空，因此需要对其进行空指针的判断
    if (curR != nullptr) {
        curR->_parent = parent;
    }
    cur->_right = parent;
    parent->_parent = cur;
	// 如果parent是根节点就不需要连接，将cur作为根
    if (parent == _root) {
        _root = cur;
        _root->_parent == nullptr;
    }
    // 将cur作为根，否则就需要找出链接的子树，并完成相互链接
    else{
        if (parentParent->_left == parent) {
            parentParent->_left = cur;
            cur->_parent = parentParent;
        }
        else {
            parentParent->_right = cur;
            cur->_parent = parentParent;
        }
    }
    cur->_balanceFactor = parent->_balanceFactor = 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
2.3.2 左单旋(RotateL)

几何特征：当新节点插入较高右子树的右侧时，将其需要将其像左旋转，图示如下：

平衡因子特征：parent->_balanceFactor == 2 && cur->_balanceFactor == 1

修改平衡因子：cur->_balanceFactor = parent->_balanceFactor = 0;

旋转意义：将高度较高的子树的最大节点上提为根，将原来的根下移为子树的根，使得高度平衡。如此原来高度为H+2的子树降低为H+1，原来H的子树提高为H+1。

实现过程：与右单旋类似，只是方向不同，在此不做过多赘述

void RotateL(AVLTreeNode* parent) {
    AVLTreeNode* cur = parent->_right;
    AVLTreeNode* curL = cur->_left;

    AVLTreeNode* parentParent = parent->_parent;

    parent->_right = curL;
    if (curL != nullptr) {
        curR->_parent = parent;
    }

    parent->_parent = cur;
    cur->_left = parent;

    if (parent == _root) {
        _root = cur;
        _root->_parent = nullptr;
    }
    else {
        if (parentParent->_left == parent) {
            parentParent->_left = cur;
            cur->_parent = parentParent;
        }
        else {
            parentParent->_right = cur;
            cur->_parent = parentParent;
        }
    }

    cur->_balanceFactor = parent->_balanceFactor = 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
2.3.3 左右双旋(RotateLR)

几何特征：新节点插入较高左子树的右侧，先左单旋再右单旋，图示如下：

在这里插入图片描述

平衡因子特征：parent->_balanceFactor == -2 && cur->_balanceFactor == 1

修改平衡因子：可以通过curR的balanceFactor来判断

  • bf == 0 ，H = 0时，表示插入节点为curR时，此时的平衡因子为皆为0

  • 当H ≠ 0时

    • 当bf == -1 时，cur->_balanceFactor = curR->_balanceFactor = 0以及parent->_balanceFactor = 1

    • 当bf == 1时，parent->_balanceFactor = curR->_balanceFactor = 0以及cur->_balanceFactor = -1

在这里插入图片描述

旋转意义：如果单纯的进行右旋转是无意义的，因为给予给原来根节点的左子树，与cur的左子树相比，旋转后仍然不符合AVL树的规则。为此，先通过左旋转来降低子树的高度，再进行右旋转进行第二次降低高度

实现过程：

  • 获取各个点的指针，便于旋转后进行对平衡因子的修改
  • 左单旋后右单旋
  • 平衡因子修改

完整代码：

void RotateLR(AVLTreeNode* parent) {
	AVLTreeNode* cur = parent->_left;
	AVLTreeNode* curR = cur->_right;
	int bf = curR->_balanceFactor;
	RotateL(cur);
	RotateR(parent);

	if (bf == 1) {
		parent->_balanceFactor = curR->_balanceFactor = 0;
		cur -> _balanceFactor = -1;
	}
	else if (bf == -1) {
		cur -> _balanceFactor = curR->_balanceFactor = 0;
		parent -> _balanceFactor = 1;
	}
	else if (bf == 0){
		cur -> _balanceFactor = curR->_balanceFactor = parent->_balanceFactor = 0;
	}
	else {
		assert(false);
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
2.3.4 右左双旋(RotateRL)

几何特征：新节点插入较高右子树的左侧，先右单旋再左单旋

平衡因子特征：parent->_balanceFactor == 2 && cur->_balanceFactor == -1

修改平衡因子：与左右双旋的分析方法一致，此处不做赘述

  • bf == 0 ，H = 0时，表示插入节点为curR时，此时的平衡因子为皆为0
  • 当H ≠ 0时
    • 当bf == -1 时，parent->_balanceFactor = curR->_balanceFactor = 0以及cur->_balanceFactor = 1
    • 当bf == 1时，cur->_balanceFactor = curR->_balanceFactor = 0以及parent->_balanceFactor = -1

旋转意义：如果单纯的进行左旋转是无意义的，因为给予给原来根节点的右子树，与cur的右子树相比，旋转后仍然不符合AVL树的规则。为此，先通过右旋转来降低子树的高度，再进行左旋转进行第二次降低高度

实现过程：与左右双旋一致，不再赘述

完整代码：

void RotateRL(AVLTreeNode* parent) {
    AVLTreeNode* cur = parent->_right;
    AVLTreeNode* curR = cur->_left;
    int bf = curR->_balanceFactor;

    RotateR(cur);
    RotateL(parent);

    if (bf == -1) {
        parent->_balanceFactor = curR->_balanceFactor = 0;
        cur -> _balanceFactor = 1;
    }
    else if (bf == 1) {
        cur -> _balanceFactor = curR->_balanceFactor = 0;
        parent -> _balanceFactor = -1;
    }
    else if (bf == 0) {
        cur->_balanceFactor = curR->_balanceFactor = parent->_balanceFactor = 0;
    }
    else {
        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

三、验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

  • 验证其为二叉搜索树
  • 验证其为平衡树

3.1 验证搜索树

中序遍历可得到一个有序的序列，就说明为二叉搜索树

public:
	void InOrder() {
		_InOrder(_root);
	}
private:
	void _InOrder(AVLTreeNode* root) {
		if (root == NULL)
			return;

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

3.2 验证其为平衡树

每个节点子树高度差的绝对值不超过1，节点的平衡因子是否计算正确。通过递归法求出树的高度，当平衡因子不符合树的高度差或者平衡因子异常时返回false，代码如下：

private:
	bool _IsBalance(AVLTreeNode* root) {
		if (root == NULL)
			return true;

		// 对当前树进行检查
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);

		if (rightHeight - leftHeight != root->_balanceFactor){
			return false;
		}

		return abs(rightHeight - leftHeight) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}
public:
	int Height(AVLTreeNode* root)
	{
		if (root == NULL)
			return 0;
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}
	bool IsBalance()
	{
		return _IsBalance(_root);
	}

  • 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

四、性能分析

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即log (N)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

五、完整代码

// AVLTree.h
#pragma once
#include <utility>
#include <iostream>
#include <assert.h>
using namespace std;
template<class K, class V>
class AVLTreeNode {
public:
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;

	pair<K, V> _keyValue; // 键值对

	int _balanceFactor; // 平衡因子

	AVLTreeNode(const pair<K, V>& keyValue)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _keyValue(keyValue)
		, _balanceFactor(0)
	{}
};

template<class K, class V>
class AVLTree {
	typedef AVLTreeNode<K, V> AVLTreeNode;
private:
	AVLTreeNode* _root;
private:
	void RotateR(AVLTreeNode* parent) {
		AVLTreeNode* cur = parent->_left;
		AVLTreeNode* curR = cur->_right;
		// 对于parent的parent也要进行连接
		AVLTreeNode* parentParent = parent->_parent;

		parent->_left = curR;
		// curR可能为空，因此需要对其进行空指针的判断
		if (curR != nullptr) {
			curR->_parent = parent;
		}

		cur->_right = parent;
		parent->_parent = cur;

		// 如果parent是根节点就不需要连接，将cur作为根
		if (parent == _root) {
			_root = cur;
			_root->_parent == nullptr;
		}
		// 将cur作为根，否则就需要找出链接的子树，并完成相互链接
		else {
			if (parentParent->_left == parent) {
				parentParent->_left = cur;
				cur->_parent = parentParent;
			}
			else {
				parentParent->_right = cur;
				cur->_parent = parentParent;
			}
		}
		// 平衡因子	
		cur->_balanceFactor = parent->_balanceFactor = 0;
	}
	void RotateL(AVLTreeNode* parent) {
		AVLTreeNode* cur = parent->_right;
		AVLTreeNode* curL = cur->_left;

		AVLTreeNode* parentParent = parent->_parent;

		parent->_right = curL;
		if (curL != nullptr) {
			curL->_parent = parent;
		}

		parent->_parent = cur;
		cur->_left = parent;

		if (parent == _root) {
			_root = cur;
			_root->_parent = nullptr;
		}
		else {
			if (parentParent->_left == parent) {
				parentParent->_left = cur;
				cur->_parent = parentParent;
			}
			else {
				parentParent->_right = cur;
				cur->_parent = parentParent;
			}
		}

		cur->_balanceFactor = parent->_balanceFactor = 0;
	}
	void RotateLR(AVLTreeNode* parent) {
		AVLTreeNode* cur = parent->_left;
		AVLTreeNode* curR = cur->_right;
		int bf = curR->_balanceFactor;
		RotateL(cur);
		RotateR(parent);

		if (bf == 1) {
			parent->_balanceFactor = curR->_balanceFactor = 0;
			cur -> _balanceFactor = -1;
		}
		else if (bf == -1) {
			cur -> _balanceFactor = curR->_balanceFactor = 0;
			parent -> _balanceFactor = 1;
		}
		else if (bf == 0){
			cur -> _balanceFactor = curR->_balanceFactor = parent->_balanceFactor = 0;
		}
		else {
			assert(false);
		}
	}
	void RotateRL(AVLTreeNode* parent) {
		AVLTreeNode* cur = parent->_right;
		AVLTreeNode* curR = cur->_left;
		int bf = curR->_balanceFactor;

		RotateR(cur);
		RotateL(parent);

		if (bf == -1) {
			parent->_balanceFactor = curR->_balanceFactor = 0;
			cur -> _balanceFactor = 1;
		}
		else if (bf == 1) {
			cur -> _balanceFactor = curR->_balanceFactor = 0;
			parent -> _balanceFactor = -1;
		}
		else if (bf == 0) {
			cur->_balanceFactor = curR->_balanceFactor = parent->_balanceFactor = 0;
		}
		else {
			assert(false);
		}
	}
	void _InOrder(AVLTreeNode* root) {
		if (root == NULL)
			return;

		_InOrder(root->_left);
		cout << root->_keyValue.first << ":" << root->_keyValue.second << endl;
		_InOrder(root->_right);
	}
	bool _IsBalance(AVLTreeNode* root) {
		if (root == NULL)
			return true;

		// 对当前树进行检查
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);

		if (rightHeight - leftHeight != root->_balanceFactor){
			//cout << "发生错误：";
			//cout << root->_keyValue.first << " 的平衡因子是:" << root->_balanceFactor 
			//	<< " 应该是:" << rightHeight - leftHeight << endl;
			return false;
		}

		return abs(rightHeight - leftHeight) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}
public:
	AVLTree()
		:_root(nullptr)
	{}
	bool Insert(const pair<K, V>& kv) {
		if (_root == nullptr) {
			_root = new AVLTreeNode(kv);
			return true;
		}
		// 根据二叉搜索树的规则寻找插入位置
		AVLTreeNode* parent = nullptr;
		AVLTreeNode* cur = _root;
		while (cur) {
			if (cur->_keyValue.first > kv.first) {
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_keyValue.first < kv.first) {
				parent = cur;
				cur = cur->_right;
			}
			else {
				return false;
			}
		}
		// 插入新节点
		cur = new AVLTreeNode(kv);
		if (parent->_keyValue.first > cur->_keyValue.first) {
			parent->_left = cur;
			cur->_parent = parent;
		}
		else {
			parent->_right = cur;
			cur->_parent = parent;
		}
		// 更新平衡因子
		while (parent) {
			//根据cur插入的位置，对于parent的平衡因子进行更新，
			//当插入在parent的左子树时，balanceFactor需要减少，
			//插入在右子树时需要增加balanceFactor
			if (parent->_left == cur) {
				parent->_balanceFactor--;
			}
			else {
				parent->_balanceFactor++;
			}
			if (parent->_balanceFactor == 0) {
				break;
			}
			// 继续往上更新
			else if (parent->_balanceFactor == 1 || parent->_balanceFactor == -1) {
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_balanceFactor == 2 || parent->_balanceFactor == -2) {
				// 对于AVL树平衡因子异常处理
				if (parent->_balanceFactor == -2 && cur->_balanceFactor == -1) {
					RotateR(parent);
				}
				else if (parent->_balanceFactor == 2 && cur->_balanceFactor == 1) {
					RotateL(parent);
				}
				else if (parent->_balanceFactor == -2 && cur->_balanceFactor == 1) {
					RotateLR(parent);
				}
				else if (parent->_balanceFactor == 2 && cur->_balanceFactor == -1) {
					RotateRL(parent);
				}
				else {
					assert(false);
				}
				break;
			}
			else {
				// 说明插入更新平衡因子之前，树中平衡因子就有问题了
				assert(false);
			}
		}
		return true;
	}
	void InOrder() {
		_InOrder(_root);
	}
	int Height(AVLTreeNode* root)
	{
		if (root == NULL)
			return 0;
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
};

  • 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

补充：

  1. 代码将会放到：C++/C/数据结构代码链接 ，欢迎查看！
  2. 欢迎各位点赞、评论、收藏与关注，大家的支持是我更新的动力，我会继续不断地分享更多的知识！
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/喵喵爱编程/article/detail/862469
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号