紅黑樹演算法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 方法更快。