做苗木网站哪个公司好,c 网站建设综合报告,企业培训课程种类,推广官网红黑树 1. 红黑树的概念2. 红黑树的性质3. 红黑树节点的定义4. 红黑树的插入操作5. 红黑树与AVL树的比较 1. 红黑树的概念
红黑树是一种自平衡二叉查找树#xff0c;是在计算机科学中用到的一种数据结构#xff0c;典型用途是实现关联数组。它在1972年由鲁道夫贝尔发明… 红黑树 1. 红黑树的概念2. 红黑树的性质3. 红黑树节点的定义4. 红黑树的插入操作5. 红黑树与AVL树的比较 1. 红黑树的概念
红黑树是一种自平衡二叉查找树是在计算机科学中用到的一种数据结构典型用途是实现关联数组。它在1972年由鲁道夫·贝尔发明被称为「对称二叉B树」它现代的名字源于Leo J. Guibas和罗伯特·塞奇威克于1978年写的一篇论文。红黑树的结构复杂但它的操作有着良好的最坏情况运行时间并且在实践中高效它可以在O(log n)时间内完成查找、插入和删除这里的n是树中元素的数目。红黑树是每个节点都带有颜色属性的二叉查找树颜色为红色或黑色。在二叉查找树强制一般要求以外对于任何有效的红黑树我们增加了如下的额外要求节点是红色或黑色。 根是黑色。 所有叶子都是黑色叶子是NIL节点。 每个红色节点必须有两个黑色的子节点。 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。 在红黑树中所有的叶子结点都是黑色的空节点NIL节点。NIL节点是红黑树额外引入的结点在计算红黑数高度时NIL结点也会被计算在内。NIL结点指的是叶结点空的左右子结点延伸出来的的结点也包括了叶子节点本身。
2. 红黑树的性质
每个结点不是红色就是黑色 根节点是黑色的 如果一个节点是红色的则它的两个孩子结点是黑色的 对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点 每个叶子结点都是黑色的( 此处的叶子结点指的是空结点(NIL节点) )。
这些约束确保了红黑树的关键特性从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。 因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例这个在高度上的理论上限允许红黑树在最坏情况下都是高效的而不同于普通的二叉查找树。
3. 红黑树节点的定义
// 节点的颜色
enum Color{RED, BLACK};
// 红黑树节点的定义
templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left; // 节点的左孩子RBTreeNodeK, V* _right; // 节点的右孩子RBTreeNodeK, V* _parent; // 节点的双亲(红黑树需要旋转为了实现简单给出该字段)pairK, V _kv; // 节点的值Colour _col; // 节点的颜色RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED) //默认为红节点{}
};插入红色节点树的性质可能不会改变而插入黑色节点每次都会违反性质4所以 将节点设置为红色在插入时对红黑树造成的影响是小的而黑色的影响是最大的
4. 红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件因此红黑树的插入可分为两步
按照二叉搜索的树规则插入新节点检测新节点插入后红黑树的性质是否造到破坏如过性质被破坏就要进行旋转或变色的操作此时需要对红黑树分情况来讨论 以下为父节点在祖父的左边 对于红黑树的插入来说如果插入的父节点为黑并且插入的节点默认为红节点所以如果父节点为黑色时插入是不需要进行调节的如图1-2 有2-3图可以看出cur、p两个红节点相连所以需要调整这种情况计为情况一cur为红p为红g为黑u存在且为红。约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点 unlce节点的作用 在红黑树中uncle节点是指当前节点的父节点的兄弟节点。它的作用是在插入新节点时如果当前节点的父节点和uncle节点都是红色那么需要将当前节点的父节点和uncle节点染成黑色将当前节点的祖父节点染成红色然后以祖父节点为当前节点进行下一轮操作。这样可以保证红黑树的性质4每个红色节点必须有两个黑色的子节点不被破坏。 对图3进行调整需要保证红色节点不能相连并且从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点。如果只将cur改为黑色那么违反规则4将cur和uncle改为黑色也会违反规则四因为如果这棵树是一个子树那么g结点的左右路径是会多一个黑色结点。那么如何调整 解决方式将p,u改为黑g改为红然后把g当成cur继续向上调整因为g的父节点可能为红色。 这样保证了每条路径上的黑色结点的个数都相同。 对于变色来说不论cur在parent的左边还是右边变色后各个节点的位置都没有改变所以不需要分类讨论。 代码如下
while (parent parent-_col RED)
{Node* grandfather parent-_parent;if (grandfather-_left parent){//情况1:uncle存在且为红Node* uncle grandfather-_right;if (uncle uncle-_col RED){grandfather-_col RED;parent-_col uncle-_col BLACK;//继续向上调整cur grandfather;parent cur-_parent;}}
}cur为parent的左边如下图又该怎样调整
说明: u的情况有两种 1.如果u节点不存在则cur一定是新插入节点因为如果cur不是新插入节点,则cur和p一定有一个节点的颜色是黑色就不满足性质4:每条路径黑色节点个数相同这时就需要旋转变色处理。 2.如果u节点存在则其一定是黑色的那么cur节点原来的颜色一定是黑色的现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。如上图下半部分所示 计上述情况为情况二: cur为红p为红g为黑u不存在/u存在且为黑 对于上述两种情况我们发现怎么变色都是不行的所以可以旋转变色处理。旋转的详解如本篇博客AVL树 p为g的左孩子cur为p的左孩子则进行右单旋转相反p为g的右孩子cur为p的右孩子则进行左单旋转 p、g变色–p变黑g变红
cur为parent的右边如下图又该怎样调整 上述情况记为情况三: cur为红p为红g为黑u不存在/u存在且为黑 p为g的左孩子cur为p的右孩子则针对p做左单旋转相反p为g的右孩子cur为p的左孩子则针对p做右单旋转则转换成了情况2。 如下图进行旋转变色
代码如下
// 情况2和情况三3u不存在/u存在且为黑旋转变色// g// p u// c
//cur为父亲节点的左边
if (cur parent-_left)
{RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;
}
//cur为父亲节点的右边在右边需要双旋如AVL树中的旋转
else
{// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;
}对于父节点在祖父节点的右边这种情况和上述大致相同就不在多画了完整代码如下。 RBTree.h文件中的代码
#pragma onceenum Colour
{RED,BLACK,
};templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left; // 节点的左孩子RBTreeNodeK, V* _right; // 节点的右孩子RBTreeNodeK, V* _parent; // 节点的双亲(红黑树需要旋转为了实现简单给出该字段)pairK, V _kv; // 节点的值Colour _col; // 节点的颜色RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:Node* Find(const K key){Node* cur _root;while (cur){if (cur-_kv.first key){cur cur-_left;}else if (cur-_kv.first key){cur cur-_right;}else{return cur;}}return nullptr;}bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}//寻找插入的位置Node* parent nullptr;Node* cur _root;while (cur){parent cur;if (cur-_kv kv){cur cur-_left;}else if (cur-_kv kv){cur cur-_right;}else{return false;}}//插入新节点cur new Node(kv);if (parent-_kv kv){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//进行调整这棵红黑树while (parent parent-_col RED){Node* grandfather parent-_parent;//父节点在祖父的左边if (grandfather-_left parent){//情况1:uncle存在且为红Node* uncle grandfather-_right;if (uncle uncle-_col RED){grandfather-_col RED;parent-_col uncle-_col BLACK;//继续向上调整cur grandfather;parent cur-_parent;}else //叔叔不存在或叔叔存在且为黑,旋转变黑{//cur为父亲节点的左边if (cur parent-_left){// g// p u// c RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else //cur为父亲节点的右边{// g// p u// c RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}//父节点在祖父的右边else // (grandfather-_right parent){// g// u p// cNode* uncle grandfather-_left;// 情况1u存在且为红变色处理并继续往上处理if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 继续往上调整cur grandfather;parent cur-_parent;}else // 情况23u不存在/u存在且为黑旋转变色{// g// u p// cif (cur parent-_right){RotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}//确保每次调整完后根节点为黑色_root-_col BLACK;return true;}//因为红黑树的结点是new出来的所以需要释放也就是需要写析构函数~RBTree(){_Destroy(_root);_root nullptr;}int Height(){return _Height(_root);}void InOrder(){_InOrder(_root);}
private:int _Height(Node* root){if (root NULL)return 0;int leftH _Height(root-_left);int rightH _Height(root-_right);return leftH rightH ? leftH 1 : rightH 1;}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;Node* ppnode parent-_parent;subR-_left parent;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;}}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 (parent _root){_root subL;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}}void _Destroy(Node* root){if (root nullptr)return;_Destroy(root-_left);_Destroy(root-_right);delete(root);}
private:Node* _root nullptr;
};测试代码
#include iostream
using namespace std;#include RBTree.hvoid Test_RBTree1()
{int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 16, 3, 7, 11, 9, 26, 18, 14, 15 };RBTreeint, int t1;for (auto e : a){t1.Insert(make_pair(e, e));}t1.InOrder();
}
int main()
{Test_RBTree1();return 0;
}运行结果如下
5. 红黑树与AVL树的比较
1.红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O(log N)但它们的实现方式不同。 2.红黑树的查询性能略微逊色于AVL树因为其比AVL树会稍微不平衡最多一层也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较。 3.红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍红黑树在插入和删除上优于AVL树AVL树每次插入删除会进行大量的平衡度计算而红黑树为了维持红黑性质所做的红黑变换和旋转的开销相较于AVL树为了维持平衡的开销要小得多。 所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。
