红黑树算法java

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

java8不是用红黑树来管理hashmap，而是在hash值相同的情况下（且重复数量大于8），用红黑树来管理数据。 红黑树相当于排序数据。可以自动的使用二分法进行定位。性能较高。
一般情况下，hash值做的比较好的话基本上用不到红黑树。

B. 在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.

Everypathfrom a given node to any of its descendant NIL nodes goes through the same number of black nodes.

其中根节点为黑色。

红黑树的搜索与二叉搜索树无异，但是插入和删除可能会违背上述四条原则。需要用到左旋右旋操作。左旋右旋上图，可以看到左旋右旋本身不改变二叉搜索树的特性，旋转后必要时改变节点的颜色可消除插入或者删除带来的红冲突和黑冲突，有时红黑树的重新平衡需要迭代进行。

红黑树比较适合的应用场景:

需要动态插入、删除、查找的场景，包括但不限于：

某些数据库的增删改查，比如select * from xxx where 这类条件检索。

linux内核中进程通过红黑树组织管理，便于快速插入、删除、查找进程的task_struct。

linux内存中内存的管理：分配和回收。用红黑树组织已经分配的内存块，当应用程序调用free释放内存的时候，可以根据内存地址在红黑树中快速找到目标内存块。

hashmap中(key,value)增、删、改查的实现；java 8就采用了RBTree替代链表。

Ext3文件系统，通过红黑树组织目录项。

C. 红黑树，b+树分别用于什么场景，为什么

红黑树属于“黑平衡”的二叉树，虽然牺牲了一定的平衡性，但是add、remove操作要由优于AVL树也就是说RB-Tree的“统计性能”更佳！Java中TreeSet，TreeMap的底层都是基于RedBlackTree红黑树的；

B+树主要用在文件系统以及数据库做索引。比如磁盘存储、文件系统、MySQL数据库

D. Java的集合类ArrayList和TreeSet,调用contains方法,谁比较快

对于 contains 方法，ArrayList 直接是遍历进行比较。从第一个元素开始比较，直到找到对应的元素，或者比较到了最后一个元素。时间复杂度为 O(n)。如果对应元素的索引靠前，那么只需要进行少量比较，如果对应元素索引靠后或者根本没有对应元素，就需要遍历所有元素来进行比较。
而 TreeSet 是一个红黑树，红黑树是一种二叉查找树，查找时会从根节点开始比较，小于根节点就找左边的子树，大于根节点就找右边的子树。时间复杂度为 O(log n)。你可以简单理解为二分查找。
所以，总体而言，TreeSet 调用 contains 方法更快。