湖北专业网站制作公司,网站域名更改了怎么换,小程序制作推广,制作百度移动网站模板免费下载本文主要对AVL树和红黑树的结构和实现方法进行一定的介绍#xff0c;仅实现部分接口。
目录
一、AVL树
1.AVL树的概念
2.AVL树节点的定义
3.AVL树的插入
4.AVL树的旋转
1. 新节点插入较高左子树的左侧——左左#xff1a;右单旋
2. 新节点插入较高右子树的右侧——右…本文主要对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树节点的定义
templateclass K,class V
struct AVLTreeNode
{AVLTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}AVLTreeNodeT* _left; // 该节点的左孩子AVLTreeNodeT* _right; // 该节点的右孩子AVLTreeNodeT* _parent; // 该节点的双亲pairK, V _kv;int _bf; // 该节点的平衡因子
}; 3.AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为以下步骤
按照二叉搜索树的方式找到其对应的位置插入新节点调整节点的平衡因子平衡因子的更新取决于子树高度的变化左子树新增则--平衡因子右子树新增平衡因子如果更新完以后平衡没有出现问题,即 |_bf|1,平衡结构没有受到影响不需要处理如果更新完以后平衡没有出现问题,即 |_bf|1,平衡结构受到影响需要旋转处理 其中新节点插入后父节点的平衡因子一定需要调整在插入之前父节点的平衡因子分为三种情况 - 10, 1, 分以下两种情况
如果新节点插入到父节点的左侧只需给父节点的平衡因子 - 1即可如果新节点插入到父节点的右侧只需给父节点的平衡因子 1即可
此时父节点的平衡因子可能有三种情况0正负1正负2。
如果父节点的平衡因子为0说明插入之前parent的平衡因子为正负1插入后被调整成0此时满足AVL树的性质插入成功如果父节点的平衡因子为正负1说明插入前父节点的平衡因子一定为0插入后被更新成正负1此时以父节点为根的树的高度增加需要继续向上更新如果parent的平衡因子为正负2则parent的平衡因子违反平衡树的性质需要对其进行旋转处理
bool Insert(const pairK, 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. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 其中根据性质34可以得到一条路径最短的情况为该路径都是黑节点最长路径的情况为该路径上的节点为一黑一红交替因此红黑树的最长路径最多为最短路径的2倍。 3.红黑树节点的定义
enum Color// 节点的颜色
{RED,BLACK
};
// 红黑树节点的定义
templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;// 节点的左孩子RBTreeNodeK, V* _right;// 节点的右孩子RBTreeNodeK, V* _parent; // 节点的双亲(红黑树需要旋转)pairK, V _kv; // 节点的值域Color _col; // 节点的颜色RBTreeNode(const pairK, 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 pairK, 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)// 情况1u存在且为红变色处理并继续往上处理{parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else// 情况23u不存在/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)// 情况1u存在且为红变色处理并继续往上处理{parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else// 情况23u不存在/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树更优而且红黑树实现比较简单所以实际运用中红黑树更多。
