红黑树插入算法

A. C++中set的插入和查找 与二分查找对比 效率如何

Set的底层是用的红黑树。而数组就是顺序表。这两种数据结构优劣不同。
如果已知数据有序，那么顺序表的二分查找当然最快。但是顺序表的插入性能极差，比如我要在头部插入一个数据，则要吧所有的数据后移一格，开销极大。红黑树则平衡了插入性能和查找性能。所以就有你看到的数据了，set的时间空间性能都比较差。
顺序复制数组，不涉及到插入，所以数组很快。但是插入，删除的话，红黑树需要一些时间来调整结构，所以有时间和空间的开销。
如果你有这样的一批数据，数量比较大，假设25w左右，他们需要频繁的发生插入，删除，以及查找工作，那么数组就无法处理了，红黑树则是更好的选择。
你可以研究一下红黑树的性质，就很容易理解了。

如果有不清楚的地方请追问。

B. 请问java中HashMap是怎么实现的，还有treeMap的实现原理是红黑树，请解释一下红黑树

参考资料的网页上有比较的代码,你可以仔细看下~~~

java中HashMap,LinkedHashMap,TreeMap，HashTable的区别
java为数据结构中的映射定义了一个接口java.util.Map;它有四个实现类,分别是HashMap Hashtable LinkedHashMap 和TreeMap
Map主要用于存储健值对，根据键得到值，因此不允许键重复(重复了覆盖了),但允许值重复。
Hashmap 是一个最常用的Map,它根据键的HashCode 值存储数据,根据键可以直接获取它的值，具有很快的访问速度，遍历时，取得数据的顺序是完全随机的。HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null;HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。
Hashtable与 HashMap类似,它继承自Dictionary类，不同的是:它不允许记录的键或者值为空;它支持线程的同步，即任一时刻只有一个线程能写Hashtable,因此也导致了 Hashtable在写入时会比较慢。
LinkedHashMap保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的.也可以在构造时用带参数，按照应用次数排序。在遍历的时候会比HashMap慢，不过有种情况例外，当HashMap容量很大，实际数据较少时，遍历起来可能会比LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。
TreeMap实现SortMap接口，能够把它保存的记录根据键排序,默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator 遍历TreeMap时，得到的记录是排过序的。

一般情况下，我们用的最多的是HashMap,HashMap里面存入的键值对在取出的时候是随机的,它根据键的HashCode值存储数据,根据键可以直接获取它的值，具有很快的访问速度。在Map 中插入、删除和定位元素，HashMap 是最好的选择。
TreeMap取出来的是排序后的键值对。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。
LinkedHashMap 是HashMap的一个子类，如果需要输出的顺序和输入的相同,那么用LinkedHashMap可以实现,它还可以按读取顺序来排列，像连接池中可以应用。

C. 关于算法导论

概念：

红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，他称之为"对称二叉B树"，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

红黑树是一种很有意思的平衡检索树。它的统计性能要好于平衡二叉树(有些书籍根据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树)，因此，红黑树在很多地方都有应用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。

背景和术语：
红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。所有数据块都存储在节点中。这些节点中的某一个节点总是担当启始位置的功能，它不是任何节点的儿子；我们称之为根节点或根。它有最多两个"儿子"，都是它连接到的其他节点。所有这些儿子都可以有自己的儿子，以此类推。这样根节点就有了把它连接到在树中任何其他节点的路径。

如果一个节点没有儿子，我们称之为叶子节点，因为在直觉上它是在树的边缘上。子树是从特定节点可以延伸到的树的某一部分，其自身被当作一个树。在红黑树中，叶子被假定为 null 或空。

由于红黑树也是二叉查找树，它们当中每一个节点都的比较值都必须大于或等于在它的左子树中的所有节点，并且小于或等于在它的右子树中的所有节点。这确保红黑树运作时能够快速的在树中查找给定的值。
用途和好处：
红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如即时应用(real time application)中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树。

红黑树在函数式编程中也特别有用，在这里它们是最常用的持久数据结构之一，它们用来构造关联数组和集合，在突变之后它们能保持为以前的版本。除了O(log n)的时间之外，红黑树的持久版本对每次插入或删除需要O(log n)的空间。

红黑树是 2-3-4树的一种等同。换句话说，对于每个 2-3-4 树，都存在至少一个数据元素是同样次序的红黑树。在 2-3-4 树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得 2-3-4 树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍 2-3-4 树的原因，尽管 2-3-4 树在实践中不经常使用。
属性：
红黑树是每个节点都有颜色特性的二叉查找树，颜色的值是红色或黑色之一。除了二叉查找树带有的一般要求，我们对任何有效的红黑树加以如下增补要求:

1.节点是红色或黑色。

2.根是黑色。

3.每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

4.从每个叶子到根的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键属性: 从根到叶子的最长的可能路径不大于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值都要求与树的高度成比例的最坏情况时间，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

在很多树数据结构的表示中，一个节点有可能只有一个儿子，而叶子节点包含数据。用这种范例表示红黑树是可能的，但是这会改变一些属性并使算法复杂。为此，本文中我们使用 "null 叶子" 或"空(null)叶子"，如上图所示，它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略，导致了这些树好像同上述原则相矛盾，而实际上不是这样。与此有关的结论是所有节点都有两个儿子，尽管其中的一个或两个可能是空叶子。

操作：
在红黑树上只读操作不需要对用于二叉查找树的操作做出修改，因为它也二叉查找树。但是，在插入和删除之后，红黑属性可能变得违规。恢复红黑属性需要少量(O(log n))的颜色变更(这在实践中是非常快速的)并且不超过三次树旋转(对于插入是两次)。这允许插入和删除保持为 O(log n) 次，但是它导致了非常复杂的操作。

D. 红黑树的用途

红黑树用在关联数组、字典的实现上。需要的空间比散列表小。 任何键值对应,需要随机存储和键有序的情况都可以用。

E. 为什么工程中都用红黑树，而不是其他平衡二叉树

红黑树和平衡二叉树区别如下：
1、红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。
2、平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。

平衡二叉树又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。构造与调整方法 平衡二叉树的常用算法有红黑树、AVL、Treap等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

F. 红黑树如何执行修改操作

红黑树解释起来比较麻烦，里面有一些树节点的旋转工作，我有编好的程序，也是搞了n多天才搞定的。你先看看（代码是C++的）。里面实现了其节点插入、删除、遍历、前驱、后继等接口。

程序太长，没法拷贝过来，到我的博客去看吧。

如果程序没法理解，请查看麻省理工的《算法导论》中文版关于二叉查找树和红黑树的章节，里面有详细介绍和很多伪代码，我的代码就是参考伪代码写出来的。

=============最新回复==============

不知道你所说的修改是什么意思，是修改卫星数据还是修改key值？
如果是修改卫星数据，那么不需要改动树结构；
如果是修改key值，那么愚以为，删除和插入两个操作相加是最好的办法，因为即使两者操作叠加，时间复杂度也不会超过log(n)

麻省理工的《算法导论》中文版卓越网上有热卖哦：-）

G. 只有左树节点是红树的红黑树与算法里介绍的红黑树有何区别

只有左树节点是红树的红黑树与算法里介绍的红黑树有何区别
因为插入之前所有根至外部节点的路径上黑色节点数目都相同，所以如果插入的节点是黑色肯定错误（黑色节点数目不相同），而相对的插入红节点可能会也可能不会违反“没有连续两个节点是红色”这一条件，所以插入的节点为红色，如果违反条件再调整
红黑树的操作时间跟二叉查找树的时间复杂度是一样的，执行查找、插入、删除等操作的时间复杂度为O（logn）。
红黑树是特殊的AVL树，遵循红定理和黑定理 红定理：不能有两个相连的红节点 黑定理：根节点必须是黑节点，而且所有节点通向NULL的路径上，所经过的黑节点的个数必须相等

H. 为什么像map，set都用红黑树来实现

STL中List,Vector,Map,Set的理解2009年07月11日 星期六 21:27List封装了链表,Vector封装了数组, list和vector得最主要的区别在于vector使用连续内存存储的，他支持[]运算符，而list是以链表形式实现的，不支持[]。Vector对于随机访问的速度很快，但是对于插入尤其是在头部插入元素速度很慢，在尾部插入速度很快。List对于随机访问速度慢得多，因为可能要遍历整个链表才能做到，但是对于插入就快的多了，不需要拷贝和移动数据，只需要改变指针的指向就可以了。另外对于新添加的元素，Vector有一套算法，而List可以任意加入。Map,Set属于标准关联容器，使用了非常高效的平衡检索二叉树：红黑树，他的插入删除效率比其他序列容器高是因为不需要做内存拷贝和内存移动，而直接替换指向节点的指针即可。Set和Vector的区别在于Set不包含重复的数据。Set和Map的区别在于Set只含有Key，而Map有一个Key和Key所对应的Value两个元素。Map和Hash_Map的区别是Hash_Map使用了Hash算法来加快查找过程，但是需要更多的内存来存放这些Hash桶元素，因此可以算得上是采用空间来换取时间策略。

I. 平衡树的主要算法

红黑树的平衡是在插入和删除的过程中取得的。对一个要插入的数据项，插入程序要检查不会破坏树一定的特征。如果破坏了，程序就会进行纠正，根据需要更改树的结构。通过维持树的特征，保持了树的平衡。
红黑树有两个特征：
(1) 节点都有颜色
(2) 在插入和删除过程中，要遵循保持这些颜色的不同排列的规则。
红黑规则：
1. 每一个节点不是红色的就是黑色的
2. 根总是黑色的
3. 如果节点是红色的，则它的子节点必须是黑色的（反之不一定成立）
4. 从根到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点。
（空子节点是指非叶节点可以接子节点的位置。换句话说，就是一个有右子节点的节点可能接左子节点的位置，或是有左子节点的节点可能接右子节点的位置） AVL树，它或者是一颗空二叉树，或者是具有下列性质的二叉树：
(1) 其根的左右子树高度之差的绝对值不能超过1；
(2) 其根的左右子树都是二叉平衡树。
AVL树查找的时间复杂度为O(logN)，因为树一定是平衡的。但是由于插入或删除一个节点时需要扫描两趟树，依次向下查找插入点，依次向上平衡树，AVL树不如红黑树效率高，也不如红黑树常用。
AVL树插入的C++代码： template<classT>ResultCodeAVLTree<T>::Insert(AVLNode<T>*&p,T&x,bool&unBalanced)...{ResultCoderesult=Success;if(p==null)...{//插入新节点p=newAVLNode<T>(x);unBalanced=true;}elseif(x<p->element)...{//新节点插入左子树result=Insert(p->lChild,x,unBalanced);if(unBanlanced)...{switch(p->bF)...{case-1:p->bF=0;unBalanced=false;break;case0:p->bF=1;break;case1:LRotation(p,unBalanced);}}}elseif(x==p->element)...{//有重复元素，插入失败unBalanced=false;x=p->element;result=Duplicate;}else...{//新节点插入右子树result=Insert(p->rChild,x,unBalanced);if(unBalanced)...{switch(p->bF)...{case1:p->bF=0;unBalanced=false;break;case0:p->bF=-1;break;case-1:RRotation(p,unBalanced);}}}returnresult;}template<classT>voidAVLTree<T>::LRotation(AVLNode<T>*&s,bool&unBalanced)...{AVLNode<T>*u,*r=s->lChild;if(r->bF==1)...{//LL旋转s->lChild=r->rChild;r->rChild=s;s->bF=0;s=r;//s指示新子树的根}else...{//LR旋转u=r->rChild;r->rChild=u->lChild;u->lChild=r;s->lChild=u->rChild;u->rChild=s;switch(u->bF)...{case1:s->bF=-1;r->bF=0;break;case0:s->bF=r->bF=0;break;case-1:s->bF=0;r->bF=1;}s=u;//s指示新子树的根}s->bF=0;//s的平衡因子为0unBalanced=false;//结束重新平衡操作}通常我们使用二叉树的原因是它可以用O（logn）的复杂度来查找一个数，删除一个数，对吧？？可是有时候会发现树会退化，这个就可能使O（logn）->O（n）的了，那么还不如用直接搜一次呢！！所以我们就要想办法使一棵树平衡。而我仅仅看了（AVL）的那个，所以也仅仅能说（AVL）的那个，至于（TREAP），我还不懂，如果你们知道算法的话，欢迎告诉我~！谢谢~
首先引入一个变量，叫做平衡因子（r），节点X的r就表示x的左子树的深度-右子树的深度。然后我们要保证一棵树平衡，就是要保证左右子树的深度差小于等于1.所以r的取值能且仅能取0，-1，1.
其次，我要介绍旋转，旋转有两种方式，就是左旋（顺时针旋转）和右旋（逆时针旋转）。
左旋（左儿子代替根）：即用左儿子取代根，假设我们要旋转以X为根，LR分别为X的左右儿子，那么我们只需要把L的右儿子取代X的左儿子，然后把更新后的X赋值为L的右儿子，就可以了。
右旋（右儿子代替根）：即用右儿子取代根，假设我们要旋转以X为根，LR分别为X的左右儿子，那么我们只需要把R的左儿子取代X的右儿子，然后把更新后的X赋值为R的左儿子，就可以了。 Size Balanced Tree(SBT平衡树）是2007年Winter Camp上由我国着名OI选手陈启峰发布的他自己创造的数据结构。相比于一般的平衡树，此平衡树具有的特点是：快速（远超Treap，超过AVL)、代码简洁、空间小（是线段树的1/4左右）、便于调试和修改等优势。
与一般平衡搜索树相比，该数据结构只靠维护一个Size来保持树的平衡，通过核心操作Maintain(修复）使得树的修改平摊时间为O(1)。因而大大简化代码实现复杂度、提高运算速度。
参见网络SBT。 平衡树的一种，每次将待操作节点提到根，每次操作时间复杂度为O(logn)。见伸展树。 constintSPLAYmaxn=200005;constintSPLAYinf=100000000;structSplay_Node{intl,r,fa,v,sum;};structSplay{Splay_Nodet[SPLAYmaxn];introot,tot;voidcreate(){root=1,tot=2;t[1].v=-SPLAYinf;t[2].v=SPLAYinf;t[1].r=t[1].sum=2;t[2].fa=t[2].sum=1;}voipdate(intnow){t[now].sum=t[t[now].l].sum+t[t[now].r].sum+1;}voidleft(intnow){intfa=t[now].fa;t[now].fa=t[fa].fa;if(t[t[fa].fa].l==fa)t[t[fa].fa].l=now;if(t[t[fa].fa].r==fa)t[t[fa].fa].r=now;t[fa].fa=now;t[fa].r=t[now].l;t[t[now].l].fa=fa;t[now].l=fa;up(fa);}voidright(intnow){intfa=t[now].fa;t[now].fa=t[fa].fa;if(t[t[fa].fa].l==fa)t[t[fa].fa].l=now;if(t[t[fa].fa].r==fa)t[t[fa].fa].r=now;t[fa].fa=now;t[fa].l=t[now].r;t[t[now].r].fa=fa;t[now].r=fa;update(fa);}voidsplay(intnow,intFA=0){while(t[now].fa!=FA){intfa=t[now].fa;if(t[fa].fa==FA)if(t[fa].l==now)right(now);elseleft(now);elseif(t[t[fa].fa].l==fa)if(t[fa].l==now)right(fa),right(now);elseleft(now),right(now);elseif(t[fa].l==now)right(now),left(now);elseleft(fa),left(now);}update(now);if(!FA)root=now;}intlower_bound(intv){intans=0,la=0;for(intnow=root;now;){la=now;if(t[now].v>=v)ans=now,now=t[now].l;elsenow=t[now].r;}splay(la);returnans;}voidinsert(intv){for(intnow=root;;){++t[now].sum;if(t[now].v>=v)if(t[now].l)now=t[now].l;else{t[now].l=++tot;t[tot].sum=1;t[tot].fa=now;t[tot].v=v;splay(tot);return;}elseif(t[now].r)now=t[now].r;else{t[now].r=++tot;t[tot].sum=1;t[tot].fa=now;t[tot].v=v;splay(tot);return;}}}intget_lower(inta){splay(a);for(a=t[a].l;t[a].r;a=t[a].r);returna;}intget_upper(inta){splay(a);for(a=t[a].r;t[a].l;a=t[a].l);returna;}intget_rank(inta){splay(a);returnt[t[a].l].sum;}voiddel(intl,intr){l=get_lower(l);r=get_upper(r);splay(l);splay(r,l);t[r].l=0;update(r);update(l);}intget_kth(intk){++k;for(intnow=root;;){if(t[t[now].l].sum==k-1)returnnow;if(t[t[now].l].sum>=k)now=t[now].l;elsek-=t[t[now].l].sum+1,now=t[now].r;}}};

J. 红黑树和平衡二叉树 区别

红黑树和平衡二叉树的主要区别如下：
平衡二叉树（AVL）树是严格的平衡二叉树，平衡条件必须满足（所有节点的左右子树高度差不超过1）。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而的英文旋转非常耗时的。所以平衡二叉树（AVL）适合用于插入与删除次数比较少，但查找多的情况。
红黑树在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log
n)。所以红黑树适用于搜索，插入，删除操作较多的情况。
(10)红黑树插入算法扩展阅读：
平衡二叉树在Windows
NT内核中广泛存在。
红黑树的应用：
1、在C
++的STL中，地图和集都是用红黑树实现的；
2、着名的Linux的的进程调度完全公平调度程序，用红黑树管理进程控制块，进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间；
3、IO多路复用的epoll的的的实现采用红黑树组织管理的sockfd，以支持快速的增删改查；
4、Nginx的的的中用红黑树管理定时器，因为红黑树是有序的，可以很快的得到距离当前最小的定时器；
5、Java中的TreeMap中的实现。
参考资料：
网络-平衡二叉树
网络-红黑树