C++进阶——红黑树

一、红黑树的概念红黑树是一棵二叉搜索树他的每个节点增加一个数据来存储颜色可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束红黑树确保没有一条路径会超出其他路径2倍的长度1.1 红黑树的规则每个节点不是红色就是黑色根节点是黑色的如果一个节点是红的他的孩子节点就是黑色的这意味着任意一条路径不能出现连续的红色节点对任意一个节点从该节点到其所有NULL节点的简单路径上均包含相同数量的黑色节点当我们能时刻满足这四条规则时我们就能确保树上没有一条路径会超出其他路径2倍的长度。1.2 红黑树的效率假设N是红黑树树中结点数量h是最短路径长度则2^h-1N2^(2*h)-1,由此推出h大约为logN也就意味着红黑树增删查改最坏也就是走最长路径2*logN那么时间复杂度还是OlogN红黑树的表达相对AVL树要抽象一些AVL树通过控制高度差直观地控制了平衡。红黑树通过4条规则的约束实现了近似平衡它们的效率都是同一档次但红黑树插入节点时旋转次数更少二、红黑树的实现2.1 红黑树的结构enum Color { RED, BLACK }; templateclass K,class V struct RBTreeNode { pairK, V _kv; Color _col; RBTreeNodeK, V* _parent; RBTreeNodeK, V* _left; RBTreeNodeK, V* _right; RBTreeNode(const pairK,V kv) :_kv(kv) ,_parent(nullptr) ,_left(nullptr) ,_right(nullptr) { } }; templateclass K,class V class RBTree { typedef RBTreeNodeK, V Node; public: RBTree(Node* rootnullptr) :_root(root) { } private: Node* _root; };2.2 红黑树的插入2.2.1 节点插入的大概过程插入一个值按二叉搜索树规则插入插入后只需观察是否符合红黑树的四条规则如果是空树插入新增节点是黑色节点。如果不是空树选中节点必须是红色节点若插入黑色节点会破坏规则4非空树插入后新增节点的父节点如果是黑色就未破坏规则插入结束若父节点是红色的则违反规则3。据下图c是红色p是红色g必为黑色2.2.2 情况1变色若c、p、u均为红色节点g为黑色节点就将p、u变黑g变红再将g变为新的c向上更新2.2.3 情况2单旋变色c、p为红g为黑u不存在或u为黑u不存在c必为新增节点因为若c为原来的g节点那么它因为孩子节点变色而变红原来是黑色节点但u的分支后面没有黑色节点了不满足每条分支黑色节点数量相等u存在且为黑c一定不是新增节点2.2.4 情况3双旋变色c、p为红g为黑u不存在或存在为黑2.3 红黑树的验证规则1枚举颜色类型天然保证了颜色只有黑色和红色规则2可直接验证规则3前序遍历检查遇到红色节点就查孩子不太方便可反过来检查父节点颜色前序遍历遍历时用形参记录当前节点到根黑色节点数量直到空节点再选任意一条路径黑色节点作为参考值依次比较三、全部实现代码#pragma once #includeiostream #includecassert using namespace std; enum Color { RED, BLACK }; templateclass K,class V struct RBTreeNode { pairK, V _kv; Color _col; RBTreeNodeK, V* _parent; RBTreeNodeK, V* _left; RBTreeNodeK, V* _right; RBTreeNode(const pairK,V kv) :_kv(kv) ,_parent(nullptr) ,_left(nullptr) ,_right(nullptr) { } }; templateclass K,class V class RBTree { typedef RBTreeNodeK, V Node; public: RBTree(Node* rootnullptr) :_root(root) { } bool Insert(const pairK, V kv) { Node* newnode new Node(kv); newnode-_col RED; if (_root nullptr) { newnode-_col BLACK; _root newnode; return true; } Node* pcur _root; Node* parent pcur; while (pcur) { parent pcur; if (pcur-_kv.first kv.first) pcur pcur-_right; else if (pcur-_kv.first kv.first) pcur pcur-_left; else { delete newnode; return false; } } //开始插入 pcur newnode; pcur-_parent parent; if (parent-_kv.first kv.first) parent-_left pcur; else parent-_right pcur; while (parent parent-_col ! BLACK) { Node* g parent-_parent; Node* u nullptr; if (g) { if (parent g-_left)u g-_right; else u g-_left; if (u u-_col RED g-_col BLACK)//情况1p、c、u、都是红色g为黑色 { parent-_col BLACK; u-_col BLACK; g-_col RED; pcur g; parent g-_parent; } else if (parentg-_leftpcurparent-_left)//情况2单旋变色 { RotateR(parent); parent-_col BLACK; g-_col RED; break; } else if (parent-_right pcur g-_right parent) { RotateL(parent); parent-_col BLACK; g-_col RED; break; } else if (parent-_rightpcurg-_leftparent)//情况三双旋变色 { RotateL(pcur); RotateR(pcur); pcur-_col BLACK; g-_col RED; break; } else if (parent-_left pcur g-_right parent) { RotateR(pcur); RotateL(pcur); pcur-_col BLACK; g-_col RED; break; } } } _root-_col BLACK; return true; } void Print(Node* root) { if (root nullptr) return; Print(root-_left); cout root-_kv.first : root-_kv.second ; Print(root-_right); } Node* root() { return _root; } Node* Find(const K key) { Node* pcur _root; while (pcur) { if (pcur-_kv.first key) pcur pcur-_left; else if (pcur-_kv.first key) pcur pcur-_right; else return pcur; } return nullptr; } bool Isrbtree(Node* root) { if (_root nullptr)return true; if (root-_col ! BLACK)return false; int refnum 0; Node* cur root; while (cur ! nullptr) { if (cur-_col BLACK)refnum; cur cur-_left; } return Preorder(root,0,refnum); } private: bool Preorder(Node* root, int num, const int ref) { if (root nullptr) { return num ref; } if (root-_col RED root-_parent-_col ! BLACK) { cout 出现连续红色节点 endl; return false; } if (root-_col BLACK) return Preorder(root-_left, num 1, ref) Preorder(root-_right, num 1, ref); if (root-_col RED) return Preorder(root-_left, num, ref) Preorder(root-_right, num, ref); } void RotateR(Node* cur) { Node* parent cur-_parent; Node* grandpa parent-_parent; parent-_left cur-_right; parent-_parent cur; if (cur-_right) cur-_right-_parent parent; if (grandpa) { if (grandpa-_right parent) grandpa-_right cur; else grandpa-_left cur; } else _root cur; cur-_parent grandpa; cur-_right parent; } void RotateL(Node* cur) { Node* parent cur-_parent; Node* grandpa parent-_parent; parent-_right cur-_left; parent-_parent cur; if (cur-_left) { cur-_left-_parent parent; } if (grandpa) { if (grandpa-_right parent) grandpa-_right cur; else grandpa-_left cur; } else _root cur; cur-_parent grandpa; cur-_left parent; } Node* _root; };