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

C++：AVL树的实现

news 2024/10/26 11:27:49

AVL的代码

Gitee_AVL的实现代码

一、定义与性质

定义：AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
性质：

它的左右子树都是AVL树。
节点的左子树不为空，平衡因子-1，右子树不为空，平衡因子+1。
任意节点的左子树和右子树的高度差（平衡因子）的绝对值不超过1（-1、0或1）。
当该树的平衡因子等于二或负二的时候要进行调整。
增删查改的效率为O(logN)。

当树里有平衡因子等于2或-2时，就需要进行调整了。

二、AVL树的节点结构

需要一个链接左右子树的指针和父节点的指针，一个变量_data来存储数据，一个平衡因子来判断是否要进行调整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树支持常见的二叉搜索树操作，如插入、删除和搜索。在执行这些操作时，AVL树会根据节点的平衡因子进行自平衡调整。

若不熟悉二叉搜索树可以看这篇文章->数据结构：详解搜索二叉树-CSDN博客

平衡方法：AVL树通过四种旋转操作来维持平衡：

右旋转（Right Rotation）：当某个节点的左子树高度较高时，通过右旋转来降低左子树的高度。
左旋转（Left Rotation）：当某个节点的右子树高度较高时，通过左旋转来降低右子树的高度。
左右旋转（Left-Right Rotation）：当某个节点的左子树的右子树高度较高时，通过先对左子树进行左旋转，再对根节点进行右旋转来调整树的平衡。
右左旋转（Right-Left Rotation）：当某个节点的右子树的左子树高度较高时，通过先对右子树进行右旋转，再对根节点进行左旋转来调整树的平衡。

1、右旋转

出现下面这种情况需要用左旋转来调整AVL树，确保节点的平衡因子不为2或-2。

这里我们需要将 p 节点的左子树链接 s 节点的右子树，s 节点的右子树链接 p 节点。其中还需要注意父节点的链接。我们可以发现 p 节点的平衡因子变为零，s 节点也变为零。调整完的结果应该像下面这样。

void RotateR(Node* parent)
{Node* pParent = parent->_pParent;Node* subL = parent->_pLeft;Node* subLR = subL->_pRight;subL->_pParent = pParent;if (pParent){if (pParent->_pLeft == parent)pParent->_pLeft = subL;elsepParent->_pRight = subL;}else{_pRoot = subL;subL->_pParent = pParent;}subL->_pRight = parent;parent->_pParent = subL;parent->_pLeft = subLR;if (subLR){subLR->_pParent = parent;}subL->_bf = 0;parent->_bf = 0;
}

2、左旋转

基本同理，转为下面这样

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

3、左右旋转

先对 sl 节点进行一次左旋转

再对 p 节点进行一次右旋转

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

4、右左旋转

右左旋转的图形就与左右旋转的图形类似。~~这里偷个懒就不画了~~

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