做电影资源网站有哪些,网站建设 有限公司,dedecms源码下载,2023年火爆的新闻目录
#x1f308;前言#x1f308;
#x1f4c1; 红黑树的概念
#x1f4c1; 红黑树的性质
#x1f4c1; 红黑树节点的定义
#x1f4c1; 红黑树的插入操作
#x1f4c1; 红黑树和AVL树的比较
#x1f4c1; 全代码展示
#x1f4c1; 总结 #x1f308;前言… 目录
前言 红黑树的概念 红黑树的性质 红黑树节点的定义 红黑树的插入操作 红黑树和AVL树的比较 全代码展示 总结 前言 欢迎大家观看本期【C杂货铺】本期内容将讲解二叉搜索树的进阶——红黑树。红黑树是一种二叉搜索树通过控制每个节点的颜色来调整整棵树的高度。 红黑树是set和map实现的底层实现在下一期内容我们将讲解STL中set和map的模拟实现。如果你对二叉搜索树还不是很了解可以快速阅览下面这篇文章; 【C杂货铺】二叉搜索树-CSDN博客 红黑树的概念 红黑树是一种二叉搜索树在每个节点增加一个存储位表示节点的颜色可以是Red或Black。通过对任何一条从根到叶子的路径上各个节点着色方式的限制红黑树确保没有一条路径会比其他路径长出两倍因而接近平衡的。 红黑树的性质
1. 每个节点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的那么它的两个孩子节点是黑色的
4. 对于每个节点从该节点到其他所有后代叶节点的简单路径上均包含相同数目的黑色节点个数
5. 每个叶子结点都是黑色的(此后的叶子结点指的是空节点) 红黑树节点的定义
// 节点的颜色
enum Color{RED, BLACK};
// 红黑树节点的定义
templateclass ValueType
struct RBTreeNode
{RBTreeNode(const ValueType data ValueType()Color color RED): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _color(color){}RBTreeNodeValueType* _pLeft; // 节点的左孩子RBTreeNodeValueType* _pRight; // 节点的右孩子RBTreeNodeValueType* _pParent; // 节点的双亲(红黑树需要旋转为了实现简单给
出该字段)ValueType _data; // 节点的值域Color _color; // 节点的颜色
}; 红黑树的插入操作 红黑树是在二叉搜索树的基础上加上其平衡限制条件因此红黑树的插入可分为两步
1. 按照二叉搜索树规则插入新节点 新插入节点的默认颜色是红色。因为红色容易控制规则如果默认插入黑色需要保证从当前节点到叶子节点具有相同的黑色节点个数不易控制。 即先保证性质4不被违反再来判断性质3是否被违反如果违反就进行调整。
2. 检测新节点插入后红黑树的性质是否遭到破坏。 如果双亲节点的颜色是黑色没有违反规则则不需要调整当新插入节点的双亲节点颜色为红色时就违反了性质3即不能有连续在一起的红色节点此时需要进行调整可分为两种情况
约定cur为当前节点p为父亲节点g为祖父节点u为叔叔节点
● 情况1cur为红p为红g为黑u存在且为红 ● 情况2cur为红p为红g为黑u存在且为黑 或者 u不存在 当如子树如下图所示时需要对红黑树进行双旋先以p为根进行左旋再以g为根进行右旋。下图是p在g的左子树的情况考虑一下p在g的右子树且cur为p的左子树的情况。 红黑树和AVL树的比较 红黑树和AVL数都是搞笑的平衡二叉树增删查改的时间复杂度都是O(log N)红黑树不追求绝对平衡其只需要保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL数更优而且红黑树的实现比较简单所以实际应用中红黑树更多。 map和set的底层就是红黑树。 全代码展示
template class T
struct RBTreeNode
{typedef RBTreeNodeT Node;RBTreeNode(const T val T()):_left(nullptr), _right(nullptr), _parent(nullptr), _val(val), _color(RED){}Node* _left;Node* _right;Node* _parent;T _val;Color _color;
};templateclass T
class RBTree
{typedef RBTreeNodeT Node;
public:bool Insert(const T val){if (_root nullptr){_root new Node(val);_root-_color Black;return true;}Node* cur _root;Node* parent nullptr;while (cur){if (cur-_val val){parent cur;cur cur-_left;}else if (cur-_val val){parent cur;cur cur-_right;}else{return false;}}cur new Node(val);if (parent-_val val){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;//调整颜色不能出现连续的红色while (parent parent-_color RED){Node* grandfather parent-_parent;if (parent grandfather-_left){//叔叔在右边//1. 叔叔存在且为红色Node* uncle grandfather-_right;if (uncle uncle-_color RED){grandfather-_color RED;uncle-_color parent-_color Black;cur grandfather;parent cur-_parent;}//2. 叔叔存在且为黑色 || 叔叔不存在else{/*gp uc */if (cur parent-_left){RotateR(grandfather);parent-_color Black;grandfather-_color RED;}/*gp uc*/else{RotateL(parent);RotateR(grandfather);cur-_color Black;grandfather-_color RED;}break;}}else{//叔叔在左边//1. 叔叔存在且为红色Node* uncle grandfather-_left;if (uncle uncle-_color RED){grandfather-_color RED;parent-_color uncle-_color Black;cur grandfather;parent cur-_parent;}//2. 叔叔存在且为黑色 || 叔叔不存在else{/*gu pc*/if (cur parent-_right){RotateL(grandfather);parent-_color Black;grandfather-_color RED;}/*gu pc */else{RotateR(parent);RotateL(grandfather);cur-_color Black;grandfather-_color RED;}break;}}}_root-_color Black;return true;}//遍历
void InOrder()
{_InOrder(_root);cout endl;
}bool isBalance()
{if (_root nullptr){return true;}int BlackNum 0;Node* cur _root;while (cur){if (cur-_color Black)BlackNum;cur cur-_right;}return _isBalance(_root,0,BlackNum);
}protected:bool _isBalance(Node* root,int count , const int BlackNum){if(root nullptr){if (count ! BlackNum)return false;return true;}if (root-_color RED root-_parent-_color RED){cout red endl;return false;}if (root-_color Black)count;return _isBalance(root-_left,count,BlackNum) _isBalance(root-_right,count,BlackNum);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_val endl;_InOrder(root-_right);}//左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;Node* pparent parent-_parent;parent-_parent subR;if (parent _root){_root subR;_root-_parent nullptr;}else{if (parent pparent-_right){pparent-_right subR;}else{pparent-_left subR;}subR-_parent pparent;}}//右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;Node* pparent parent-_parent;parent-_parent subL;if (parent _root){_root subL;_root-_parent nullptr;}else{if (parent pparent-_right){pparent-_right subL;}else{pparent-_left subL;}subL-_parent pparent;}}
private:Node* _root nullptr;
}; 总结 以上就是本期【C杂货铺】的主要内容了讲解了红黑树如果优化二叉搜索树红黑树的概念红黑树实现插入以及红黑树的高度平衡调整此外模拟实现了红黑树。 如果感觉本期内容对你有帮助欢迎点赞收藏关注Thanks♪(ω)
