做网站php和asp哪个好,wordpress登录下载附件,怎么建设婚恋网站,网站设计学习目录 一、红黑树的概念二、红黑树的性质三、红黑树的插入操作四、红黑树的验证五、红黑树和AVL树的比较六、代码 一、红黑树的概念 红黑树#xff0c;是一种二叉搜索树#xff0c;但在每个结点上增加一个存储位表示结点的颜色#xff0c;可以是Red或Black。 通过对任何一条从… 目录 一、红黑树的概念二、红黑树的性质三、红黑树的插入操作四、红黑树的验证五、红黑树和AVL树的比较六、代码 一、红黑树的概念 红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。 二、红黑树的性质 红黑树有以下五点性质 每个结点不是红色就是黑色。根结点是黑色的。如果一个结点是红色的则它的两个孩子结点是黑色的。(没有连续的红结点)对于每个结点从该结点到其所有后代叶子结点的简单路径上均包含相同数目的黑色结点。(每条路径上的黑色结点数量相同)每个叶子结点都是黑色的此处的叶子结点指定是空结点。 为什么满足上面的性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点给树的两倍呢 1.根据红黑树的性质我们可以知道黑节点的孩子可以是黑节点但是必须保证每条路径上黑色节点的数量相等全黑节点的路径就是最短路径。 2.红节点的孩子节点不能是红节点我们可以知道在每条路径黑色节点已经定长的时候红色节点最少可以是0个最多可以是和黑色节点相同数量的节点不考虑子节点为空因为空也代表黑色节点所以在黑色节点和红色节点相间时可以找到最长路径最长路径的长度范围最大也就是两倍的黑色节点数量。 3.最短路径长度是全黑色节点的数量最长路径长度是红黑相间的路径长度也就是最多是黑色节点的两倍所有我们可以知道红黑树的最长路径长度不会超过最短路径长度的2倍 三、红黑树的插入操作 对于红黑树的插入来说我们都是要通过构造红黑树节点来进行插入的那么就有一个问题究竟是构造红节点还是黑节点呢 以上图为例当插入的是红节点时其父节点如果是黑色那么将不需要调整红黑树如果是红色节点也只是影响局部简单调整但是插入黑色节点就不一样了无论你插在哪里对整棵树的影响很大,所以我们可以插入红色节点然后往上调整。 在插入节点时如果父亲节点是黑色则不需要去处理如果插入的节点的父亲节点是红色我们分两种情况去讨论①叔叔节点存在且叔叔节点是红色节点 ②叔叔节点存在且为黑色节点或者叔叔节点不存在此时我们需要进行旋转操作。 情况一 叔叔节点存在且为红色 情况二 叔叔节点存在且为黑/不存在 ① p为g的左节点cur为p的左节点需要进行右单旋 ② p为g的左节点cur为g的右节点需要进行左右双旋 ③ p为g的右节点cur为p的右节点需要进行左单旋 ④ p为g的右节点cur为p的左节点需要进行右左单旋 四、红黑树的验证 先利用中序遍历看他是否是一颗搜索树 void InOrder()
{_InOrder(_root);
}void _InOrder(Node* root)
{if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);
}根据红黑树的性质进行判断 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-_left;}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-_colRED){//该节点为红色节点那么他一定存在父亲节点cout 存在连续的红色节点 endl;return false;} //递归return _Check(root-_left,blackNum,benchmark) _Check(root-_right,blackNum,benchmark);}五、红黑树和AVL树的比较 红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。 六、代码
#pragma once
#includeiostream
#includeassert.henum Color { RED, BLACK };templateclass T
struct RBTreeNode
{RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;Color _col;RBTreeNode(const T data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};templateclass T,class Ref,class Ptr
struct _RBTreeIterator
{typedef RBTreeNodeT Node;typedef _RBTreeIteratorT, Ref, Ptr Self;typedef _RBTreeIteratorT, T, T* iterator;Node* _node;_RBTreeIterator(Node* node):_node(node){}_RBTreeIterator(const iterator it){_node it._node;}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self s){return _node ! s._node;}Self operator(){if (_node-_right){//右不为空下一个就是右子树的最左几点Node* subLeft _node-_right;while (subLeft-_left){subLeft subLeft-_left;}_node subLeft;}else {//右为空沿着根的路径找孩子是父亲左的那个祖先Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_right){cur parent;parent parent-_parent;}_node parent;}return *this;}Self operator--(){if (_node-_left){//左不为空下一个就是左子树的最右节点Node* subRight _node-_left;while(subRight-_right){subRight subRight-_right;}_node subRight;}else {//左为空沿着根的路径孩子是父亲的右的祖先Node* cur _node;Node* parent cur-_parent; while (parent cur parent-_left){cur parent;parent parent-_parent;}_node parent;}return *this;}
};templateclass K, class T,class KeyOft
class RBTree
{typedef RBTreeNodeT Node;
public:typedef _RBTreeIteratorT, T, T*iterator;typedef _RBTreeIteratorT, const T, const T*const_iterator;iterator begin(){Node* cur _root;while (cur cur-_left){cur cur-_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}//查找Node* Find(const K key){Node* cur _root;KeyOft kot;while (cur){if (kot(cur-_data) key){cur cur-_right;}else if (kot(cur-_data) key){cur cur-_left;}else{return cur;}}}//析构函数~RBTree(){_Destory(_root);_root nullptr;}
public:pairiterator,bool Insert(const T data){if (_root nullptr){//根节点为空创建一个节点为根节点_root new Node(data);_root-_col BLACK;return make_pair(iterator(_root),true);}KeyOft kot;Node* parent nullptr;Node* cur _root;while (cur){if (kot(cur-_data) kot(data)){parent cur;cur cur-_left;}else if (kot(cur-_data) kot(data)){parent cur;cur cur-_right;}else return make_pair(iterator(cur),false); //要插入的元素已经存在返回 false}cur new Node(data);Node* newnode cur;if (kot(cur-_data) kot(parent-_data)){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;while (parent parent-_col RED){Node* grandfather parent-_parent;if (grandfather-_left parent){Node* uncle grandfather-_right;if (uncle uncle-_col RED){//叔叔节点存在并且是红色节点parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续往上调整cur grandfather;parent cur-_parent;}else {//叔叔节点不存在或者存在但为黑//旋转 变色// g// p u// cif (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;parent-_col RED;grandfather-_col RED;}break;}}else if (grandfather-_right parent){Node* uncle grandfather-_left;if (uncle uncle-_col RED){//叔叔节点存在并且是红色节点parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续往上调整cur grandfather;parent cur-_parent;}else {//叔叔节点不存在或者存在但为黑//旋转 变色// g// u p// cif (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;parent-_col RED;grandfather-_col RED;}break;}}}_root-_col BLACK; //把根变成黑色return make_pair(iterator(newnode),true);}void InOrder(){ _InOrder(_root);cout endl;}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-_left;}return _Check(_root, 0, benchmark);}
private:void _Destory(Node* root){//析构后续遍历销毁if (root nullptr){return;}_Destory(root-_left);_Destory(root-_right);delete root;}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-_col RED){//该节点为红色节点那么他一定存在父亲节点cout 存在连续的红色节点 endl;return false;}return _Check(root-_left, blackNum, benchmark) _Check(root-_right, blackNum, benchmark);}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}void RotateL(Node* parent) //左单旋{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent; //subRL可能为空Node* ppnode parent-_parent;subR-_left parent; //parent节点成为subR的左子树节点parent-_parent subR;if (ppnode nullptr) //判断当前传入的节点是否为根节点{_root subR;_root-_parent nullptr;}else {if (ppnode-_left parent){ppnode-_left subR;}else {ppnode-_right subR;}subR-_parent ppnode; //subR 成为当前子树的根节点}}void RotateR(Node* parent) //右单旋{Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* ppnode parent-_parent;subL-_right parent;parent-_parent subL;if (ppnode nullptr){_root subL;subL-_parent nullptr;}else{if (parent ppnode-_left){ppnode-_left subL;}else {ppnode-_right subL;}subL-_parent ppnode;}}private:Node* _root nullptr;
};void RBTreeTest()
{//RBTreeint, int t1;//int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16,14 };//for (auto e : a)//{// t1.Insert(make_pair(e, e));//}//t1.InOrder();//cout t1.IsBalance() endl;
}
