当前位置：首页 > news >正文

AVL树c++实现

news 2025/6/7 22:32:47

AVL树脱胎于二叉搜索树,是平衡的二叉搜索树.

判断一棵树是不是AVL树,首先要判断它是不是二叉搜索树,然后再判断它是否平衡.

判断二叉搜索树的方法我写在这篇博客了:二叉搜索树(BST)的介绍和实现(c++)-CSDN博客

判断平衡的方法涉及到平衡因子(Balance Factor).

平衡因子

每一个节点都有平衡因子,

节点的平衡因子＝该节点右子树高度-该节点左子树高度.

AVL树所有节点的平衡因子只能为0，-1或1.

如果某节点的平衡因子不为上面三个值中的任意一个，就说明AVL树不平衡了.

下面是一棵AVL树:

AVL树的一些规律

假设有一棵高为h的AVL树，它的节点数为n.

n的最大值就是2^h-1(树的形状就会是满二叉树)，

那么n的最小值会是什么呢？

让我们先来看看下面的图,

图中左边表示的是同一高度中节点最少的AVL树,

例如,高度为2的AVL树,最多可以有3个节点,最少可以有2个节点.

上图节点数的规律:

设高度为h的节点数最少的 AVL树的节点数为n(h)(h≥3),

则n(h)＝n(h-1)+n(h-2)+1,

例如上图高度为4的AVL树，它的节点数为7，

7＝2+4+1，

(注意到:高度为2的AVL树节点数为2，

高度为3的AVL树节点数为4)

符合上面我们讲的规律.

数学上的规律可以映射到几何上。

我们观察可以发现，一棵节点数最少的AVL树由一个节点➕它的前两颗树组合而成。

可以联想到斐波那契数列:

1，1，2，3，5，8，13，……

（1+1＝2

1+2＝3

2+3＝5

3+5＝8

……

）

所以我们算复杂度的时候可以用斐波那契数列近似。

博主不擅长数学证明，在这里就不多说了。

如果AVL树不平衡，就该调整平衡，进行一些旋转操作.

AVL树旋转

首先需要明确的一点是,

我们构建AVL树是一个一个节点挂上去的,

只要一不平衡,

就开始调整.

所以两颗子树的高度差等于2就是不平衡,就要开始调整,

下面的图示展示的就是该情况

左单旋

看看下面需要左单旋的情况:

树1本来是一棵AVL树,

但是加上100这个结点,

变成树2之后,

树2不是一棵AVL树了,

这时树2需要进行左单旋来恢复平衡.

b子树的范围是大于5小于8,因此b子树移动成为5的右子树.

这就是抽象出来的左单旋的实现.

右单旋

树1本来是一棵AVL树,

但是加上1这个结点,

变成树2之后,

树2不是一棵AVL树了,

这时树2需要进行右单旋来恢复平衡.

左右双旋

左右单旋的意思是,一棵二叉搜索树不平衡了,先进行左单旋,再进行右单旋才能恢平衡,变成AVL树.

需要进行左右单旋的情况有3种.

情况1

情况2

情况3

右左双旋

情况1

情况2

情况3

AVL树的实现

定义AVL树的节点

template<class T>
struct AVLTreeNode
{AVLTreeNode(const T& data = T()): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}AVLTreeNode<T>* _pLeft; //指向左节点AVLTreeNode<T>* _pRight; //指向右节点AVLTreeNode<T>* _pParent; //指向父节点T _data; //存放数据int _bf;   // 节点的平衡因子,采用右子树高度-左子树高度
};

AVL树类的定义和实现

整体框架

template<class T>
class AVLTree
{typedef AVLTreeNode<T> Node;
public://初始化树AVLTree(): _pRoot(nullptr){}//......中间有很多函数private:Node* _pRoot; //根节点
};

右单旋

void RotateR(Node* pParent){Node* subL = pParent->_pLeft;Node* subLR = subL->_pRight;pParent->_pLeft = subLR;//判断subLR是否为空,不为空就与pParent连接if (subLR){subLR->_pParent = pParent;}Node* parent = pParent->_pParent;//原父节点的父节点subL->_pRight = pParent;pParent->_pParent = subL;if (pParent == _pRoot){_pRoot = subL;subL->_pParent = nullptr;}else{//判断原父节点是它父节点的左孩子还是右孩子,并进行指针更新if (parent->_pLeft == pParent){parent->_pLeft = subL;}else{parent->_pRight = subL;}subL->_pParent = parent;}//调整平衡因子subL->_bf = 0;pParent->_bf = 0;}

左单旋

void RotateL(Node* pParent){Node* subR = pParent->_pRight;Node* subRL = subR->_pLeft;pParent->_pRight = subRL;if (subRL){subRL->_pParent = pParent;}Node* parent = pParent->_pParent;subR->_pLeft = pParent;pParent->_pParent = subR;if (pParent == _pRoot){subR->_pParent = nullptr;_pRoot = subR;}else{if (pParent == parent->_pLeft){parent->_pLeft = subR;}else{parent->_pRight = subR;}subR->_pParent = parent;}subR->_bf = 0;pParent->_bf = 0;}

右左单旋

void RotateRL(Node* pParent){Node* subR = pParent->_pRight;Node* subRL = subR->_pLeft;int bf = subRL->_bf;RotateR(subR);RotateL(pParent);if (bf == 1){subRL->_bf = 0;subR->_bf = 0;pParent->_bf = -1;}else if (bf == -1){subRL->_bf = 0;subR->_bf = 1;pParent->_bf = 0;}else if (bf == 0){subRL->_bf = 0;subR->_bf = 0;pParent->_bf = 0;}else{assert(false);}}

左右单旋

void RotateLR(Node* pParent){Node* subL = pParent->_pLeft;Node* subLR = subL->_pRight;int bf = subLR->_bf;RotateL(subL);RotateR(pParent);if (bf == 1){subLR->_bf = 0;subL->_bf = -1;pParent->_bf = 0;}else if (bf == -1){subLR->_bf = 0;subL->_bf = 0;pParent->_bf = 1;}else if (bf == 0){subLR->_bf = 0;subL->_bf = 0;pParent->_bf = 0;}else{assert(false);}}

插入节点的函数

    // 在AVL树中插入值为data的节点//按二叉搜索树的逻辑插入//检查平衡因子//不平衡再旋转调整bool Insert(const T& data){if (_pRoot == nullptr){_pRoot = new Node(data);return true;}Node* parent = nullptr;Node* cur = _pRoot;while (cur){if (data > cur->_data){parent = cur;cur = cur->_pRight;}else if (data < cur->_data){parent = cur;cur = cur->_pLeft;}else{return false;}}//插入节点并进行连接cur = new Node(data);if (data > parent->_data){parent->_pRight = cur;}else{parent->_pLeft = cur;}cur->_pParent = parent;//更新平衡因子while (parent){if (cur == parent->_pLeft){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_pParent;}else if (parent->_bf == 2 || parent->_bf == -2){if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){RotateL(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;}

查看全文

http://www.xdnf.cn/news/717607.html