AVL树、红黑树的介绍和实现[C++]
本文主要对AVL树和红黑树的结构和实现方法进行一定的介绍,仅实现部分接口。
目录
一、AVL树
1.AVL树的概念
2.AVL树节点的定义
3.AVL树的插入
4.AVL树的旋转
1. 新节点插入较高左子树的左侧——左左:右单旋
2. 新节点插入较高右子树的右侧——右右:左单旋
3. 新节点插入较高左子树的右侧——左右:先左单旋再右单旋
4. 新节点插入较高右子树的左侧——右左:先右单旋再左单旋
5.AVL树的验证
6.AVL树的性能
二、红黑树
1.红黑树的概念
2.红黑树的性质
3.红黑树节点的定义
4.红黑树的插入操作
1.情况一:cur为红,p为红,g为黑,u存在且为红
2.情况二: cur为红,p为红,g为黑,u不存在/u存在且为黑
3.情况三: cur为红,p为红,g为黑,u不存在/u存在且为黑
4.代码如下:
5.红黑树的验证
6.红黑树与AVL树的比较
前言
map/multimap/set/multiset介绍和使用
二叉搜索树介绍和实现
上一篇文章对map/multimap/set/multiset进行了简单的介绍,在其文档介绍中发现,这几个容器有个共同点是:其底层都是按照二叉搜索树来实现的,但是二叉搜索树有其自身的缺陷,假如往树中 插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度会退化成O(N),因此 map、set等关联式容器的底层结构是对二叉树进行了平衡处理,即采用平衡树来实现。
一、AVL树
1.AVL树的概念
二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查 找元素相当于在顺序表中搜索元素,效率低下。
因此,两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
(平衡因子只是一种AVL的实现方式,本文通过这种方法来实现)
如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在 ,搜索时间复杂度。
2.AVL树节点的定义
AVL树节点的定义:
template<class K,class V>
struct AVLTreeNode
{AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}AVLTreeNode<T>* _left; // 该节点的左孩子AVLTreeNode<T>* _right; // 该节点的右孩子AVLTreeNode<T>* _parent; // 该节点的双亲pair<K, V> _kv;int _bf; // 该节点的平衡因子
};
3.AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为以下步骤:
- 按照二叉搜索树的方式找到其对应的位置插入新节点
- 调整节点的平衡因子,平衡因子的更新取决于子树高度的变化,左子树新增则--平衡因子,右子树新增++平衡因子
- 如果更新完以后,平衡没有出现问题,即 |_bf|<=1,平衡结构没有受到影响,不需要处理
- 如果更新完以后,平衡没有出现问题,即 |_bf|>1,平衡结构受到影响,需要旋转处理
其中,新节点插入后,父节点的平衡因子一定需要调整,在插入之前,父节点的平衡因子分为三种情况: - 1,0, 1, 分以下两种情况:
- 如果新节点插入到父节点的左侧,只需给父节点的平衡因子 - 1即可
- 如果新节点插入到父节点的右侧,只需给父节点的平衡因子 + 1即可
此时:父节点的平衡因子可能有三种情况:0,正负1,正负2。
- 如果父节点的平衡因子为0,说明插入之前parent的平衡因子为正负1,插入后被调整成0,此时满足AVL树的性质,插入成功
- 如果父节点的平衡因子为正负1,说明插入前父节点的平衡因子一定为0,插入后被更新成正负1,此时以父节点为根的树的高度增加,需要继续向上更新
- 如果parent的平衡因子为正负2,则parent的平衡因子违反平衡树的性质,需要对其进行旋转处理
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 (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);cur->_parent = parent;if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}//调整平衡因子while (parent){if (parent->_left == cur)parent->_bf--;elseparent->_bf++;if (parent->_bf == 1 || parent->_bf == -1){parent = parent->_parent;cur = cur->_parent;}else if(parent->_bf == 0){break;}//进行旋转调整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){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}break;}else{assert(false);}}
}
4.AVL树的旋转
如果在一棵原本是平衡的AVL树中插入一个新节点,可能造成不平衡,此时必须调整树的结构, 使之平衡化。根据节点插入位置的不同,AVL树的旋转分为四种:
1. 新节点插入较高左子树的左侧——左左:右单旋
上图在插入前,AVL树是平衡的,新节点插入到20的左子树(注意:此处不是左孩子)中,20左子树增加了一层,导致以40为根的二叉树不平衡,要让40平衡,只能将40左子树的高度减少一层,右子树增加一层, 即将左子树往上提,这样40转下来,因为40比20大,只能将其放在20的右子树,而如果20有右子树,右子树根的值一定大于20,小于40,只能将其放在40的左子树,旋转完成后,更新节点的平衡因子即可。
代码如下:
void RotateR(Node* parent)//parent为平衡因子为-2的节点
{Node* subL = parent->_left;//parent的左孩子Node* subLR = subL->_right;//parent左孩子的右孩子,即需要更新为parent的新左孩子的节点parent->_left = subLR;// 如果20的左孩子的右孩子存在,更新父节点if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;// 如果40是根节点,根新指向根节点的指针if (ppnode == nullptr){_root = subL;_root->_parent = nullptr;}else{// 如果40是子树,可能是其双亲的左子树,也可能是右子树subL->_parent = ppnode;if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}}//根据调整后的结构更新部分节点的平衡因子parent->_bf = subL->_bf = 0;
}
2. 新节点插入较高右子树的右侧——右右:左单旋
该情况为右右单旋的镜像,实现及情况考虑参考右单旋即可。
代码如下:
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if(subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (ppnode == nullptr){_root = subR;_root->_parent = nullptr;}else{subR->_parent = ppnode;if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}}parent->_bf = subR->_bf = 0;
}
3. 新节点插入较高左子树的右侧——左右:先左单旋再右单旋
将双旋变成单旋后再旋转,即:先对20进行左单旋,然后再对60进行右单旋,旋转完成后再考虑平衡因子的更新。
代码如下:
// 旋转之前,40的平衡因子可能是-1/0/1,旋转完成之后,
//根据情况对其他节点的平衡因子进行调整
void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;// 旋转之前,保存pSubLR的平衡因子,旋转完成之后,
// 需要根据该平衡因子来调整其他节点的平衡因子int bf = subLR->_bf;
// 先对20进行左单旋RotateL(parent->_left);// 再对60进行右单旋RotateR(parent);if (bf == -1){parent->_bf = 1;subLR->_bf = 0;subL->_bf = 0;}else if (bf == 1){parent->_bf = 0;subLR->_bf = 0;subL->_bf = -1;}else if (bf == 0){parent->_bf = 0;subLR->_bf = 0;subL->_bf = 0;}else//如果运行到此处说明平衡因子有错误assert(false);
}
4. 新节点插入较高右子树的左侧——右左:先右单旋再左单旋
参考左右双旋。
代码如下:
void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == -1){parent->_bf = 0;subRL->_bf = 0 ;subR->_bf = 1;}else if (bf == 1){parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else if (bf == 0){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 0;}elseassert(false);
}
总结:
假如以parent为根的子树不平衡,即parent的平衡因子为2或者-2,分以下情况考虑
1. parent的平衡因子为2,说明parent的右子树高,设parent的右子树的根为subR
- 当subR的平衡因子为1时,执行左单旋
- 当subR的平衡因子为-1时,执行右左双旋
2. parent的平衡因子为-2,说明parent的左子树高,设parent的左子树的根为subL
- 当subL的平衡因子为-1是,执行右单旋
- 当subL的平衡因子为1时,执行左右双旋
5.AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制,因此要验证AVL树,可以分两步:
1. 验证其为二叉搜索树
如果中序遍历可得到一个有序的序列,就说明为二叉搜索树
2. 验证其为平衡树
- 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
- 节点的平衡因子是否计算正确
int _Height(Node* root)//求树的高度
{if (root == nullptr)//为空返回0return 0;//递归求左子树和右子树的高度int left = _Height(root->_left);int right = _Height(root->_right);//返回较高子树的高度+1(根节点)return left > right ? left + 1 : right + 1;
}bool _IsBalance(Node* root)判断是否平衡
{if (root == nullptr)return true;int leftH = _Height(root->_left);int rightH = _Height(root->_right);//右子树高度-左子树高度!=平衡因子则说明有误if ((rightH - leftH) != root->_bf){ cout <<root->_kv.first<< "平衡因子错误" << endl;return false;}//平衡因子小于2,去递归左右子树return (abs(leftH - rightH) < 2)&& _IsBalance(root->_left)&& _IsBalance(root->_right);}bool IsBalance()
{return _IsBalance(_root);
}
因为AVL树也是二叉搜索树,其他接口与二叉搜索树类似,其中删除接口可按照二叉搜索树的方式将节点删除,然后再更新平衡因子,只不过与删除不同的是,删除节点后的平衡因子更新,最差情况下一直要调整到根节点的位置。
本文主要介绍结构,其他接口实现不做介绍了。
6.AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过1,这 样可以保证查询时高效的时间复杂度,即。但是如果要对AVL树做一些结构修改的操作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时, 有可能一直要让旋转持续到根的位置。因此:如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑AVL树,但一个结构经常修改,就不太适合。
二、红黑树
1.红黑树的概念
红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,因而是接近平衡的。
2.红黑树的性质
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的,则它的两个孩子结点是黑色的
4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
其中,根据性质3,4可以得到一条路径最短的情况为该路径都是黑节点,最长路径的情况为该路径上的节点为一黑一红交替,因此红黑树的最长路径最多为最短路径的2倍。
3.红黑树节点的定义
enum Color// 节点的颜色
{RED,BLACK
};
// 红黑树节点的定义
template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;// 节点的左孩子RBTreeNode<K, V>* _right;// 节点的右孩子RBTreeNode<K, V>* _parent; // 节点的双亲(红黑树需要旋转)pair<K, V> _kv; // 节点的值域Color _col; // 节点的颜色RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};
将新插入节点的默认颜色设置为红色。
如果新插入节点默认颜色为黑色的话,该节点插入后会违反性质4,那么需要对全部路径进行调整。新插入节点默认颜色为红色的话,如果该节点插入后父节点为黑色,则不需要调整,父节点为红色再继续调整。
根据上述情况,新插入节点默认颜色为红色更优。
4.红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:
1. 按照二叉搜索的树规则插入新节点
2. 检测新节点插入后,红黑树的性质是否造到破坏
因为新节点的默认颜色是红色,因此:如果其双亲节点的颜色是黑色,没有违反红黑树任何性质,则不需要调整;但当新插入节点的双亲节点颜色为红色时,就违反了性质3不能有连在一起的红色节点,此时需要对红黑树分情况来讨论:
约定:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点
1.情况一:cur为红,p为红,g为黑,u存在且为红
解决方式:将p,u改为黑,g改为红,然后把g当成cur,继续向上调整。
(注意:下图中的树,可能是一颗完整二叉树,也可能是一颗子树)
2.情况二: cur为红,p为红,g为黑,u不存在/u存在且为黑
解决方式:
- p为g的左孩子,cur为p的左孩子,则进行右单旋转;
- 相反, p为g的右孩子,cur为p的右孩子,则进行左单旋转
- p、g变色--p变黑,g变红
说明:u的情况有两种。
1. 如果u节点不存在,则cur一定是新插入节点,因为如果cur不是新插入节点,则cur和p一定有一个节点的颜色是黑色,就不满足性质4:每条路径黑色节点的数量相同。
2.如果u节点存在且黑色,那么cur节点原来的颜色一定是黑色,现在看到cur是红色的原因是因为cur的子树在调整过程中将cur节点的颜色由黑色变为红色。
3.情况三: cur为红,p为红,g为黑,u不存在/u存在且为黑
解决方式:
- p为g的左孩子,cur为p的右孩子,则针对p做左单旋转;
- 相反, p为g的右孩子,cur为p的左孩子,则针对p做右单旋转,则转换成了情况2
其余情况都为上述情况的镜像,在此不做介绍了。
4.代码如下:
bool Insert(const pair<K, V>& kv)
{//寻找插入位置if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);cur->_parent = parent;if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}//调整while (parent && parent->_col == RED){// 注意:grandfather一定存在// 因为parent存在,且不是黑色节点,则parent一定不是根,则其一定有双亲Node* grandfather = parent->_parent;// 先讨论左侧情况if ( grandfather->_left == parent){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)// 情况1:u存在且为红,变色处理,并继续往上处理{parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else// 情况2+3:u不存在/u存在且为黑,旋转+变色{if (cur == parent->_left){RotateR(grandfather);//旋转部分代码见下文parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else// 讨论右侧情况{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED)// 情况1:u存在且为红,变色处理,并继续往上处理{parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else// 情况2+3:u不存在/u存在且为黑,旋转+变色{if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//根节点变为黑色_root->_col = BLACK;return true;
}
旋转部分:
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (ppnode == nullptr){_root = subR;_root->_parent = nullptr;}else{subR->_parent = ppnode;if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}}
}void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (ppnode == nullptr){_root = subL;_root->_parent = nullptr;}else{subL->_parent = ppnode;if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}}
}
红黑树的其他接口不做介绍了。
红黑树的删除
5.红黑树的验证
红黑树的检测分为两步:
- 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
- 检测其是否满足红黑树的性质
bool _check(Node* root, int blackNum, int benchmark)
{if (root == nullptr){if (blackNum != benchmark){cout << "路径上黑色节点的数量不相等" << endl;return false;} }if (root->_col == BLACK)//记录路径中黑色节点的个数{++blackNum;}if (root->_col == RED && root->_parent->_col == RED){cout << "出现连续红色节点" << endl;return false;}//通过上方检测后递归判断左右子树return _check(root->_left, blackNum, benchmark)&& _check(root->_right, blackNum, benchmark);
}bool IsBalance()
{if (_root->_col == RED){cout << "根节点为红色" << endl;return false;}int benchmark = 0;Node* cur = _root;// 获取任意一条路径中黑色节点的个数,作为基准值while (cur){if(cur->_col == BLACK)++benchmark;cur = cur->_left;}return _check(_root, 0, benchmark);
}
6.红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是,红黑树不追求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对而言,降低了插入和旋转的次数, 所以在经常进行增删的结构中性能比AVL树更优,而且红黑树实现比较简单,所以实际运用中红黑树更多。