C++模拟实现AVL树

目录

1.文章概括

2.AVL树概念

3.AVL树的性质

4.AVL树的插入

5.旋转控制

1.左单旋

2. 右单旋

3.左右双旋

4.右左双旋

6.全部代码

---

1.文章概括

        本文适合理解平衡二叉树的读者阅读，因为AVL树是平衡二叉树的一种优化，其大部分实现逻辑与平衡二叉树是相同的，相同的部分不做过多阐述。

2.AVL树概念

        平衡二叉树主要用于查找数据，可提高查找效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。在这样的缺点下，AVL树被发明了出来。AVL树的优化点在于：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1（需要对树中的结点进行调整），即可降低树的高度，从而减少平均搜索长度。

3.AVL树的性质

        一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

1.它的左右子树都是AVL树；

2.左右子树高度之差（简称平衡因子）的绝对值不超过1（-1,0,1）。

AVL树 == 高度平衡二叉搜索树，说是平衡，为什么不是相等？

因为高度差不超过1，不是高度相等。

AVL树图片示例：

        如此控制后，增删改查的时间复杂度即为高度次 == O(logN)。

4.AVL树的插入

        对于一个结点的插入，分析如下：

1.新增在该结点的左，parent平衡因子减减；

2.新增在该结点的右，parent平衡因子加加；

3.更新后parent平衡因子 == 0，说明parent所在的子树的高度不变，不会再影响祖先，不用再沿着到root的路径往上更新；

4.更新后parent平衡因子 == 1 or -1，说明parent所在的子树的高度变化，会再影响祖先，需要沿着到root的路径往上更新；

5.更新后parent平衡因子 == 2 or -2，说明parent所在的子树的高度变化且不平衡，对parent所在子树进行旋转，让它平衡；

6.更到根结点。

补充说明：执行到4时会从1,2,开始继续循环，执行到3,5,6时插入结束。

旋转时需要注意的问题：

1.保持它是搜索树；

2.变成平衡树且降低这个子树的高度。

代码：

bool Insert(const T& data){Node* parent = nullptr;Node* cur = _pRoot;if (cur == nullptr){cur = new Node(data);_pRoot = cur;}while (cur){if (cur->_data > data){parent = cur;cur = cur->_pLeft;}else if (cur->_data < data){parent = cur;cur = cur->_pRight;}elsereturn false;}cur = new Node(data);if (parent->_data > data){parent->_pLeft = cur;cur->_pParent = parent;}else{parent->_pRight = cur;cur->_pParent = parent;}while (parent){if (parent->_pLeft == cur)parent->_bf--;elseparent->_bf++;if (parent->_bf == 0)return true;else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_pParent;}else{if (cur->_bf == 1 && parent->_bf == 2){RotateL(parent);}else if (cur->_bf == -1 && parent->_bf == -2){RotateR(parent);}else if (cur->_bf == -1 && parent->_bf == 2){RotateRL(parent);}else if (cur->_bf == 1 && parent->_bf == -2){RotateLR(parent);}break;}}}

        代码中，我使用了平衡因子来控制这棵树的高度。

5.旋转控制

1.左单旋

新节点插入较高右子树的右侧 --- 右右：

2. 右单旋

新节点插入较高左子树的左侧 --- 左左

3.左右双旋

 新节点插入较高左子树的右侧---左右：

4.右左双旋

新节点插入较高右子树的左侧 --- 右左：

6.全部代码

#pragma once
#include <iostream>
#include <assert.h>
#include <vector>
using namespace std;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){}// 在AVL树中插入值为data的节点bool Insert(const T& data){Node* parent = nullptr;Node* cur = _pRoot;if (cur == nullptr){cur = new Node(data);_pRoot = cur;}while (cur){if (cur->_data > data){parent = cur;cur = cur->_pLeft;}else if (cur->_data < data){parent = cur;cur = cur->_pRight;}elsereturn false;}cur = new Node(data);if (parent->_data > data){parent->_pLeft = cur;cur->_pParent = parent;}else{parent->_pRight = cur;cur->_pParent = parent;}while (parent){if (parent->_pLeft == cur)parent->_bf--;elseparent->_bf++;if (parent->_bf == 0)return true;else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_pParent;}else{if (cur->_bf == 1 && parent->_bf == 2){RotateL(parent);}else if (cur->_bf == -1 && parent->_bf == -2){RotateR(parent);}else if (cur->_bf == -1 && parent->_bf == 2){RotateRL(parent);}else if (cur->_bf == 1 && parent->_bf == -2){RotateLR(parent);}break;}}}// AVL树的验证bool IsAVLTree(){return _IsAVLTree(_pRoot);}private:// 根据AVL树的概念验证pRoot是否为有效的AVL树bool _IsAVLTree(Node* root){if (root == nullptr)return true;int leftHight = Height(root->_pLeft);int rightHight = Height(root->_pRight);if (rightHight - leftHight != root->_bf){cout << "平衡因子异常:" << root->_data << "->" << root->_bf << endl;return false;}return abs(rightHight - leftHight) < 2&& _IsAVLTree(root->_pLeft)&& _IsAVLTree(root->_pRight);}size_t Height(Node* root){if (root == nullptr)return 0;int leftHeight = Height(root->_pLeft);int rightHeight = Height(root->_pRight);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}// 右单旋void RotateR(Node* pParent) {Node* cur = pParent->_pLeft;Node* curRight = cur->_pRight;Node* parentP = pParent->_pParent;pParent->_pLeft = curRight;if(curRight)curRight->_pParent = pParent;cur->_pRight = pParent;pParent->_pParent = cur;if (parentP == nullptr){_pRoot = cur;cur->_pParent = nullptr;}else{cur->_pParent = parentP;if (parentP->_pLeft == pParent)parentP->_pLeft = cur;elseparentP->_pRight = cur;}if(curRight)curRight->_bf = 0;pParent->_bf = cur->_bf = 0;}// 左单旋void RotateL(Node* pParent){Node* cur = pParent->_pRight;Node* curLeft = cur->_pLeft;Node* parentP = pParent->_pParent;pParent->_pRight = curLeft;if(curLeft)curLeft->_pParent = pParent;cur->_pLeft = pParent;pParent->_pParent = cur;if (parentP == nullptr){_pRoot = cur;cur->_pParent = nullptr;}else{cur->_pParent = parentP;if (parentP->_pLeft == pParent)parentP->_pLeft = cur;elseparentP->_pRight = cur;}if(curLeft)curLeft->_bf = 0;pParent->_bf = cur->_bf = 0;}// 右左双旋void RotateRL(Node* pParent){Node* cur = pParent->_pRight;Node* curLeft = cur->_pLeft;int temp = curLeft->_bf;RotateR(cur);RotateL(pParent);if (temp == 0)return;else if (temp == 1){pParent->_bf = -1;cur->_bf = 0;curLeft->_bf = 0;}else if (temp == -1){pParent->_bf = 0;cur->_bf = 1;curLeft->_bf = 0;}elseassert(false);}// 左右双旋void RotateLR(Node* pParent){Node* cur = pParent->_pLeft;Node* curRight = cur->_pRight;int temp = curRight->_bf;RotateL(cur);RotateR(pParent);if (temp == 0)return;else if (temp == 1){pParent->_bf = 0;cur->_bf = -1;curRight->_bf = 0;}else if (temp == -1){pParent->_bf = 1;cur->_bf = 0;curRight->_bf = 0;}elseassert(false);}private:Node* _pRoot;
};