网站建设合约具体内容,wordpress 主题 设计,软文是什么文章,wordpress 搭建wiki学了很久编程了#xff0c;红黑树在我们耳边早就如雷贯耳#xff0c;都说他是数据结构中最难的几种结构了#xff0c;但是#xff0c;实际上学会了之后#xff0c;你会发现他还是很简单的#xff0c;个人认为他还没有AVL树的旋转难#xff0c;好了#xff0c;老规矩红黑树在我们耳边早就如雷贯耳都说他是数据结构中最难的几种结构了但是实际上学会了之后你会发现他还是很简单的个人认为他还没有AVL树的旋转难好了老规矩来上代码
#pragma once
#pragma once
#include iostream
#include set
#include map
#include assert.h
#include math.h
#include vector
using namespace std;
namespace cc
{enum colour{RED,BLACK};templateclass K, class Vstruct RBtreenode{colour _col;pairK, V _val;RBtreenodeK, V* _left;RBtreenodeK, V* _right;RBtreenodeK, V* _parent;RBtreenode(const pairK, V x):_val(x), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}};templateclass K, class Vclass RBtree{public:typedef RBtreenodeK, V node;void reor(node* parent){node* sub parent-_left;node* subr sub-_right;if (_root parent){_root sub;sub-_parent nullptr;sub-_right parent;parent-_parent sub;parent-_left subr;if (subr)subr-_parent parent;}else{node* pparent parent-_parent;if (pparent-_left parent)pparent-_left sub;elsepparent-_right sub;sub-_parent pparent;sub-_right parent;parent-_parent sub;parent-_left subr;if (subr)subr-_parent parent;}}void reol(node* parent){node* sub parent-_right;node* subl sub-_left;if (_root parent){_root sub;sub-_parent nullptr;sub-_left parent;parent-_parent sub;parent-_right subl;if (subl)subl-_parent parent;}else{node* pparent parent-_parent;if (pparent-_left parent)pparent-_left sub;elsepparent-_right sub;sub-_parent pparent;sub-_left parent;parent-_parent sub;parent-_right subl;if (subl)subl-_parent parent;}}bool insert(const pairK, V x){if (_root nullptr){_root new node(x);_root-_col BLACK;return true;}node* parent nullptr;node* cur _root;while (cur){if (x.first cur-_val.first){parent cur;cur cur-_left;}else if (x.first cur-_val.first){parent cur;cur cur-_right;}elsereturn false;}cur new node(x);if (parent-_val.first x.first)parent-_left cur;elseparent-_right cur;cur-_parent parent;node* grandfather parent-_parent;while (parent parent-_col RED){if (grandfather-_left parent){node* uncle grandfather-_right;//情况一只染色if (uncle uncle-_col RED){uncle-_col BLACK;parent-_col BLACK;grandfather-_col RED;if (grandfather _root){grandfather-_col BLACK;break;}}//情况二三旋转染色else if (uncle uncle-_col BLACK){if (parent-_left cur){//单旋reor(grandfather);//染色grandfather-_col RED;parent-_col BLACK;}else{//双旋reol(parent);reor(grandfather);//染色cur-_col BLACK;//爷爷节点变红grandfather-_col RED;}break;}else if (uncle nullptr){if (parent-_left cur){reor(grandfather);grandfather-_col RED;parent-_col BLACK;}else{reol(parent);reor(grandfather);grandfather-_col RED;cur-_col BLACK;}break;}}else{node* uncle grandfather-_left;if (uncle uncle-_col RED){uncle-_col BLACK;parent-_col BLACK;grandfather-_col RED;if (_root grandfather){grandfather-_col BLACK;break;}}else if (uncle uncle-_col BLACK){if (parent-_left cur){reor(parent);reol(grandfather);grandfather-_col RED;cur-_col BLACK;}else{reol(grandfather);grandfather-_col RED;parent-_col BLACK;}break;}else if (uncle nullptr){if (parent-_left cur){reor(parent);reol(grandfather);cur-_col BLACK;grandfather-_col RED;}else{reol(grandfather);parent-_col BLACK;grandfather-_col RED;}break;}}cur grandfather;parent cur-_parent;grandfather parent-_parent;}return true;}bool check(){return _check(_root);}void print(){prin(_root);}void prin(node* root,int num){if (root nullptr)return;if (root-_col BLACK)num;if (root-_left root-_right root-_left nullptr)cout num endl;prin(root-_left,num);prin(root-_right,num);}bool _check(node* root){if (root nullptr){if (root-_col ! BLACK)exit(-1);return true;}if (root-_parent root-_parent-_col RED){cout 异常退出 endl;exit(-1);}int num 0;prin(root, num);}private:node* _root nullptr;};
}其实和AVL树的代码差不多唯一不同的是我们没有平衡因子了但是有颜色。
下面来说说红黑树的规则
1.一个节点不是红色就是黑色
2.根节点必须是黑色
3.红色节点的两个孩子必须是黑色节点
4.每条路径的黑色节点个数相同
5.叶子结点NIL节点是黑色的
上面就是红黑树的规则红黑树的代码就在上面现在说一下红黑树的具体实现规则
1.如果叔叔节点存在且叔叔节点为红色那么把父节点和叔叔节点染成黑色组父节点染成红色如果此时的祖父节点是根节点那么就在把祖父节点染成黑色。如果不是就把新插入的节点更新成祖父节点依次往上更新直到父节点为空或是父节点的颜色为黑色就停止。
2.如果叔叔节点存在且叔叔节点是黑色的那么此时就要判断新插入的节点在父节点的左还右如果父节点祖父节点新插入的节点成一条线那么此时就是单旋然后旋转完成之后把父节点染成黑色祖父节点染成红色。
3.如果叔叔节点存在且为黑色新插入节点与父节点祖父节点形成折线那么此时应该是双旋旋转完成之后把新插入的节点染成黑色祖父节点染成红色。
4.如果叔叔节点不存在那就看是上面的额那种情况是那种旋转找到对应的旋转就好了。
以上就是实现红黑树代码的具体细节。
AVL树和红黑树的对比
其实AVL树和红黑树两个各有各的好处是的个人认为两个各有各的好处因为AVL对树高比较严格所以导致旋转点额次数就多所以就会有额外的消耗但是红黑树就没有这么多的消耗了因为红黑树的上面几个规则导致红黑树最长路径不得超过对短路径的两倍所以红黑树也会旋转但是插入同等节点的条件下红黑树旋转点次数肯定比AVL树少但是AVL树是严格的logn而红黑树是不太严格的logn所以我说是各有各的好。
以上就是红黑树的规则讲解以及代码实现。希望大家能够多多支持谢谢
