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

红黑树怎么实现对历史版本的访问

红黑树的出现可以解决对历史版本的访问问题。

主要是将插入和删除控制在常数范围内。

多版本，大量数据共享。

少量更新。

绝大多数的树，在动态操作过程当中如果不超过常数比较难。

主要是旋转。

插入式满足的，一次旋转性能就可以复原，但是很可惜，删除可能需要多大logn的旋转。

任何动态操作都能控制在常数的范围，就是红黑树。

第三个对控制深度比较重要，第四个对于平衡性比较重要。

使用（2,3）b树对红黑树进行分析。

提升变换对于红黑树的意义。

底层节点比那成同一水平节点平齐高度。

java 8 为什么要采用红黑树来管理hashmap

java8不是用红黑而是在hash值相同的情况下（且重复数量大于8），用红黑树来管理数据。

红黑树相当于排序数据。

可以自动的使用二分法进行定位。

性能较高。

一般情况下，hash值做的比较好的话基本上用不到红黑树。

求红黑树应用实例，谢谢！

红黑树用在关联数组、字典的实现上。

需要的空间比散列表小。

任何键值对应，需要随机存储和键有序的情况都可以用。

实例中 内存中比如缓存的(区块-数据)，编号对应内容，引索号对应数据项 日期对应日程。

价格对应商品。

应用遍及，在内存中使用效率比较高

为什么选择红黑树作为底层实现

红黑树属于平衡二叉树。

说它不严格是因为它不是严格控制左、右子树高度或节点数之差小于等于1。

但红黑树高度依然是平均log(n)，且最坏情况高度不会超过2log(n)，这有数学证明。

所以它算平衡树，只是不严格。

不过严格与否并不影响数据结构的复杂度。

红黑树多用于系统底层，oi竞赛中基本不用。

红黑树的红色叶子节点一定没有兄弟节点吗?为什么？

: 红黑树内部节点包含根节点叶节点. 好乱。

红黑树只有三个性质。

1:根节点和所有外部节点是黑色。

2:根至外部节点中没有两个连续的颜色是黑色

为什么像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桶元素，因此可以算得上是采用空间来换取时间策略。