C++简单实现AVL树

目录

一、AVL树的概念

二、AVL树的性质

三、AVL树节点的定义

四、AVL树的插入

4.1 parent的平衡因子为0

4.2 parent的平衡因子为1或-1

4.3 parent的平衡因子为2或-2

4.3.1 左单旋

4.3.2 右单旋

4.3.3 先左单旋再右单旋

4.3.4 先右单旋再左单旋

4.4 插入节点完整代码：

五、AVL树判断是否平衡

六、AVL树的验证

---

一、AVL树的概念

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

二、AVL树的性质

1、空树也是一颗AVL树

2、它的左右子树都是AVL树

3、左右子树高度差（平衡因子）的绝对值不超过1

4、如果一颗二叉搜索树是高度平衡的，它就是AVL树。如果它由N个节点，其高度可保持在O(log2N)，搜索时间复杂度为O(log2N)。

三、AVL树节点的定义

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode(const pair<K, V>& kv):_kv(kv),_parent(nullptr),_left(nullptr),_right(nullptr),_bf(0)//平衡因子初始为0{}pair<K, V> _kv;AVLTreeNode* _parent;AVLTreeNode* _left;AVLTreeNode* _right;int _bf;//平衡因子 —— balance factor
};

四、AVL树的插入

AVL树的插入分为两大步：

1、新建节点，插入到正确的位置（使之符合二叉搜索树的性质）

如果插入到右边，则平衡因子加1，如果插入到左边，平衡因子减1；

2、判断平衡因子是否合法，不合法则调整节点（旋转）

插入完成后平衡因子有以下几种情况：

4.1 parent的平衡因子为0

如果此时parent的平衡因子为0，那么之前的平衡因子是1或-1，这棵树的高度不会变，不用向上更新，插入完成。

4.2 parent的平衡因子为1或-1

如果此时parent的平衡因子为1或-1，那么之前的平衡因子为0，高度改变了，需要向上更新。

4.3 parent的平衡因子为2或-2

如果此时parent的平衡因子为2或-2，那么需要通过旋转调平衡。

4.3.1 左单旋

    void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;cur->_left = parent;if (curleft)curleft->_parent = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;//更新平衡因子}

4.3.2 右单旋

    void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;cur->_right = parent;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}

4.3.3 先左单旋再右单旋

    void RotateLR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(parent->_left);RotateR(parent);//更新平衡因子if (bf == 0){parent->_bf = curright->_bf = cur->_bf = 0;}else if (bf == 1){parent->_bf = 0;cur->_bf = -1;curright = 0;}else if (bf == -1){parent->_bf = 1;cur->_bf = 0;curright = 0;}else{assert(false);}}

4.3.4 先右单旋再左单旋

    void RotateRL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;RotateR(parent->_right);RotateL(parent);//更新平衡因子if (bf == 0){parent->_bf = curleft->_bf = cur->_bf = 0;}else if (bf == 1){parent->_bf = -1;cur->_bf = 0;curleft = 0;}else if (bf == -1){parent->_bf = 0;cur->_bf = 1;curleft = 0;}else{assert(false);}}

4.4 插入节点完整代码：

    bool insert(const pair<K, V>& kv){//如果root为空if (_root == nullptr){_root = new Node(kv);return true;}//插入Node* cur = _root;Node* parent = cur;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->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//刚开始忘记写了//插入完成，开始判断是否平衡//最坏走到根就不再判断了，根的parent为空while (parent){//更新平衡因子if (parent->_left == cur){parent->_bf--;}else{parent->_bf++;}//如果此时parent的平衡因子为0，那么之前的平衡因子是1或-1，这棵树的高度不会变，不用向上更新if (parent->_bf == 0){break;}//如果此时parent的平衡因子为1或-1，那么之前的平衡因子为0，高度改变了，需要向上更新else if (parent->_bf == 1 || parent->_bf == -1){//向上更新cur = parent;parent = parent->_parent;}//如果此时parent的平衡因子为2或-2，那么需要通过旋转调平衡else if (parent->_bf == 2 || parent->_bf == -2){//左单旋if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}//右单旋if(parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}//先右单旋，再左单旋if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}//先左单旋，再右单旋if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}break;//忘记写了}else{assert(false);}}return true;}

五、AVL树判断是否平衡

    bool isBalance(){return _isBalance(_root);}int Height(Node* root){if (root == nullptr)return 0;int lh = Height(root->_left);int rh = Height(root->_right);return lh > rh ? lh + 1 : rh + 1;}bool _isBalance(Node* root){if (root == nullptr)return true;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);int diff = abs(rightHeight - leftHeight);return diff <= 1 && _isBalance(root->_left) && _isBalance(root->_right);}

六、AVL树的验证

int main()
{//常规场景AVLTree<int, int>* root1 = new AVLTree<int, int>();int a1[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };for (auto e : a1){root1->insert(make_pair(e, e));}root1->InOrder();cout << "isBalance: " << root1->isBalance() << endl;//特殊场景AVLTree<int, int>* root2 = new AVLTree<int, int>();int a2[] = { 4,2,6,1,3,5,15,7,16,14 };for (auto e : a2){root2->insert(make_pair(e, e));}root2->InOrder();cout << "isBalance: " << root2->isBalance() << endl;//随机数const int N = 100000;vector<int> v;v.reserve(N);srand(time(0));for (int i = 0; i < N; i++){int n = rand();v.push_back(n);}AVLTree<int, int>* root3 = new AVLTree<int, int>();for (auto e : v){root3->insert(make_pair(e, e));}//root->InOrder();cout << "isBalance: " << root3->isBalance() << endl;return 0;
}

运行结果：