C++ 浅谈之 AVL 树和红黑树

C++ 浅谈之 AVL 树和红黑树

HELLO，各位博友好，我是阿呆 🙈🙈🙈

这里是 C++ 浅谈系列，收录在专栏 C++ 语言中 😜😜😜

本系列阿呆将记录一些 C++ 语言重要的语法特性 🏃🏃🏃

OK，兄弟们，废话不多直接开冲 🌞🌞🌞

一 🏠 概述

AVL 树

上文提到对于二叉搜索树有单边树的缺陷，那么对于 STL 关联容器 map、set 等底层结构对其进行了平衡处理，采用平衡树实现

AVL 树，当向二叉搜索树插入新结点后，保证每个结点左右子树高度差绝对值不超过 1 ，降低树高度，减少平均搜索长度

概念

AVL 树是空树或具有如下性质的二叉搜索树

① 左右子树都是 AVL 树

② 左右子树高度之差 ( 简称平衡因子 : 右子树高 - 左子树高 ) 绝对值不超过 1

一棵二叉搜索树高度平衡，它就是 AVL 树。如果它有 n 个结点，其高度可保持在 O(log2N)，搜索时间复杂度 O(log2N)

AVL 树节点定义

template<class K,class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;//定义成三叉链的形式int _bf;//balance factor平衡因子pair<K, V> _kv;//用pair同时存K和V两个数据AVLTreeNode(const pair<K,V>& kv)//节点构造函数:_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0)//平衡因子初始给0,_kv(kv){}
};

AVL 树插入

AVL 树是在二叉搜索树基础上引入平衡因子，插入过程如下

① 按照二叉搜索树方式找到空位置，插入新节点

② 插入新节点后，需要调整节点的平衡因子

③ 插入元素后可能导致 AVL 树左右子树高度不符合条件，需要旋转

AVL 树旋转

AVL树的旋转分为多种，具体举出一种如下图所示（右单旋）

Parent 平衡因子为 2 或 -2 ，分以下情况

① 平衡因子为 2，说明右子树高，需要往左边压高度，设 Parent 右子树根为 SubR

当 SubR 平衡因子为 1 时，执行左单旋

当 SubR 平衡因子为 -1 时，执行右左双旋

② 平衡因子为 -2，说明左子树高，需要往右边压高度，设 Parent 左子树根为 SubL

当 SubL 平衡因子为 -1 时，执行右单旋

当 SubL 平衡因子为 1 时，执行左右双旋

旋转完成后，原 Parent 为根子树个高度降低，已经平衡（无需往上更新，直接退出循环）

AVL 树模拟实现

#pragma once
#include<iostream>
#include<assert.h>
#include<string>
using namespace std;template<class K,class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;//定义成三叉链的形式int _bf;//balance factor平衡因子pair<K, V> _kv;//用pair同时存K和V两个数据AVLTreeNode(const pair<K,V>& kv)//节点构造函数:_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0)//平衡因子初始给0,_kv(kv){}
};template<class K,class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:AVLTree():_root(nullptr){}//拷贝构造和赋值拷贝也需要自己实现AVLTree(const AVLTree<K,V>& kv){_root = Copy(kv._root);}AVLTree<K, V>& operator=(AVLTree<K,V> kv){swap(_root, kv._root);return *this;}~AVLTree(){Destroy(_root);_root = nullptr;}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newroot = new Node(root->_key);//建立新节点newroot->_left = Copy(root->_left);//新节点的左右节点再去转换成子问题newroot->_right = Copy(root->_right);return newroot;//最后返回新节点}void Destroy(Node* root){//利用后序遍历去释放节点if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;}V& operator[](const K& key)//重载operator[]{//operator[]的原则是://如果插入成功返回插入都value的引用//如果插入失败则返回V类型默认缺省值pair<Node*, bool> ret = Insert(make_pair(key, V()));//V采用传匿名对象的方式return ret.first->_kv.second;}Node* Find(const pair<K, V>& kv)//查找函数{Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){cur = cur->_right;}else if (kv.first < cur->_kv.first){cur = cur->_left;}else{return cur;}}return nullptr;}void RotateR(Node* parent)//右单旋{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR != nullptr)//注意:这里一定要判断不为空的，因为下面可能会出现空指针的解引用{subLR->_parent = parent;}subL->_right = parent;Node* parentParent = parent->_parent;//一定要在改变链接关系之前把这个指针存下来parent->_parent = subL;//if (parentParent == nullptr)或者采用这个条件也是可以的if(parent==_root){_root = subL;_root->_parent = nullptr;}else{//这里注意:parent还有父母时，链接之前需要注意判断到底是右孩子还是左孩子if (parentParent->_left == parent)parentParent->_left = subL;elseparentParent->_right = subL;subL->_parent = parentParent;//最后还要把父指针关系链接上}parent->_bf = subL->_bf = 0;//最后右单旋完成后平衡因子都要修改成0}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;//先把subR的左孩子赋值给parent的右节点parent->_right = subRL;if (subRL != nullptr)//注意一定要判断是否为空的情况{subRL->_parent = parent;//然后链接parent指针}//然后subR的左节点链接上parentsubR->_left = parent;Node* parentParent = parent->_parent;//提前记录parent->_parent = subR;//if (parentParent == nullptr)if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (parentParent->_left == parent)parentParent->_left = subR;elseparentParent->_right = subR;subR->_parent = parentParent;}parent->_bf = subR->_bf = 0;}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;//注意：需要提前存subRL的平衡因子，因为旋转可能引起改变//subRL的平衡因子是双旋的关键节点RotateR(parent->_right);//先进行右旋，并注意旋转点为父节点的右节点RotateL(parent);//再进行左旋，此时旋转点为父节点if (bf == 0){parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}else if (bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}//注意这里处理完成过后sunRL的平衡因子一定都是等于0的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){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}//注意这里处理完成过后sunRL的平衡因子一定都是等于0的else{assert(false);}}pair<Node*,bool> Insert(const pair<K, V>& kv){if (_root == nullptr)//根节点为空时先new一个新节点{_root = new Node(kv);return make_pair(_root, true);}Node* cur = _root;Node* parent = nullptr;//先利用while循环去找cur的空位while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return make_pair(cur, false);}}//将cur插入到相应位置cur = new Node(kv);Node* newnode = cur;//用一个newnode记录一下新节点用以返回if (kv.first > parent->_kv.first){parent->_right = cur;//注意三叉链的链接逻辑顺序,等号左右方向不能反，先把cur链接到父节点的右边cur->_parent = parent;//然后再去把父指针知道父节点}else{parent->_left = cur;cur->_parent = parent;}//进行旋转调整//while(cur!=_root)while (parent){//1.进入循环先对平衡因子进行调整if (cur == parent->_right){parent->_bf++;}else{parent->_bf--;}//分三种情况向上走if (parent->_bf == 0)//平衡因子等于0不需要调整{//为什么不需调整//因为等于0的话，说明底层子树高度不平衡，添加进入新元素后平衡了，只要平衡了高度并没发生变化，不会影响上面的父节点break;}else if (parent->_bf == -1 || parent->_bf == 1){//平衡因子等于-1，说明插入新节点后子树的高度不平衡了，需要继续往上迭代查看父节点是否还满足平衡节点cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){if (parent->_bf == -2)//父节点等于-2，说明左边高，触发右旋的情况{if (cur->_bf == -1)//cur节点等于-1，说明在cur的左边更高，触发右单旋的情况{RotateR(parent);}else//cur等于-1,说明在cur的右边更高，触发左右双旋{RotateLR(parent);}}else//父节点等于1，说明右边更高，触发左旋的情况{if (cur->_bf == 1)//cur节点等于1时，说明在cur的右边更高，触发右单旋的情况{RotateL(parent);}else//cur等于-1,说明在cur的左边更高，触发右左双旋{RotateRL(parent);}}//思考：为什么上面在传参数的时候，都是传parent的节点呢？这样的好处是什么呢break;//调整完成后break退出循环//这里为什么调整完成过后就可以退出，通过旋转调整平衡因子后，parent节点的平衡因子都为0了，调整过后不需要再向上继续查找了}else{assert(false);}}return make_pair(newnode,true);}void _Inorder(Node* root)//中序遍历打印每个节点{if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_Inorder(root->_right);}void Inorder(){_Inorder(_root);cout << endl;}//验证是否为平衡二叉树//1.左子树高度与右子树高度差必须小于1int _Height(Node* root)//求树的高度函数{if (root == nullptr){return 0;}int leftHeight = _Height(root->_left);//递归去子问题求解int rightHeight = _Height(root->_right);return rightHeight > leftHeight ? rightHeight + 1 : leftHeight + 1;}bool _IsBalance(Node* root){if (root == nullptr){return true;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);// 2.检查一下每颗树的平衡因子是否正确if (rightHeight - leftHeight != root->_bf){cout << "平衡因子异常:" << root->_kv.first << endl;return false;}return abs(rightHeight - leftHeight) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);//分别递归到各自的左右子树再去检查}bool IsAVLTree(){return _IsBalance(_root);}
private:Node* _root;
};

二 🏠 核心

红黑树

红黑树的概念

一种二叉搜索树，在每个结点上增加一个存储位表示结点颜色，Red 或 Black。确保没有一条路径会比其他路径长 2 倍，因而接近平衡

红黑树性质

红黑树的定义

1. 每个结点不是红就是黑
2. 根节点是黑色
3. 一个节点是红，则两个孩子是黑 ( 没有连续红节点 )
4. 每条路径上包含相同数量黑节点
5. 每个叶子结点都是黑 ( 此处指的是空结点，即 NIL 节点 )

为什么红黑树能保证最长路径中节点个数不会超过最短路径的两倍 ？

假设黑节点数量 N 个，最短路径为 ：logN，最长路径为 ：2 * logN . 所以最长路径节点数不会超过最短路径的两倍

红黑树节点定义

enum Colour
{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;//节点中存放的键值对Colour _col;//节点的颜色RBTreeNode(const pair<K,V> kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};

为什么节点默认颜色是红色 ？

因为默认颜色黑色，将破坏定义四，其它每条路径都会因该路径增加一个黑节点而不满足红黑树性质，这是一种全局的破坏；默认颜色红色，会破坏定义三，但只会影响当前路径，并不会对其它路径造成影响

红黑树插入操作

可分为两步

1. 按照二叉搜索树规则插入新节点

2. 检测新节点插入后，红黑树性质是否造到破坏

如果父节点是黑色（未违反红黑树任何性质），则不需要调整；

父节点为红色时，违反了定义三不能有连在一起的红色节点

此时对红黑树有多种情况，如下图为其中一种讨论

红黑树模拟实现

#pragma once
#include<iostream>
using namespace std;enum Colour
{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;//节点中存放的T类型的数据Colour _col;//节点的颜色RBTreeNode(const pair<K,V> kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:RBTree():_root(nullptr){}//拷贝构造和赋值拷贝也需要自行实现这里不做赘述~RBTree(){Destory(_root);_root = nullptr;}void Destory(Node* root){if (root == nullptr){return;}//利用后序遍历释放节点Destory(root->_left);Destory(root->_right);delete root;}void RotateR(Node* parent)//右单旋{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR != nullptr)//注意:这里一定要判断不为空的，因为下面可能会出现空指针的解引用{subLR->_parent = parent;}subL->_right = parent;Node* parentParent = parent->_parent;//一定要在改变链接关系之前把这个指针存下来parent->_parent = subL;//if (parentParent == nullptr)或者采用这个条件也是可以的if (parent == _root){_root = subL;_root->_parent = nullptr;}else{//这里注意:parent还有父母时，链接之前需要注意判断到底是右孩子还是左孩子if (parentParent->_left == parent)parentParent->_left = subL;elseparentParent->_right = subL;subL->_parent = parentParent;//最后还要把父指针关系链接上}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;//先把subR的左孩子赋值给parent的右节点parent->_right = subRL;if (subRL != nullptr)//注意一定要判断是否为空的情况{subRL->_parent = parent;//然后链接parent指针}//然后subR的左节点链接上parentsubR->_left = parent;Node* parentParent = parent->_parent;//提前记录parent->_parent = subR;//if (parentParent == nullptr)if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (parentParent->_left == parent)parentParent->_left = subR;elseparentParent->_right = subR;subR->_parent = parentParent;}}pair<Node*, bool> Insert(const pair<K, V> kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//根节点给黑色return make_pair(_root, true);}Node* cur = _root;Node* parent = nullptr;while (cur)//循环去找空位{if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if(kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return make_pair(cur, false);}}Node* newnode = new Node(kv);newnode->_col = RED;//链接上新节点if (kv.first > parent->_kv.first){parent->_right = newnode;newnode->_parent = parent;}else{parent->_left = newnode;newnode->_parent = parent;}cur = newnode;//父节点存在且父节点为红色时需要继续处理while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//关键看叔叔的脸色if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//具体变色的情况需要画图分析:grandfather->_col = RED;parent->_col = uncle->_col = BLACK;//注意需要继续向上处理,容易忘记cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_left){RotateR(grandfather);//右单旋parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);//先以父节点为旋转点左旋RotateR(grandfather);//再以g为旋转点右旋cur->_col = BLACK;grandfather->_col = RED;}break;//旋转+变色过后一定是满足所有性质的直接退出循环}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){uncle->_col = parent->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else // 情况2：+ 情况3：{if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else // cur == parent->_left{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(newnode, true);}void _InOrder(Node* root)//中序遍历递归打印{if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":"<<root->_kv.second<<endl;_InOrder(root->_right);}void InOrder(){_InOrder(_root);cout << endl;}bool _CheckBlance(Node* root, int blackNum, int count)//balckNum相当于一个标尺，count就是用来记录每条路径的黑节点数目{if (root == nullptr)//如果root走到空节点{if (count != blackNum)//count不等于最左路径的黑色节点数{cout << "黑色节点的数量不相等" << endl;return false;//返回假}return true;//否则返回真}if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){count++;}return _CheckBlance(root->_left, blackNum, count)&& _CheckBlance(root->_right, blackNum, count);//再递归到各子树的子问题}bool CheckBlance(){if (_root == nullptr){return true;}if (_root->_col == RED){cout << "根节点是红色的" << endl;return false;}// 找最左路径做黑色节点数量参考值int blackNum = 0;Node* left = _root;while (left){if (left->_col == BLACK){blackNum++;}left = left->_left;}int count = 0;return _CheckBlance(_root, blackNum, count);}
private:Node* _root;
};

红黑树与 AVL 树比较

都是高效平衡二叉树，增删改查时间复杂度都是 O( log2N) ，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径 2 倍，降低了插入和旋转次数，所以在经常进行增删结构中性能比 AVL 树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多

三 🏠 结语

身处于这个浮躁的社会，却有耐心看到这里，你一定是个很厉害的人吧 👍👍👍

各位博友觉得文章有帮助的话，别忘了点赞 + 关注哦，你们的鼓励就是我最大的动力

博主还会不断更新更优质的内容，加油吧！技术人！ 💪💪💪