龙港哪里有做阿里巴巴网站,wordpress作品展示模板,怎样让百度收录网站,烟台网站制作计划目录 什么是红黑树#xff1f;红黑树红黑树的性质 定义红黑树红黑树的操作insertinorderfindheightsize构造函数析构函数赋值拷贝判断红黑树 全部代码总结 什么是红黑树#xff1f;
红黑树
红黑树#xff08;Red-Black Tree#xff09;是一种自平衡的二叉搜索树#xff… 目录 什么是红黑树红黑树红黑树的性质 定义红黑树红黑树的操作insertinorderfindheightsize构造函数析构函数赋值拷贝判断红黑树 全部代码总结 什么是红黑树
红黑树
红黑树Red-Black Tree是一种自平衡的二叉搜索树用于保持树的平衡以确保在最坏情况下基本操作如插入、删除和查找的时间复杂度仍为 O(log n)。红黑树的每个节点都包含一个额外的颜色位即红色或黑色。红黑树通过严格的平衡条件来维持树的平衡。
红黑树的性质
节点是红色或黑色的每个节点都有颜色属性红色或黑色。根是黑色的红黑树的根节点必须是黑色的。叶节点NIL 节点是黑色的红黑树中的所有叶节点这里的叶节点是指为空的 NIL 节点而不是实际的元素节点都是黑色的。红色节点的子节点必须是黑色的即红色节点不能有红色子节点也叫“红黑相间”红色节点不能连续连接在一起。从任何节点到其每个叶子的所有简单路径都必须包含相同数量的黑色节点这确保了树的平衡性。
定义红黑树
enum Color
{RED,BLACK,
};
templateclass K, class V
struct RBTreeNode
{pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Color _col;RBTreeNode(const pairK, V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}
};
templateclass K,class V
class RBTree
{
public:typedef RBTreeNodeK, V Node;
private:Node* _root nullptr;
};红黑树的操作
insert
红黑树的逻辑是在普通的二叉搜索树上进行实现的在普通的二叉搜索树中我们不需要调节平衡但是在红黑树当中我们需要根据红黑树的性质来调整数的颜色和高度首先我们来看看第一种情况 cur是插入节点由于红色节点不能连续所以这里已经破坏了平衡所以我们应该进行调整颜色我们不可能插入cur是黑色节点因为如果插入黑色节点的话代价很大每条路上都会多出来一个黑色节点这样很不好维护所以插入红色节点是代价最小的插入红色节点之后破坏了规则所以p应该变成黑色由于p这条路多了一个黑色节点所以u应该也变成黑色节点由于这棵树有可能是某个子树这两条路多出来一个黑色节点为了保证黑色节点不多所以g节点应该也变成红色这样做完之后继续往上调整将cur赋值到g节点继续往上调整颜色。 这样就算调整完毕了。 第二种情况当u节点不存在时 对于这种情况我们先准备调色首先我们先将p改为黑色节点然后将g改为红色节点之后我们会发现左边这条路多出来一个黑色节点这样是不行的。 上面这个是不行的左边已经多出来了一个黑色节点了但是右边没有黑色节点所以这种情况我们应该进行旋转。 对g节点进行右旋 进行右旋之后将p改为黑色节点将g改为红色节点这样两边都保持平衡了。 还有一种情况u存在但是为黑色
最下面的那个红色节点是插入节点 这种情况我们先向上调整 调整成这样之后我们就发现u是黑色节点不管我们怎么调整左边都会多出一个黑色节点所以这里我们应该旋转 绕着g节点进行旋转之后我们可以发现调整颜色就会平衡 还有双旋的情况双旋的情况我们只说一种 左旋将p和cur的位置交换然后再对g进行右旋就可以达到平衡的效果。
左旋接口
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* parentParent parent-_parent;subR-_left parent;parent-_parent subR;if (parentParent nullptr){_root subR;subR-_parent nullptr;}else{if (parent parentParent-_left)parentParent-_left subR;else parentParent-_right subR;subR-_parent parentParent;}
}右旋接口
void RotateR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* parentParent parent-_parent;subL-_right parent;parent-_parent subL;if (parentParent nullptr){_root subL;subL-_parent nullptr;}else{if (parentParent-_left parent)parentParent-_left subL;else parentParent-_right subL;subL-_parent parentParent;}
}insert的代码
bool Insert(const pairK, V kv)
{if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}Node* cur _root;Node* parent nullptr;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);cur-_col RED;//插入到右边if (parent-_kv.first kv.first)parent-_right cur;else parent-_left cur;cur-_parent parent;//调整颜色或旋转//parent不为空并且parent指向的颜色是红色才进行调整while (parent parent-_col RED){Node* grandparent parent-_parent;if (grandparent-_left parent){Node* uncle grandparent-_right;//uncle存在且是红色if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;parent cur-_parent;}//uncle不存在或者存在为黑色else{//判断cur是parent的左子树还是右子树//右单旋if (cur parent-_left){RotateR(grandparent);grandparent-_col RED;parent-_col BLACK;}else{RotateL(parent);RotateR(grandparent);cur-_col BLACK;grandparent-_col RED;}break;}}else{Node* uncle grandparent-_left;//uncle存在且是红色if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;parent cur-_parent;}//uncle不存在或者存在为黑色else{//判断cur是parent的左子树还是右子树//右单旋if (cur parent-_right){RotateL(grandparent);grandparent-_col RED;parent-_col BLACK;}else{RotateR(parent);RotateL(grandparent);cur-_col BLACK;grandparent-_col RED;}break;}}}_root-_col BLACK;return true;
}inorder
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);
}find
bool Find(const K k)
{Node* cur _root;while (cur){if (cur-_kv.first k) cur cur-_right;else if (cur-_kv.first k) cur cur-_left;else return true;}return false;
}height
int height()
{return _height(_root);
}
int _height(Node* root)
{if (root nullptr)return 0;int leftheight _height(root-_left);int rightheight _height(root-_right);return max(leftheight, rightheight) 1;
}size
int size()
{return _size(_root);
}
int _size(Node* root)
{if (root nullptr)return 0;int left _size(root-_left);int right _size(root-_right);return left right 1;
}构造函数
//默认构造
RBTree() default;
//拷贝构造
RBTree(const RBTreeK, V t)
{_root Copy(t._root);
}
Node* Copy(Node* root)
{if (root nullptr)return nullptr;Node* newnode new Node(root-_kv);newnode-_left Copy(root-_left);newnode-_right Copy(root-_right);return newnode;
}析构函数
~RBTree()
{Destroy(_root);_root nullptr;
}
void Destroy(Node* root)
{if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;
}赋值拷贝
RBTreeK, V operator(RBTreeK, V t)
{swap(_root, t._root);return *this;
}判断红黑树
bool IsBalance()
{//空树也是搜索树if (_root nullptr) return true;//根节点不能为红色if (_root-_col RED) return false;//参考值int refNum 0;Node* cur _root;while (cur){//遇到黑色if (cur-_col BLACK) refNum;cur cur-_left;}return Check(_root, 0, refNum);
}
bool Check(Node* root, int blackNum, const int refNum)
{//走到空之后就算出一条路径的数量了if (root nullptr){if (blackNum ! refNum){cout 存在黑色节点不相等的路径 endl;return false;}return true;}//存在连续的红色节点if (root-_col RED root-_parent-_col RED)return false;if (root-_col BLACK)blackNum;return Check(root-_left, blackNum, refNum) Check(root-_right, blackNum, refNum);
}全部代码
#pragma once
#includeiostream
#includeassert.h
using namespace std;
enum Color
{RED,BLACK,
};
templateclass K, class V
struct RBTreeNode
{pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Color _col;RBTreeNode(const pairK, V kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}
};
templateclass K,class V
class RBTree
{
public:typedef RBTreeNodeK, V Node;//默认构造RBTree() default;//拷贝构造RBTree(const RBTreeK, V t){_root Copy(t._root);}//赋值拷贝RBTreeK, V operator(RBTreeK, V t){swap(_root, t._root);return *this;}//析构函数~RBTree(){Destroy(_root);_root nullptr;}//查找bool Find(const K k){Node* cur _root;while (cur){if (cur-_kv.first k) cur cur-_right;else if (cur-_kv.first k) cur cur-_left;else return true;}return false;}//中序遍历void InOrder(){_InOrder(_root);}//插入bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}Node* cur _root;Node* parent nullptr;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);cur-_col RED;//插入到右边if (parent-_kv.first kv.first)parent-_right cur;else parent-_left cur;cur-_parent parent;//调整颜色或旋转//parent不为空并且parent指向的颜色是红色才进行调整while (parent parent-_col RED){Node* grandparent parent-_parent;if (grandparent-_left parent){Node* uncle grandparent-_right;//uncle存在且是红色if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;parent cur-_parent;}//uncle不存在或者存在为黑色else{//判断cur是parent的左子树还是右子树//右单旋if (cur parent-_left){RotateR(grandparent);grandparent-_col RED;parent-_col BLACK;}else{RotateL(parent);RotateR(grandparent);cur-_col BLACK;grandparent-_col RED;}break;}}else{Node* uncle grandparent-_left;//uncle存在且是红色if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandparent-_col RED;cur grandparent;parent cur-_parent;}//uncle不存在或者存在为黑色else{//判断cur是parent的左子树还是右子树//右单旋if (cur parent-_right){RotateL(grandparent);grandparent-_col RED;parent-_col BLACK;}else{RotateR(parent);RotateL(grandparent);cur-_col BLACK;grandparent-_col RED;}break;}}}_root-_col BLACK;return true;}//大小int size(){return _size(_root);}//树的高度int height(){return _height(_root);}
private:int _height(Node* root){if (root nullptr)return 0;int leftheight _height(root-_left);int rightheight _height(root-_right);return max(leftheight, rightheight) 1;}int _size(Node* root){if (root nullptr)return 0;int left _size(root-_left);int right _size(root-_right);return left right 1;}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* parentParent parent-_parent;subR-_left parent;parent-_parent subR;if (parentParent nullptr){_root subR;subR-_parent nullptr;}else{if (parent parentParent-_left)parentParent-_left subR;else parentParent-_right subR;subR-_parent parentParent;}}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* parentParent parent-_parent;subL-_right parent;parent-_parent subL;if (parentParent nullptr){_root subL;subL-_parent nullptr;}else{if (parentParent-_left parent)parentParent-_left subL;else parentParent-_right subL;subL-_parent parentParent;}}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}void Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;}Node* Copy(Node* root){if (root nullptr)return nullptr;Node* newnode new Node(root-_kv);newnode-_left Copy(root-_left);newnode-_right Copy(root-_right);return newnode;}Node* _root nullptr;
};总结
红黑树作为一种自平衡二叉搜索树通过严格的颜色和旋转规则保证了在最坏情况下仍能提供高效的查找、插入和删除操作。其特有的平衡机制使得红黑树在实际应用中被广泛采用尤其在需要频繁增删节点的数据结构中表现出色。掌握红黑树的原理和操作不仅有助于理解复杂数据结构的实现也为开发高效算法奠定了坚实基础。希望通过本篇博客大家能够对红黑树有更加深入的认识并在实际编程中灵活应用。
