福建省百川建设发展有限公司网站,国内域名注册商排行榜,基础网站开发,查询网站ftp地址1.什么是红黑树 红黑树#xff0c;是一种二叉搜索树#xff0c;但在每个结点上增加一个存储位表示结点的颜色#xff0c;可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制#xff0c;红黑树确保没有一条路径会比其他路径长出俩倍#xff0c;因…1.什么是红黑树 红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。 性质 1. 每个结点不是红色就是黑色。 2. 根节点是黑色的。 3. 如果一个节点是红色的则它的两个孩子结点是黑色的即红色不能连续。 4. 对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点即每条路径黑色节点相同。 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 注意黑色节点相同红色节点不连续所以最长路径中节点个数不会超过最短路径节点个数的两倍。
2.红黑树的插入实现
由于红黑树是一颗二叉平衡搜索树所以它的性质和AVL树差不多AVL树的特性左右子树高度差的绝对值不超过一。
红黑树的插入可以分为两部分按照二叉搜索树的规则插入新节点然后判断是否需要旋转交换和改变颜色。
检测新节点的插入需要判断是否破坏了红黑树的性质因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论。
插入代码的实现
#pragma once
using namespace std;
#include assert.h
namespace sss
{enum Color{red,black};templateclass K,class Vstruct RedBlackTreeNode{RedBlackTreeNodeK,V* _left;RedBlackTreeNodeK, V* _right;RedBlackTreeNodeK, V* _parent;pairK, V _date;Color _col;RedBlackTreeNode(const pairK, V datemake_pair(0,0)):_left(nullptr),_right(nullptr),_parent(nullptr),_date(date)//, _col(black){}};templateclass K, class Vclass RedBlackTree{typedef RedBlackTreeNodeK, V Node;public:typedef RedBlackTree Tree;bool insert(const pairK, V date){if (_root nullptr){_root new Node(date);_root-_col black;return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_date date){parent cur;cur cur-_right;}else if (cur-_date date){parent cur;cur cur-_left;}else{return false;}}cur new Node(date);cur-_col red;if (parent-_date.first date. first){parent-_right cur;}else {parent-_left cur;}cur-_parent parent;//Node* uncleparent-_parent-while (parent parent-_col red){Node* grandfater parent-_parent;assert(grandfater);assert(grandfater-_colblack);if (parent grandfater-_left){Node* uncle grandfater-_right;// 情况一 : uncle存在且为红变色继续往上处理if (uncle uncle-_col red){parent-_col uncle-_col black;grandfater-_col red;// 继续往上处理cur grandfater;parent cur-_parent;}// 情况二三uncle不存在 存在且为黑else{// 情况二右单旋变色// g // p u// cif (cur parent-_left){RotateR(grandfater);parent-_col black;grandfater-_col red;}else{// 情况三左右单旋变色// g // p u// cRotateL(parent);RotateR(grandfater);cur-_col black;grandfater-_col red;}break;}}else{Node* uncle grandfater-_left;// 情况一if (uncle uncle-_col red){parent-_col uncle-_col black;grandfater-_col red;// 继续往上处理cur grandfater;parent cur-_parent;}else{// 情况二左单旋变色// g // u p// cif (cur parent-_right){RotateL(grandfater);parent-_col black;grandfater-_col red;}else{// 情况三右左单旋变色// g // u p// cRotateR(parent);RotateL(grandfater);cur-_col black;grandfater-_col red;}break;}}}_root-_col black;return true;}void Inorder(){_Inorder(_root);}private://右旋void RotateR(Node* parent){Node* subl parent-_left;Node* sublr subl-_right;Node* prev parent-_parent;parent-_left sublr;if (sublr)sublr-_parent parent;parent-_parent subl;subl-_right parent;if (_root parent){_root subl;subl-_parent nullptr;}else{if (prev-_left parent){subl-_parent prev;prev-_left subl;}else{subl-_parent prev;prev-_right subl;}}}//左旋void RotateL(Node* parent){Node* subr parent-_right;Node* subrl subr-_left;Node* prev parent-_parent;parent-_right subrl;if (subrl)subrl-_parent parent;subr-_left parent;parent-_parent subr;if (_root parent){_root subr;subr-_parent nullptr;}else{if (prev-_left parent){subr-_parent prev;prev-_left subr;}else{subr-_parent prev;prev-_right subr;}}}void _Inorder(Node* _root){if (_root nullptr)return;_Inorder(_root-_left);cout _root-_date.first _root-_date.second endl;_Inorder(_root-_right);}private:Node* _root nullptr;};}
