底层结构
map和set的使用 ---- multiset和multimap
我们已经比较了解map/multimap/set/multiset,在其文档介绍中发现,这几个容器有个共同点是:其底层都是按照二叉搜索树来实现的,但是二叉搜索树有其自身的缺陷,假如往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度会退化成O(N),因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理,即采用平衡树来实现。
1. AVL的概念
二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在O ( l o g 2 n ) O(log_2 n)O(log2n),搜索时间复杂度O(l o g 2 n log_2 nlog2n)。
2. AVL树节点的定义
template <class K, class V> struct AVLTreeNode { AVLTreeNode<K,V>* _left;//左孩子节点 AVLTreeNode<K,V>* _right;//右孩子节点 AVLTreeNode<K,V>* _parent;//父亲节点 pair<K, V> _kv; //存储键值对的pair对象,其中K表示键的类型,V表示值的类型。 int _bf;//该节点的平衡因子:高度差 AVLTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) ,_kv(kv) ,_bf(0) {} };
结构体中包含以下成员变量:
- _left:指向左孩子节点的指针。
- _right:指向右孩子节点的指针。
- _parent:指向父节点的指针。
- _kv:存储键值对的pair对象,其中K表示键的类型,V表示值的类型。
- _bf:该节点的平衡因子,用于衡量左右子树高度差。
结构体中还定义了一个构造函数AVLTreeNode(const pair<K, V>& kv),用于初始化节点对象。构造函数会对成员变量进行初始化,其中:
- _left、_right、_parent被初始化为nullptr,表示当前节点没有左孩子、右孩子和父节点。
- _kv被初始化为传入的键值对对象kv。
- _bf被初始化为0,表示当前节点的平衡因子为0。
- 通过这个结构体,可以创建AVL树的节点对象,并且使用成员变量来访问和修改节点的属性。
3. AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步:
- 按照二叉搜索树的方式插入新节点
- 调整节点的平衡因子
先创建一个AVLTree的类
注:本文定义的函数全部都在AVLTree类中
//class默认是private template <class K,class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: bool insert(const pair<K,V>& kv) {} //.... private: Node* _root = nullptr; };
首先是普通搜索树的常规插入操作
bool insert(const pair<K,V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (kv.first < cur->_kv.first) { parent = cur; cur = cur->_left; } else if (kv.first > cur->_kv.first) { parent = cur; cur = cur->_right; } else { return false; } } cur = new Node(kv); if (kv.first < parent->_kv.first) { parent->_left = cur; cur->_parent = parent; } if (kv.first > parent->_kv.first) { parent->_right = cur; cur->_parent = parent; } /// AVL的开始 .......... return true; }
分析
如果影响祖先,怎么影响?分析如下:
现在可以把AVL的插入操作大概框架写一下了:
bool insert(const pair<K,V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (kv.first < cur->_kv.first) { parent = cur; cur = cur->_left; } else if (kv.first > cur->_kv.first) { parent = cur; cur = cur->_right; } else { return false; } } cur = new Node(kv); if (kv.first < parent->_kv.first) { parent->_left = cur; cur->_parent = parent; } if (kv.first > parent->_kv.first) { parent->_right = cur; cur->_parent = parent; } /// //AVL的开始 while (parent) { // 更新双亲的平衡因子 if (cur == parent->_left) { parent->_bf--; } else { parent->_bf++; } //说明更新前是-1或者1,并且更新后父节点左右平衡,不用继续往上更新了 if (parent->_bf == 0) { break; } //说明更新前bf是0,必须往上进行更新 else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = parent->_parent; } //说明更新前是-1或者1,并且更新后的子树违反了AVL树的规则,需要进行调整 else if(parent->_bf == 2 || parent->_bf == -2) { //调整处理 //........ } } return true; }
情况1一和情况二都好说
重点在于情况三的调整,下面将重点介绍调整的思路:“旋转”
4. AVL树的旋转
如果在一棵原本是平衡的AVL树中插入一个新节点,可能造成不平衡,此时必须调整树的结构,使之平衡化。根据节点插入位置的不同,AVL树的旋转分为四种:
4.1 新节点插入较高右子树的右侧—右右:左单旋
思路:
- 将父节点的右孩子保存为SubR,将SubR的左孩子保存为SubRL。
- 旋转链接,将SubRL作为父节点的右孩子,将父节点作为SubR的左孩子。
- 获取父节点的父节点,并根据情况将SubR连接到父节点的父节点的相应位置。
- 更新旋转后节点的平衡因子为0。
//左单旋 //(1.父亲节点的右边等于右孩子的左边; 2.右孩子的左边等于父亲节点) //【把右孩子的左边给给父亲节点的右边; 2.再把父亲节点给给右孩子的左边】 void RotateL(Node *parent) { Node* SubR = parent->_right;// 将父节点的右孩子保存为SubR Node* SubRL = SubR->_left;// 将SubR的左孩子保存为SubRL //旋转链接 parent->_right = SubRL;// 将SubRL作为父节点的右孩子 SubR->_left = parent; // 将父节点作为SubR的左孩子 Node* Parent_Parent = parent->_parent;// 获取父节点的父节点 parent->_parent = SubR; // 将SubR作为父节点的父节点 if (SubRL) { // 如果SubRL存在,则将其父节点指针指向父节点 SubRL->_parent = parent; } //和父节点的父节点链接 if (_root == parent) { _root = SubR;// 如果parent是根节点,将SubR设为新的根节点 SubR->_parent = nullptr;// 新的根节点的父节点指针设为nullptr } else { if (Parent_Parent->_left == parent) { // 将SubR作为父节点的父节点的左孩子 Parent_Parent->_left = SubR; } else { // 将SubR作为父节点的父节点的右孩子 Parent_Parent->_right = SubR; } SubR->_parent = Parent_Parent;// 将SubR的父节点指针指向父节点的父节点 } //更新平衡因子 SubR->_bf = parent->_bf = 0; }
4.2 新节点插入较高左子树的左侧—左左:右单旋
右单旋和左单旋完全类似:老铁们可以参考左单旋先写一遍再来看代码
思路:
- 将父节点的左孩子保存为SubL,将SubL的右孩子保存为SubLR。
- 旋转链接,将SubLR作为父节点的左孩子,将父节点作为SubL的右孩子。
- 获取父节点的父节点,并根据情况将SubL连接到父节点的父节点的相应位置。
- 更新旋转后节点的平衡因子为0。
//右单旋 void RotateR(Node* parent) { Node* SubL = parent->_left; Node* SubLR = SubL->_right; //旋转链接 //动一个节点就把他的父亲也变动 parent->_left = SubLR; if (SubLR)//SubLR可能为空 { SubLR->_parent = parent; } Node* Parent_Parent = parent->_parent; SubL->_right = parent; parent->_parent = SubL; //和父节点的父节点链接 if (_root == parent) { _root = SubL; SubL->_parent = nullptr; } else { if (Parent_Parent->_left == parent) { Parent_Parent->_left = SubL; } else { Parent_Parent->_right = SubL; } SubL->_parent = Parent_Parent;//链接 } SubL->_bf = parent->_bf = 0; //更新平衡因子 }
4.3 新节点插入较高右子树的左侧—右左:先右单旋再左单旋(右左双旋)
思路:
右左双旋又分两大种情况:
一. h>=1的AVL树
1.在b处插入
2.在c处插入
二. h==0的AVL树
3. 60自己就是新增
是不是很简单?
并且我们可以直接复用之前的单旋
代码思路:
- 将父节点的右孩子保存为subR,将subR的左孩子保存为subRL。
- 获取subRL的平衡因子。
- 对parent的右孩子进行右单旋操作。
- 再对parent进行左单旋操作。
- 根据subRL的平衡因子的不同情况,更新subRL、subR和parent的平衡因子。
//右左双旋 void RotateRL(Node* parent) { Node* subR = parent->_right; // 将父节点的右孩子保存为subR Node* subRL = subR->_left; // 将subR的左孩子保存为subRL int bf = subRL->_bf; // 提前获取subRL的平衡因子 RotateR(parent->_right); // 对parent的右孩子进行右单旋操作 RotateL(parent); // 对parent进行左单旋操作 if (bf == 0) // 如果subRL的平衡因子为0 { subRL->_bf = subR->_bf = parent->_bf = 0; // 更新subRL、subR和parent的平衡因子为0 } else if (bf == 1) // 如果subRL的平衡因子为1 { subRL->_bf = subR->_bf = 0; // 更新subRL和subR的平衡因子为0 parent->_bf = -1; // 更新parent的平衡因子为-1 } else if (bf == -1) // 如果subRL的平衡因子为-1 { subRL->_bf = parent->_bf = 0; // 更新subRL和parent的平衡因子为0 subR->_bf = 1; // 更新subR的平衡因子为1 } else { assert(false); // 如果平衡因子不是0、1或-1,则抛出错误 } }
4.4 新节点插入较高左子树的右侧—左右:先左单旋再右单旋(左右双旋)
思路:
在b处插入:
在c处插入:
60就是新增节点
代码思路:
- 将父节点的左孩子保存为subL,将subL的右孩子保存为subLR。
- 获取subLR的平衡因子。
- 对parent的左孩子进行左单旋操作。
- 再对parent进行右单旋操作。
- 根据subLR的平衡因子的不同情况,更新subLR、subL和parent的平衡因子。
//左右双旋 void RotateLR(Node* parent) { Node* subL = parent->_left; // 将父节点的左孩子保存为subL Node* subLR = subL->_right; // 将subL的右孩子保存为subLR int bf = subLR->_bf; // 获取subLR的平衡因子 RotateL(parent->_left); //对parent的左孩子进行左单旋操作 RotateR(parent); // 对parent进行右单旋操作 if (bf == 0) // 如果subLR的平衡因子为0 { subLR->_bf = subL->_bf = parent->_bf = 0; // 更新subLR、subL和parent的平衡因子为0 } else if (bf == 1) // 如果subLR的平衡因子为1 { subLR->_bf = parent->_bf = 0; // 更新subLR和parent的平衡因子为0 subL->_bf = -1; // 更新subL的平衡因子为-1 } else if (bf == -1) // 如果subLR的平衡因子为-1 { subLR->_bf = subL->_bf = 0; // 更新subLR和subL的平衡因子为0 parent->_bf = 1; // 更新parent的平衡因子为1 } else { assert(false); // 如果平衡因子不是0、1或-1,则抛出错误 } }
5. 整体代码:
注:加了一些简单的打印和判断平衡的代码
#pragma once #include <iostream> using namespace std; #include <map> #include <assert.h> //struct默认权限是public template <class K, class V> struct AVLTreeNode { AVLTreeNode<K,V>* _left;//左孩子节点 AVLTreeNode<K,V>* _right;//右孩子节点 AVLTreeNode<K,V>* _parent;//父亲节点 pair<K, V> _kv; //存储键值对的pair对象,其中K表示键的类型,V表示值的类型。 int _bf;//该节点的平衡因子:高度差 AVLTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) ,_kv(kv) ,_bf(0) {} }; //class默认是private template <class K,class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: bool insert(const pair<K,V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (kv.first < cur->_kv.first) { parent = cur; cur = cur->_left; } else if (kv.first > cur->_kv.first) { parent = cur; cur = cur->_right; } else { return false; } } cur = new Node(kv); if (kv.first < parent->_kv.first) { parent->_left = cur; cur->_parent = parent; } if (kv.first > parent->_kv.first) { parent->_right = cur; cur->_parent = parent; } /// //AVL的开始 while (parent) { if (cur == parent->_left) { parent->_bf--; } else { parent->_bf++; } //说明更新前是-1或者1,并且更新后父节点左右平衡,不用继续往上更新了 if (parent->_bf == 0) { break; } //说明更新前bf是0,必须往上进行更新 else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = parent->_parent; } //说明更新前是-1或者1,并且更新后的子树违反了AVL树的规则,需要进行调整 else if(parent->_bf == 2 || parent->_bf == -2) { //旋转(核心) if (parent->_bf == 2 && cur->_bf == 1) { //左单旋 RotateL(parent); } else if (parent->_bf == -2 && cur->_bf == -1) { //右单旋 RotateR(parent); } else if (parent->_bf == 2 && cur->_bf == -1) { //右左双旋 RotateRL(parent); } else if (parent->_bf == -2 && cur->_bf == 1) { //左右双旋 RotateLR(parent); } //1.旋转让这棵子树平衡了 //2.降低了这棵子树的高度,恢复到和之前一样的高度,对上一层没有影响,不用更新了 break; } else { assert(false); } } return true; } //左单旋 //(1.父亲节点的右边等于右孩子的左边; 2.右孩子的左边等于父亲节点) //【把右孩子的左边给给父亲节点的右边; 2.再把父亲节点给给右孩子的左边】 void RotateL(Node *parent) { Node* SubR = parent->_right; Node* SubRL = SubR->_left; //旋转链接 parent->_right = SubRL; SubR->_left = parent; Node* Parent_Parent = parent->_parent; parent->_parent = SubR; if (SubRL) { SubRL->_parent = parent; } //和父节点的父节点链接 if (_root == parent) { _root = SubR; SubR->_parent = nullptr; } else { if (Parent_Parent->_left == parent) { Parent_Parent->_left = SubR; } else { Parent_Parent->_right = SubR; } SubR->_parent = Parent_Parent; } //更新平衡因子 SubR->_bf = parent->_bf = 0; } //右单旋 void RotateR(Node* parent) { Node* SubL = parent->_left; Node* SubLR = SubL->_right; //旋转链接 //动一个节点就把他的父亲也变动 parent->_left = SubLR; if (SubLR)//SubLR可能为空 { SubLR->_parent = parent; } Node* Parent_Parent = parent->_parent; SubL->_right = parent; parent->_parent = SubL; //和父节点的父节点链接 if (_root == parent) { _root = SubL; SubL->_parent = nullptr; } else { if (Parent_Parent->_left == parent) { Parent_Parent->_left = SubL; } else { Parent_Parent->_right = SubL; } SubL->_parent = Parent_Parent;//链接 } SubL->_bf = parent->_bf = 0; //更新平衡因子 } //右左双旋 void RotateRL(Node *parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent->_right); RotateL(parent); if (bf == 0) { subRL->_bf = subR->_bf = parent->_bf=0; } else if (bf == 1) { subRL->_bf = subR->_bf = 0; parent->_bf = -1; } else if (bf == -1) { subRL->_bf = parent->_bf = 0; subR->_bf = 1; } else { assert(false); } } //左右双旋 void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateR(parent); if (bf == 0) { subLR->_bf = subL->_bf = parent->_bf = 0; } else if (bf == 1) { subLR->_bf = parent->_bf = 0; subL->_bf = -1; } else if (bf == -1) { subLR->_bf = subL->_bf = 0; parent->_bf= 1; } else { assert(false); } } void InOrder() { _InOrder(_root); cout << endl; } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << " "; _InOrder(root->_right); } //判断是否平衡 bool IsBalance() { return _IsBalance(_root); } int _Height(Node* root) { if (root == nullptr) return 0; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } bool _IsBalance(Node* root) { if (root == nullptr) return true; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); if (rightHeight - leftHeight != root->_bf) { cout << root->_kv.first << "平衡因子异常" << endl; return false; } return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right); } private: Node* _root = nullptr; };
6. AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制,因此要验证AVL树,可以分两步:
1.验证其为二叉搜索树
- 如果中序遍历可得到一个有序的序列,就说明为二叉搜索树
#include "AVLTree.h" #include <vector> int main() { int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; AVLTree<int, int> a; for (auto e : arr) { a.insert(make_pair(e, e)); } a.InOrder(); return 0; }
2.验证其为平衡树
- 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
- 节点的平衡因子是否计算正确
用下面代码判断是否为平衡树:
bool IsBalance() { return _IsBalance(_root); // 调用内部函数_IsBalance检查整个AVL树是否平衡 } int _Height(Node* root) { if (root == nullptr) // 如果当前节点为空,表示到达叶子节点,返回高度0 return 0; int leftHeight = _Height(root->_left); // 递归计算左子树的高度 int rightHeight = _Height(root->_right); // 递归计算右子树的高度 return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; // 返回较大的子树高度加1,表示当前子树的高度 } bool _IsBalance(Node* root) { if (root == nullptr) // 如果当前节点为空,表示到达叶子节点,返回true表示平衡 return true; int leftHeight = _Height(root->_left); // 计算左子树的高度 int rightHeight = _Height(root->_right); // 计算右子树的高度 if (rightHeight - leftHeight != root->_bf) // 判断右子树高度减去左子树高度是否等于当前节点的平衡因子 { cout << root->_kv.first << "平衡因子异常" << endl; // 如果不相等,输出异常信息 return false; // 返回false表示不平衡 } return abs(rightHeight - leftHeight) < 2 // 判断当前子树的高度差是否小于2 && _IsBalance(root->_left) // 递归检查左子树是否平衡 && _IsBalance(root->_right); // 递归检查右子树是否平衡 }
代码解释:
- _Height函数用于计算以给定节点为根的子树的高度,它递归地计算左子树和右子树的高度,然后返回较大的一侧高度加1,表示当前子树的高度。
- _IsBalance函数是实际进行平衡性检查的函数,它首先判断当前节点是否为空,如果为空则表示到达叶子节点,返回true表示平衡。然后,它计算当前节点的左子树和右子树的高度,并判断其高度差是否等于当前节点的平衡因子。如果不相等,则输出异常信息并返回false表示不平衡。接着,它递归地检查左子树和右子树是否平衡,并判断当前子树的高度差是否小于2。如果所有条件都满足,则返回true表示平衡。
- 通过调用IsBalance函数,可以判断整个AVL树是否平衡,即是否满足平衡因子的定义和高度差的限制。
代码测试:
int main() { const int N = 30; vector<int> v; v.reserve(N); srand(time(0)); for (size_t i = 0; i < N; i++) { v.push_back(rand() % 100 + 1); } AVLTree<int, int> t; for (auto e : v) { t.insert(make_pair(e, e)); } t.InOrder();//中序打印 if (t.IsBalance()) { cout << "是平衡二叉树" << endl; } else { cout << "不是平衡二叉树" << endl; } return 0; }
7. AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过1,这样可以保证查询时高效的时间复杂度,即l o g 2 ( N ) log_2 (N)log2(N)。但是如果要对AVL树做一些结构修改的操作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,有可能一直要让旋转持续到根的位置。因此:如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑AVL树,但一个结构经常修改,就不太适合。
(本章完)