锐客网

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

红黑树的go语言 红黑树csdn( 三 )

IT技术删除


第一步按情况4操作 ， 将55变红 。并将父节点50看做当前节点，继续操作 。
此时有关红黑树的知识就说完了 。
以上所有内容都为自己查阅资料学习理解之后手敲的 。尽量得采用通俗易懂的描述和解释让读者更明白 。27张图都是自己亲自画的 ， 花费了四天才写完，如果觉得写的还可以，麻烦点亮喜欢支持一下，如果还是不懂 ， 可以下方留言QQ等联系方式，我亲自告诉你 。
红黑树怎么实现对历史版本的访问红黑树的出现可以解决对历史版本的访问问题 。主要是将插入和删除控制在常数范围内 。
多版本，大量数据共享 。少量更新 。
绝大多数的树，在动态操作过程当中如果不超过常数比较难 。主要是旋转 。插入式满足的，一次旋转性能就可以复原，但是很可惜，删除可能需要多大logn的旋转 。任何动态操作都能控制在常数的范围，就是红黑树 。
第三个对控制深度比较重要，第四个对于平衡性比较重要 。
使用（2,3）b树对红黑树进行分析 。
提升变换对于红黑树的意义 。底层节点比那成同一水平节点平齐高度 。
红黑树的用途红黑树用在关联数组、字典红黑树的go语言的实现上 。需要的空间比散列表小 。任何键值对应,需要随机存储和键有序的情况都可以用 。
一. 基本概念
1.红黑树(Red Black Tree) 是一种自平衡二叉查找树红黑树的go语言，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组 。
2.它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树(symmetric binary B-trees) 。后来 ， 在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的"红黑树" 。
3.红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能 。
4.它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目 。
二. 数据结构
它的统计性能要好于平衡二叉树(有些书籍根红黑树据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树)，因此，红黑树在很多地方都有应用 。在C++ STL中，很多部分(包括set, multiset, map, multimap)应用红黑树的go语言了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持) 。其红黑树的go语言他平衡树还有:AVL，SBT，伸展树，TREAP 等等 。
三. 性质
性质1. 节点是红色或黑色 。
性质2. 根节点是黑色 。
性质3.每个叶节点(NIL节点 ， 空节点)是黑色的 。
性质4.每个红色节点的两个子节点都是黑色 。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点 。
在linux操作系统内核实现里经常使用的红黑树在linux操作系统内核实现里经常使用的红黑树如下：
二叉树，按中序遍历后为一递增数组，自平衡意味着树的高度有一个上限，对于红黑树，其为2log(n+1)，所以时间复杂度为最差为Olog(n) 。
赋予二叉搜索树自平衡特性的方法有多种 ， 红黑树通过一下4条约束实现自平衡:
Every node is either red or black.
All NIL nodes (figure 1) are considered black.
A red node does not have a red child.
Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.
其中根节点为黑色 。
红黑树的搜索与二叉搜索树无异 ， 但是插入和删除可能会违背上述四条原则 。需要用到左旋右旋操作 。左旋右旋上图，可以看到左旋右旋本身不改变二叉搜索树的特性，旋转后必要时改变节点的颜色可消除插入或者删除带来的红冲突和黑冲突 ， 有时红黑树的重新平衡需要迭代进行 。

推荐阅读


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

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