紅黑樹java

❶ java中哪些數據結構使用了紅黑樹

參考資料的網頁上有比較的代碼,你可以仔細看下~~~

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可以實現,它還可以按讀取順序來排列，像連接池中可以應用。

❷ java中的TreeMap為什麼要用紅黑樹實現，而不用AVL樹實現

這篇文章講的很明白了。

http://blog.csdn.net/hustyangju/article/details/27214251?utm_source=tuicool
很疑惑，為什麼大家碰到問題不先自己去網路呢？

❸ 紅黑樹和平衡二叉樹 區別

紅黑樹和平衡二叉樹的主要區別如下：
平衡二叉樹（AVL）樹是嚴格的平衡二叉樹，平衡條件必須滿足（所有節點的左右子樹高度差不超過1）。不管我們是執行插入還是刪除操作，只要不滿足上面的條件，就要通過旋轉來保持平衡，而的英文旋轉非常耗時的。所以平衡二叉樹（AVL）適合用於插入與刪除次數比較少，但查找多的情況。
紅黑樹在二叉查找樹的基礎上增加了著色和相關的性質使得紅黑樹相對平衡，從而保證了紅黑樹的查找、插入、刪除的時間復雜度最壞為O(log
n)。所以紅黑樹適用於搜索，插入，刪除操作較多的情況。
(3)紅黑樹java擴展閱讀：
平衡二叉樹在Windows
NT內核中廣泛存在。
紅黑樹的應用：
1、在C
++的STL中，地圖和集都是用紅黑樹實現的；
2、著名的Linux的的進程調度完全公平調度程序，用紅黑樹管理進程式控制制塊，進程的虛擬內存區域都存儲在一顆紅黑樹上，每個虛擬地址區域都對應紅黑樹的一個節點，左指針指向相鄰的地址虛擬存儲區域，右指針指向相鄰的高地址虛擬地址空間；
3、IO多路復用的epoll的的的實現採用紅黑樹組織管理的sockfd，以支持快速的增刪改查；
4、Nginx的的的中用紅黑樹管理定時器，因為紅黑樹是有序的，可以很快的得到距離當前最小的定時器；
5、Java中的TreeMap中的實現。
參考資料：
網路-平衡二叉樹
網路-紅黑樹