电商网站首页设计,深圳品牌床垫,网站建设新发展,唐山seo排名优化快乐的流畅#xff1a;个人主页 个人专栏#xff1a;《C语言》《数据结构世界》《进击的C》 远方有一堆篝火#xff0c;在为久候之人燃烧#xff01; 文章目录 引言一、红黑树的概念二、红黑树的模拟实现2.1 结点2.2 成员变量2.3 插入情况一#xff1a;uncle在左#xff… 快乐的流畅个人主页 个人专栏《C语言》《数据结构世界》《进击的C》 远方有一堆篝火在为久候之人燃烧 文章目录 引言一、红黑树的概念二、红黑树的模拟实现2.1 结点2.2 成员变量2.3 插入情况一uncle在左parent在右如果uncle存在且为红色如果uncle不存在或者存在且为黑色 情况二parent在左uncle在右如果uncle存在且为红色如果uncle不存在或者存在且为黑色 三、红黑树的验证四、红黑树的性能4.1 优势4.2 适用场景 引言
之前学习的AVL树是一种平衡二叉搜索树它追求绝对平衡从而导致插入和删除性能较差。而今天学习的红黑树是另一种平衡二叉搜索树它追求相对平衡使得增删查改的性能都极佳时间复杂度皆为O(log2N)是数据结构中的精华天才般的设想
一、红黑树的概念
红黑树顾名思义其节点有红和黑两种颜色。
之所以新增结点颜色的标记是因为通过结点着色方式的限制能够让红黑树的最长路径不超过最短路径的两倍以保证相对平衡。 红黑树满足五条性质
所有结点非黑即红根结点为黑色NIL结点为黑色红色结点的子结点必为黑色任意结点到其叶子NIL结点的所有路径都包含相同的黑色结点 在红黑树中NIL节点也称为空节点是叶子节点的一种特殊表示。它们不是实际存储数据的节点而是树结构中的占位符用于定义树的边界。所有的红黑树都以NIL节点为叶子节点这些NIL节点在视觉上通常不被画出来。 性质解读
性质4表明不能有连续的红色结点性质4性质5 理论最短路径全为黑色结点理论最长路径红黑相间 这样就保证了最长路径不超过最短路径的两倍。
二、红黑树的模拟实现
2.1 结点
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){}
};细节
使用三叉链增加了指向parent的指针使用KV模型数据存储键值对pair结点储存颜色同时颜色使用枚举结点的颜色初始化为红色
说明为什么结点的颜色初始化为红色呢因为插入新节点时不为根部如果插入黑色就会直接破坏性质5导致每条路径黑结点数目不同而如果插入红色有可能不会破坏性质4所以结点初始化为红色更优。
2.2 成员变量
templateclass K, class V
class RBTree
{
protected:typedef RBTreeNodeK, V Node;
public:
protected:Node* _root nullptr;
};2.3 插入
因为红黑树也是二叉搜索树所以默认成员函数和遍历与之前写的没什么不同这里重点讲解红黑树的插入。
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-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;while (parent parent-_col RED){Node* grandparent parent-_parent;if (grandparent-_right parent)//uncle在左parent在右{Node* uncle grandparent-_left;if (uncle uncle-_col RED)//uncle为红变色向上调整{parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;parent cur-_parent;}else//uncle为空或为黑变色旋转{if (parent-_right cur)//左单旋{RotateL(grandparent);parent-_col BLACK;grandparent-_col RED;}else//右左旋{RotateR(parent);RotateL(grandparent);cur-_col BLACK;grandparent-_col RED;}}}else//parent在左uncle在右{Node* uncle grandparent-_right;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;parent cur-_parent;}else{if (parent-_left cur)//右单旋{RotateR(grandparent);parent-_col BLACK;grandparent-_col RED;}else//左右旋{RotateL(parent);RotateR(grandparent);cur-_col BLACK;grandparent-_col RED;}}}}_root-_col BLACK;return true;
}思路
以二叉搜索树的方式正常插入讨论并调整结点的颜色以及调整结构使之满足红黑树的性质 循环条件while (parent parent-_col RED)
保证了parent存在且为红grandparent存在且为黑 情况一uncle在左parent在右
如果uncle存在且为红色 处理方法
将parent和uncle变黑grandparent变红cur grandparentparent cur-_parent继续向上调整防止grandparent为根节点却变红在循环结束后将根节点变为黑色
如果uncle不存在或者存在且为黑色
当cur在右部外侧时 处理方法
先对grandparent进行左单旋再将parent变黑grandparent变红 当cur在右部内侧时
处理方法
先对parent进行右单旋再对grandparent进行左单旋最后将cur变黑grandparent变红
情况二parent在左uncle在右
如果uncle存在且为红色 处理方法
将parent和uncle变黑grandparent变红cur grandparentparent cur-_parent继续向上调整防止grandparent为根节点却变红在循环结束后将根节点变为黑色
如果uncle不存在或者存在且为黑色
当cur在左部外侧时 处理方法
先对grandparent进行右单旋再将parent变黑grandparent变红 当cur在左部内侧时
处理方法
先对parent进行左单旋再对grandparent进行右单旋最后将cur变黑grandparent变红 红黑树插入的核心口诀uncle存在且为红变色向上调整uncle不存在或为黑变色旋转 附上旋转的实现
void RotateL(Node* parent)
{Node* grandparent parent-_parent;Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL){subRL-_parent parent;}subR-_left parent;parent-_parent subR;if (grandparent){if (grandparent-_right parent){grandparent-_right subR;}else{grandparent-_left subR;}}else{_root subR;}subR-_parent grandparent;
}void RotateR(Node* parent)
{Node* grandparent parent-_parent;Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR){subLR-_parent parent;}subL-_right parent;parent-_parent subL;if (grandparent){if (grandparent-_right parent){grandparent-_right subL;}else{grandparent-_left subL;}}else{_root subL;}subL-_parent grandparent;
}三、红黑树的验证
bool IsBalance()
{if (_root _root-_col RED){cout 根结点为红色 endl;return false;}int benchMark 0;//基准值Node* cur _root;while (cur){if (cur-_col BLACK){benchMark;}cur cur-_right;}return Check(_root, 0, benchMark);
}bool Check(Node* root, int blackNum, int benchMark)
{if (root nullptr){if (blackNum ! benchMark){cout 某条路径黑色结点数量不相等 endl;return false;}return true;}if (root-_col BLACK){blackNum;}if (root-_col RED root-_parent root-_parent-_col RED){cout 存在连续的红色结点 endl;return false;}return Check(root-_left, blackNum, benchMark) Check(root-_right, blackNum, benchMark);
}细节
验证根节点是否为黑先计算出一条路径的黑色结点个数作为基准值再在递归中比较每条路径的黑色结点是否相等若该节点为红检测其parent是否为红判断是否存在连续的红色节点
四、红黑树的性能
4.1 优势
红黑树是高效的平衡二叉树增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对AVL树而言降低了插入和旋转的次数。
4.2 适用场景
因此在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。 真诚点赞手有余香
