锐客网

  1. 首页 > 睿知 > it技术 > >

红黑树的go语言 红黑树csdn

IT技术删除

Go语言map是怎么比较key是否存在的首先,不推荐使用[]来判断key是否存在,因为使用操作符[]会向map容器里插入一个元素.map红黑树的go语言的operator[]重载大致是这样一个内容红黑树的go语言：
data_type operator[]( const key_type k ){value_type v(k,data_type());
iterator it = insert(v).first;
} 大致是这样,如果没有找到的话就插入一个,然后返回它的second.正确的判断方法是使用map的find函数,由于map是一个红黑树,find的时间复杂度是logn,可以接受.bool i***ist(constString keyName) { return( mRegistryMap.find(keyName)!= mRegistryMap.end()); }
红黑树——一个自平衡的二叉搜索树 普通红黑树的go语言的二叉搜索树在最坏的情况下红黑树的go语言，可能退化成一个链表 。而又因为二叉搜索树的所有操作的性能（添加 ， 删除，查找等），与二叉搜索树的高度有关 。在最坏的情况下 ， 二叉搜索树的高度和元素个数相同，此时二叉搜索树的效率降为了O(n)级别 。
所以为了防止我们的二叉搜索树退化成一个链表，就产生了 平衡二叉树。平衡二叉树 可以保证它的左右两个子树的高度差不会超过1 。平衡二叉树有很多实现 ， 一个经典实现就是 红黑树。
在红黑树中将树中的节点划分为两种状态，分别用黑色和红色来表示 。
红黑树为了保证自己能够平衡子树，所以制订以下五个规则：
【红黑树的go语言 红黑树csdn】1、每个节点必须有颜色，要么黑色，要么红色，没有别的颜色 。
2、根节点必须是黑色
3、所有的空节点(nil节点)都认为是黑色节点 。
4、红色的节点不能连续，即一个红色的节点，它的父节点和子节点不能也是红色的，
5、无论从哪一个节点起始 ， 到它每个叶子节点的路径中，黑色节点数量必须相同 。
在对红黑树进行添加、删除等操作之后，必须使红黑树符合这5个规则 。
那么问题来了，在添加删除操作之后，树中节点的数量都变了，是怎么保证整个树满足上述这些规则呢？
这里涉及到3种操作 ，  变色 、 左旋 和 右旋。通过这个三种操作，在增删节点之后调整树的形状结构 ， 使它满足上述5个规则 。这也是红黑树能保持平衡的原因 。
变色操作 我们在下文的添加、删除节点的实际操作中，再进行在描述 。
先来说一下左右旋 。
文字描述一下就是，2的右孩子节点4，变为了2的父节点 ， 2由父节点变为4的左孩子 。同时 ， 4原来的左孩子变为2的右孩子 。
右旋与左旋相反，即以某节点为支点进行顺时针旋转 。同样 ， 我们看下图，是以5为支点进行的右旋:
文字描述同样反过来 ， 5的左孩子节点3，变为5的父节点，5由父节点变为3的右孩子 。3原来的右孩子变为5的左孩子 。
首先是在树中找到新节点正确的位置，寻找位置的过程与普通的二叉搜索树相同，只是将新插入的节点默认为 红色节点。为什么默认为红色？因为如果你将新节点默认为黑色 ， 则插入后肯定会打破原本符合规则的红黑树（上述第5条规则） 。但是，如果你将新节点定为红色，则有可能不用任何操作就符合红黑树规则 ， 如下图 ， 当新插入的红色节点 ， 它的父亲节点为黑色时候，此时已经满足红黑树规则了 。所以用红色比黑色好 。
如果很不巧 ， 新插入的节点的父亲节点也为红色，因为红色节点不能连续，所以我们需要调整红黑树的结构使其满足规则 。在调整的过程中我们会遇到3种需要处理的情况 ， 我们来一一进行说明 。

推荐阅读


上一篇：jquery拖拽布局与保存，jq拖拽功能

下一篇：电脑自动返回什么意思呀，电脑老是自动返回桌面什么原因