黄骅市网站建设,苏州做网站的单位,wordpress 清理数据库,安阳到濮阳AVL树和红黑树 1. 背景2. AVL树的概念3. AVL树节点的定义4. AVL树的插入5. AVL树的旋转5.1. 左单旋5.2. 右单旋5.3. 左右单旋5.4. 右左单旋5.5. 旋转总结 6. AVL树的验证7. AVL树的性能8. 红黑树的概念9. 红黑树的节点的定义10. 红黑树的插入10.1. 情况一10.2.情况二 11. 红黑树… AVL树和红黑树 1. 背景2. AVL树的概念3. AVL树节点的定义4. AVL树的插入5. AVL树的旋转5.1. 左单旋5.2. 右单旋5.3. 左右单旋5.4. 右左单旋5.5. 旋转总结 6. AVL树的验证7. AVL树的性能8. 红黑树的概念9. 红黑树的节点的定义10. 红黑树的插入10.1. 情况一10.2.情况二 11. 红黑树的验证12. 红黑树与AVL树的比较 1. 背景 set、map、multiset、multimap这几个关联式容器的共同点是底层都是用二叉搜索树来实现的但二叉搜索树自身有缺陷若插入的元素有序或者接近有序二叉搜索树就会退化为单支树查询时相当于在顺序表中进行查询效率低下时间复杂度退化为O(n)因此map、set等关联式容器的底层结构对二叉搜索树进行了平衡处理即采用平衡树来实现。 通过保证每个节点的左、右子树高度差不超过1对树中的节点进行调整即可降低树的高度从而减少树的搜索长度时间复杂度为O(longn)。
2. AVL树的概念 AVL树具有的性质a. 每个节点的左右子树都是AVL树 b. 每个节点的左右子树高度差(平衡因子)的绝对值不超过1(0、-1、1)。 平衡因子右子树高度-左子树高度不是必须存在的只是一种控制方式帮助我们更便捷的控制树检查是否为AVL树。 如果一颗二叉搜索树高度是平衡的那么它就是AVL树如果它有n个节点它的高度就是longn则搜索的时间复杂度为O(longn)。 无法做到平衡因子的值恒为0因为二叉树插入节点是一个一个插入进去的对于2个或者4个节点的树是无法做到左右子树高度差等于0最优的高度差就是1。
3. AVL树节点的定义
templateclass K, class V //AVL树的节点(KV模型)
struct AVLTreeNode{ typedef AVLTreeNodeK, V Node; Node* _left; //该节点的左孩子Node* _right; //该节点的右孩子Node* _parent; //该节点的父亲便于向上更新int _bf; //该节点的平衡因子pairK, V _kv; AVLTreeNode(const pairK, V kv) //构造函数:_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0) { }
};4. AVL树的插入 方法先按二叉搜索树的方式插入新节点在更新平衡因子。 void RotateL(Node* parent) //右右—左单旋
{Node* subR parent-_right;Node* subRL subR-_left;Node* pphead parent-_parent;parent-_right subRL; //b变成父节点的右孩子if (subRL) //当前节点的左孩子可能存在也可能不存在 h0,b0subRL-_parent parent; //更新当前节点右孩子的父亲subR-_left parent; //父节点变为当前节点的左孩纸parent-_parent subR; //更新父节点的父亲//更新当前节点的父亲父节点可能为根节点也可能为根节点if (parent _root) //根节点 {_root subR;subR-_parent nullptr; //更新当前节点的父亲}else{if (pphead-_left parent) //子树pphead-_left subR;elsepphead-_right subR;subR-_parent pphead; //更新当前节点的父亲}subR-_bf 0; //更新平衡因子parent-_bf 0;
}void RotateR(Node* parent) //左左—右单旋
{Node* subL parent-_left;Node* subLR subL-_right;Node* pphead parent-_parent;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (pphead-_left parent)pphead-_left subL;elsepphead-_right subL;subL-_parent pphead;}subL-_bf 0; //更新平衡因子parent-_bf 0;
}void RotateRL(Node* parent) //右左—先右旋再左旋
{Node* subR parent-_right;Node* subRL subR-_left;Node* bf subRL-_bf; //因为旋转后会改变bf需要提前记录RotateR(subR); RotateL(parent);subRL-_bf 0; //更新平衡因子if (bf 0) //情况一当h 0,subRL为新增节点{subR-_bf 0;parent-_bf 0;}else if (bf -1) //情况二当h 0b插入b的高度变为h引发旋转{subR-_bf 1;parent-_bf 0;}else if(bf 1) //情况三当h 0c插入c的高度变为h引发旋转{subR-_bf 0;parent-_bf -1;}else //平衡因子异常{assert(false);}
}void RotateLR(Node* parent) //左右—先左旋再右旋
{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(subL);RotateR(parent);subLR-_bf 0; //更新平衡因子if (bf 0){subLR-_bf 0;parent-_bf 0;}else if (bf 1){subL-_bf -1;parent-_bf 0;}else if(bf -1){subL-bf 0;parent-_bf 1;}else{assert(false);}
}bool insert(const pairK, V kv) //插入
{Node* parent nullptr;Node* cur _root;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 nullptr) //空树{_root cur;return true;}if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent; //记录当前节点的父亲while (parent) //更新结束 情况1更新到根节点{if (parent-_left cur) //再更新平衡因子parent-_bf--;elseparent-_bf;if (parent-_bf 0) //更新结束 情况2p的高度不变不会影响上层的bfbreak;else if (parent-_bf 1 || parent-_bf -1) //更新继续p的高度改变会影响上层的bf但未违反平衡树性质{cur cur-_parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2) //违反了平衡树的规则做处理-》旋转 -更新结束{ //注意以下4种旋转只要完成了某一种都会更新结束需要breakif (parent-_bf 2 cur-_bf 1) //插入到较高右子树的右边{RotateL(parent); //右右—左单旋break; }else if (parent-_bf -2 cur-_bf -1) //插入到较高左子树的左边{RotateR(parent); //左左—右单旋break;}else if (parent-_bf 2 cur-_bf -1) //插入到较高右子树的左边{ RotateRL(parent); //右左—先右旋再左旋break;}else if (parent-_bf -2 cur-_bf 1) //插入到较高左子树的右边{ RotateLR(parent); //左右—先左旋再右旋break;}else //在插入前就不是AVL树 必须保证再插入前是一颗AVL树 {assert(false);break;}}}
}5. AVL树的旋转
5.1. 左单旋
void RotateL(Node* parent) //右右—左单旋
{Node* subR parent-_right;Node* subRL subR-_left;Node* pphead parent-_parent; parent-_right subRL; //b变成父节点的右孩子if (subRL) //当前节点的左孩子可能存在也可能不存在 h0,b0subRL-_parent parent; //更新当前节点右孩子的父亲subR-_left parent; //父节点变为当前节点的左孩纸parent-_parent subR; //更新父节点的父亲//更新当前节点的父亲父节点可能为根节点也可能为根节点if (parent _root) //根节点 {_root subR;subR-_parent nullptr; //更新当前节点的父亲}else{if (pphead-_left parent) //子树pphead-_left subR;elsepphead-_right subR;subR-_parent pphead; //更新当前节点的父亲}subL-_bf 0; //更新平衡因子parent-_bf 0;
}5.2. 右单旋
void RotateR(Node* parent) //左左—右单旋
{Node* subL parent-_left;Node* subLR subL-_right;Node* pphead parent-_parent;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (pphead-_left parent)pphead-_left subL;elsepphead-_right subL;subL-_parent pphead;}subL-_bf 0; //更新平衡因子parent-_bf 0;
}5.3. 左右单旋
void RotateLR(Node* parent) //左右—先左旋再右旋
{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(subL);RotateR(parent);subLR-_bf 0; //更新平衡因子if (bf 0){subLR-_bf 0;parent-_bf 0;}else if (bf 1){subL-_bf -1;parent-_bf 0;}else if(bf -1){subL-bf 0;parent-_bf 1;}else{assert(false);}
}5.4. 右左单旋
void RotateRL(Node* parent) //右左—先右旋再左旋
{Node* subR parent-_right;Node* subRL subR-_left;Node* bf subRL-_bf; //因为旋转后会改变bf需要提前记录RotateR(subR); RotateL(parent);subRL-_bf 0; //更新平衡因子if (bf 0) //情况一当h 0,subRL为新增节点{subR-_bf 0;parent-_bf 0;}else if (bf -1) //情况二当h 0b插入b的高度变为h引发旋转{subR-_bf 1;parent-_bf 0;}else if(bf 1) //情况三当h 0c插入c的高度变为h引发旋转{subR-_bf 0;parent-_bf -1;}else //平衡因子异常{assert(false);}
}5.5. 旋转总结 6. AVL树的验证 方法先验证其为二叉搜索树(中序遍历得到有序序列再验证其为平衡树(左右子树高度差的绝对值不超过1、平衡因子正常)。 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 (abs(rightHeight - leftHeight) 2){cout 不平衡 endl; return false;}if (rightHeight - leftHeight ! root-_bf){cout root-_kv.first :平衡因子异常 endl;return false;}return _Isbalance(root-_left) _Isbalance(root-_right);
}void _Inorder(Node* root) //中序遍历 验证其为二叉搜索树
{if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first [ root-_bf ] endl;_Inorder(root-_right);
}不能采用层序遍历、看bf的值原因对于完全二叉树、满二叉树通过层序遍历可以推出树的正确结构AVL树不一定为完全、满二叉树。在旋转时bf可能更新异常此时看bf的值会造错误构。 验证其为平衡二叉树采用前序遍历缺点先求高度再判平衡递归式判子树平衡导致重复求子树的高度效率低——》解决方法将前序改成后序并将高度作为引用参数(引用各个栈帧相互影响边判平衡边求高度。
bool _Isbalance(Node* root, int height) //后序遍历引用参数
{if (root nullptr) //空树也是AVL树{height 0;return true;}int leftHeight 0, rightHeight 0;if(!_Isbalance(root-_left, leftHeight) || !_Isbalance(root-_right, rightHeight)) return false; //只要左右子树有一颗不是平衡树该树就不是平衡树height leftHeight rightHeight ? leftHeight 1 : rightHeight 1;return true;
}int main()
{int a[] { 8, 5, 2, 6, 3, 7, 4, 1 };AVLTreeint, int t;for (auto e : a){t.insert(make_pair(e, e));}t.Inorder();cout t.Isbalance() endl;return 0;
}7. AVL树的性能 AVL是一颗高度平衡的二叉搜索树查询时效率高时间复杂度为O(longn)但如果要对AVL树进行结构修改操作性能非常低如插入时为了维持平衡需要进行多次旋转删除可能旋转要持续到根节点位置处。 如果需要一种查询高效且数据有序的数据结构数据的个数为静态的(不会插入元素结构不会发生改变可以考虑使用AVL树。如果一个结构需要经常的修改AVL树不太适用。
8. 红黑树的概念 红黑树的概念红黑树是一种二叉搜索树在每个节点上增加一个存储位来表示节点的颜色red或者black通过对每条路径上节点着色方式的控制红黑树保证了最长路径不超过最短路径的二倍其他路径的长度位于最短路径长度和最长路径长度之间即每条路径不会比其他路径长出两倍因此它接近于平衡。 红黑树的性质 a.每个节点的颜色不是红色就是黑色 b.根节点的颜色一定是黑色 c.如果有一个节点的颜色是红色则它的孩子节点的颜色一定是黑色即没有连续的红色节点 d.每条路径都具有相同数量的黑色节点。 e.每个叶子节点都是黑色的叶子节点指的是空节点又名为NIL节点是为了避免路径(根节点到空节点)数错的误区。 问只要满足以上的性质为什么红黑树就能保证最长路径中节点个数不超过最短路径中节点个数的两倍 答因为在极端情况下最短路径全黑最长路径一黑一红。 9. 红黑树的节点的定义
enum Color { //枚举一一列举出事物具有的所有可能Red, //枚举常量给枚举变量进行赋值Black,
};templateclass K, class V//红黑树的节点(KV模型)
struct RBTreeNode {typedef RBTreeNodeK, V Node;Node* _left; //该节点的左孩子Node* _right; //该节点的右孩子Node* _parent; //该节点的父亲便于向上更新pairK, V _kv; Color _col;RBTreeNode(const pairK, V kv, Color col Red) //构造函数:_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(col) //默认新插入节点的颜色为红色{ }
};10. 红黑树的插入 方法先按照二叉搜素树的方式插入在更新颜色。 void RotateL(Node* parent) //右右—左单旋
{Node* subR parent-_right;Node* subRL subR-_left;Node* pphead parent-_parent;parent-_right subRL; if (subRL) subRL-_parent parent; subR-_left parent; parent-_parent subR; if (parent _root) {_root subR;subR-_parent nullptr; }else{if (pphead-_left parent) pphead-_left subR;elsepphead-_right subR;subR-_parent pphead;}
}void RotateR(Node* parent) //左左—右单旋
{Node* subL parent-_left;Node* subLR subL-_right;Node* pphead parent-_parent;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (pphead-_left parent)pphead-_left subL;elsepphead-_right subL;subL-_parent pphead;}
}void RotateRL(Node* parent) //右左—先右旋再左旋
{Node* subR parent-_right;Node* subRL subR-_left;RotateR(subR);RotateL(parent);
}void RotateLR(Node* parent) //左右—先左旋再右旋
{Node* subL parent-_left;Node* subLR subL-_right;RotateL(subL);RotateR(parent);
}bool insert(const pairK, V kv) //插入
{Node* parent nullptr;Node* cur _root;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 nullptr) //空树{_root cur;_root-_col Black; //跟节点为黑return true;}if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent; //记录当前节点的父亲//更新颜色//插入结束1.插入节点的父亲是黑色因为插入前该树就为红黑树 2.情况一处理完后cur为根节点且为黑色while (parent parent-_col Red) { //爷爷一定存在因为c为红p为红所以p一定不是根节点且一定有父节点Node* grandfather parent-_parent; if (parent grandfather-_left) //旋转需要确定方向{Node* uncle grandfather-_right; if (uncle uncle-_col Red) //情况一叔叔存在且为红-无方向(p、u为g的任意边c为p的任一边){ //cur可能为新增节点也可能一开始为黑色cur的子树(下一层为红下一层为新插入节点)在调整过程中将cur由黑变为红parent-_col uncle-_col Black; //p、u变为黑g变为红grandfather-_col Red;//g可能为根节点(更新结束)也可能为子树(继续向上更新)cur grandfather; parent cur-_parent; }else //情况二叔叔不存在 或者 叔叔存在且为黑{ //叔叔不存在cur为新增节点 或 cur原来为黑经子树调整由黑变红if (parent-_left cur) //左左——右单旋{RotateR(grandfather);parent-_col Black; //p变为黑g变为红grandfather-_col Red;}else //左右——左右单旋 {RotateL(parent); RotateR(grandfather);cur-_col Black; //c变黑g变红grandfather-_col Red;}break; //更新结束3.旋转颜色处理后就是红黑树了}}else{Node* uncle grandfather-_left;if (uncle uncle-_col Red){parent-_col uncle-_col Black;grandfather-_col Red;cur grandfather;parent cur-_parent;}else{if (parent-_right cur) //右右——左单旋{RotateL(grandfather);parent-_col Black;grandfather-_col Red;}else //右左——右左单旋{RotateR(parent);RotateL(grandfather);cur-_col Black;grandfather-_col Red;}break; }}}_root-_col Black; //g为根颜色变为黑更新结束return true; //情况一插入节点的父亲为黑插入结束
}10.1. 情况一 叔叔存在且为红色——将p、u变为黑色g变为红色在把g给c。若c为根节点将c变为黑色插入结束(break)。若c不为根节点继续向上更新颜色直到c为根 或则 c的父亲为黑色。 无方向——p、u是g的左右都可以c是p的左右都可以处理方式都是一样的。
if (uncle uncle-_col Red) //情况一叔叔存在且为红-无方向(p、u为g的任意边c为p的任一边)
{ //cur可能为新增节点也可能一开始为黑色cur的子树(下一层为红下一层为新插入节点)在调整过程中将cur由黑变为红parent-_col uncle-_col Black; //p、u变为黑g变为红grandfather-_col Red;//g可能为根节点(更新结束)也可能为子树(继续向上更新)cur grandfather; parent cur-_parent;
}10.2.情况二 叔叔不存在 或者 叔叔存在且为黑色——旋转(有方向4种) 颜色处理。 a. p为g的左孩子c为p的左孩子左左右单旋。b. p为g的右孩子c为p的右孩子右右左单旋将p变为黑色将g变为红色—》将p变为黑色将g变为红色。c. p为g的左孩子c为p的右孩子左右旋。d. p为g的右孩子c为p的左孩子右左旋——》将c变为黑色g变为红色。 若叔叔不存在c只可以是新增节点因为若c不是新增节点该树最短路径长度为1最长路径长度为4在插入前就已经违反了红黑树性质3。若叔叔存在且为红c只能是原来为黑色经子树调整由黑色变为红色。 情况二在插入前最短路径长度最短路径长度12插入后违反了红黑树性质4所以需要做旋转处理。
if (parent-_left cur) //左左——右单旋
{RotateR(grandfather);parent-_col Black; //p变为黑g变为红grandfather-_col Red;
}
else //左右——左右单旋
{RotateL(parent); RotateR(grandfather);cur-_col Black; //c变黑g变红grandfather-_col Red;
}
break; //更新结束3.旋转颜色处理后就是红黑树了11. 红黑树的验证 方法先验证其为二叉搜索树(中序遍历得到有序序列再验证其是否满足红黑树的性质。 void Inorder() //验证其为二叉搜索树中序遍历
{_Inorder(_root);
}bool Balance() //验证其是否满足红黑树的性质
{if (_root _root-_col Red) //红黑树性质2跟节点为黑色return false;int refvalue 0; //红黑树性质4每条路径具有相同数量的黑节点Node* cur _root; while (cur){if (cur-_col Black)refvalue; //找参考值cur cur-_left;}_Balance(_root, 0, refvalue);
}//前序遍历将每条路径黑色节点的数量于参考值比较验证性质4
bool _Balance(Node* root, int blackcount, int refvalue)
{if (root nullptr){if (blackcount ! refvalue)return false;return true;}if (root-_col Red root-_parent-_col Red)return false; //验证红黑性质3没有连续的红节点孩子找爹if (root-_col Black) //blackcount没有用引用因为下层不能影响上次blackcount表示的是当前节点到根节点路径上黑色节点的数量blackcount;return _Balance(root-_left, blackcount, refvalue) _Balance(root-_right, blackcount, refvalue); //放在后面从前往后
}void _Inorder(Node* root) //中序遍历
{if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first endl;_Inorder(root-_right);
}#define _CRT_SECURE_NO_WARNINGS 1
#includeRBTree.hvoid test1()
{int a[] { 5, 4, 8, 6, 2, 9, 1, 3, 7 };RBTreeint, int rb;for (auto e : a){rb.insert(make_pair(e, e));}rb.Inorder();cout rb.Balance() endl;
}int main()
{test1();return 0;
}12. 红黑树与AVL树的比较 红黑树和AVL树都是高效的平衡二叉搜索树增删查改的时间复杂度都为O(longn)但红黑树不要求绝对平衡只需保证最长路径的长度不超过最短路径长度的两倍相对而言降低了插入、删除时旋转的次数所以在经常进行增删查改的结构中红黑树的性能更优在实际应用红黑树的更多。 AVL树的高度接近于longn,红黑树的高度接近于2longn,所以搜索效率AVL树略优于红黑树但是几乎可以忽略不记因为n足够大时longn就足够小两者的差距微乎其微。当插入同样得数据AVL树的高度更低通过多次旋转达到的。
