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

這篇文章講的很明白了。

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

2. java 8 為什麼要採用紅黑樹來管理hashmap

java8不是用紅黑樹來管理抄hashmap，而是在hash值相同的情況下（且重復數量大於8），用紅黑樹來管理數據。 紅黑樹相當於排序數據。可以自動的使用二分法進行定位。性能較高。
一般情況下，hash值做的比較好的話基本上用不到紅黑樹。

3. java8 hashmap 為什麼不足64 擴容為什麼鏈表長度定義是8

因為大於threshold所以要擴容，前提是你沒有指定，鏈表長度大於8會轉換為紅黑樹，為了提高查找速度

4. java編寫求方法

importjava.util.Comparator;
importjava.util.Map;
importjava.util.Map.Entry;
importjava.util.Random;
importjava.util.TreeMap;

publicclassRandomNumTest{
publicstaticvoidmain(String[]args){
=newRandom();
Map<Integer,Integer>tm=newTreeMap<Integer,Integer>(
newComparator<Integer>(){

@Override
publicintcompare(Integerarg0,Integerarg1){
returnarg1.compareTo(arg0);
}

});
for(inti=0;i<50;i++){
Integerri=r.nextInt(6)+30;
if(tm.get(ri)==null){
tm.put(ri,1);
}else{
tm.put(ri,tm.get(ri)+1);
}
}
Integerresult=null;
for(Entry<Integer,Integer>e:tm.entrySet()){
if(result==null||e.getValue()>tm.get(result)){
result=e.getKey();
}
System.out.println(e.getKey()+":"+e.getValue());
}
System.out
.println("出現次數最多的是："+result+"；出現了"+tm.get(result)+"次");
}
}

5. 紅黑樹的java實現

public class TreeNode {
public int data;

public String color;

public TreeNode lchild;

public TreeNode rchild;
}

2.RBTree.JAVA

package 第13章_紅黑樹;

/**
* @author greatwqs
* @date 2009.9.12
*
*/
public class RBTree {
TreeNode root;

// 建立紅黑樹
public void create(int[] list) {
for (int i = 0; i < list.length; i++) {
this.insert(list[i]);
}
}

// 插入一個元素
public void insert(int elem) {// 為新元素開辟一個空間
TreeNode s = new TreeNode();
s.data = elem;
s.color = "black";
s.lchild = null;
s.rchild = null;

// 判斷根是否為空,如果為空,則將root指向新元素.否則,進入循環
if (root == null) {
root = s;
root.color = "red";
return;
} else {
// 定義四個指針,分別指向祖先,祖,父,自身
TreeNode p = root, q;
TreeNode parent = root;
TreeNode grand = root;
TreeNode ancestor = root;
while (p != null) {
// 如果P的左右孩子均不為空且顏色均為紅色,則執行顏色轉換並進行調整
if (p.lchild != null && p.rchild != null) {
if (p.lchild.color == ("black")
&& p.rchild.color == ("black")) {
convertColor(p);
adjust(ancestor, grand, parent, p);
}
}

if (elem == p.data) {
return;
}

q = p; // 指針依次向後移動
ancestor = grand;
grand = parent;
parent = p;

// 如果,元素小於P
if (elem < q.data) { // P的左孩子為空
if (q.lchild == null) {
// 將P的左孩子指向新建元素
q.lchild = s;
p = s; // 調整
adjust(ancestor, grand, parent, p);
return;
} else {// P的左孩子不為空
// P向左下移動
p = p.lchild;
}
} else {// 如果,元素大於P
if (elem > q.data) { // P的右孩子為空
if (q.rchild == null) {
// 將P的右孩子指向新建元素
q.rchild = s;
p = s;// 調整
adjust(ancestor, grand, parent, p);
return;
} else {// P的右孩子不為空
// P向右下移動
p = p.rchild;
}
}
}
}
}
}

// 調整顏色的方法
public void convertColor(TreeNode p) {
// 將P的左右孩子的顏色均置為紅
p.lchild.color = "red";
p.rchild.color = "red";
// 若P為根結點,則顏色仍為紅,否則顏色置為黑
if (!(p.equals(root))) {
p.color = "black";
return;
}
if (p.equals(root)) {
p.color = "red";
}
}

public void adjust(TreeNode ancestor, TreeNode grand, TreeNode parent, TreeNode x) {// 是否存在黑黑沖突
if (!(parent.color == "black" && x.color == "black")) {
return;
}
// 符合一次調整的,將調用一次調整
if ((grand.lchild == parent && parent.lchild == x) ||

(grand.rchild == parent && parent.rchild == x)) {
onceAdjust(ancestor, grand, parent, x);
return;
}
// 符合二次調整的,將調用二次調整
if ((grand.lchild == parent && parent.rchild == x) ||

(grand.rchild == parent && parent.lchild == x)) {
twiceAdjust(ancestor, grand, parent, x);
return;
}
}

private void onceAdjust(TreeNode ancestor, TreeNode grand, TreeNode parent, TreeNode x) { // 調整父結點和祖結點的顏色
this.exchangeColor(grand);
this.exchangeColor(parent);
// 將祖先結點指向父結點
if (ancestor == grand && ancestor == this.root) {
this.root = parent;
ancestor = parent;
} else {
if (ancestor.lchild == grand) {
ancestor.lchild = parent;
} else if (ancestor.rchild == grand) {
ancestor.rchild = parent;
}
}

// 左左型調整
if (grand.lchild == parent && parent.lchild == x) {
grand.lchild = parent.rchild;
parent.rchild = grand;
return;
}

// 右右型調整
if (grand.rchild == parent && parent.rchild == x) {
grand.rchild = parent.rchild;
parent.lchild = grand;
return;
}
}

private void twiceAdjust(TreeNode ancestor, TreeNode grand, TreeNode parent, TreeNode x) { // 調整自身結點和祖結點的顏色
this.exchangeColor(grand);
this.exchangeColor(x);
// 將祖先結點指向自身結點
if (ancestor == grand && ancestor == root) {
root = x;
ancestor = x;
} else {
if (ancestor.lchild == grand) {
ancestor.lchild = x;
} else if (ancestor.rchild == grand) {
ancestor.rchild = x;
} else if (ancestor == root) {
ancestor = x;
root = x;
}
}

// 左右型調整
if (grand.lchild == parent && parent.rchild == x) {
grand.lchild = x.rchild;
parent.rchild = x.lchild;
x.lchild = parent;
x.rchild = grand;
return;
}

// 右左型調整
if (grand.rchild == parent && parent.lchild == x) {
grand.rchild = x.lchild;
parent.lchild = x.rchild;
x.lchild = grand;
x.rchild = parent;
return;
}
}

// 變換顏色的方法
private void exchangeColor(TreeNode p) {
if (p.color.equals("black")) {
p.color = "red";
} else {
p.color = "black";
}
}

public void inorder() {
inorder(root);
}

// 中序遍歷
private void inorder(TreeNode root) {
if (root != null) {
inorder(root.lchild);
System.out.println(root.data + " " + root.color);
inorder(root.rchild);
}
}
}

3.RBTreeTest.JAVA

package 第13章_紅黑樹;

import java.util.Random;
import java.util.Scanner;

/**
* @author greatwqs
* @date 2009.9.12
*
*/

public class RBTreeTest {

/**
* @param args
*/
public static void main(String[] args) {

RBTree rbt = new RBTree();
Scanner wqs = new Scanner(System.in);
Random rand = new Random();

System.out.println("請輸入建立紅黑樹的元素數目:");
int TotalNum = wqs.nextInt();
int[] list = new int[TotalNum];

System.out.println("創建紅黑樹隨機元素值如下:");
for(int i = 0; i < list.length; i++){
list[i] = Math.abs(rand.nextInt()) % 100;
System.out.println(list[i]);
}

rbt.create(list);
System.out.println("紅黑樹建立之後輸出:");
rbt.inorder();

}

}

=======================

運行結果如下(具體從大到小排序,見二叉查找樹,相似演算法):

===========================

請輸入建立紅黑樹的元素數目:
8
創建紅黑樹隨機元素值如下:
30
34
52
61
48
36
53
73
紅黑樹建立之後輸出:
30 red
36 black
48 red
52 black
53 black
61 red
73 black
34 red
36 black
48 red
52 black
53 black
61 red
73 black

6. 演算法中紅黑樹的刪除方法問題.

了無適俗韻真可與晤語

7. 有關紅黑樹的java程序，編譯成功但運行不出結果。

java8不是用紅黑樹來管理hashmap，而是在hash值相同的情況下（且重復數量大於8），用紅黑樹來管內理數據容。 紅黑樹相當於排序數據。可以自動的使用二分法進行定位。性能較高。
一般情況下，hash值做的比較好的話基本上用不到紅黑樹。

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

9. 二叉搜索樹java 京東金融java面試題 紅黑樹有什麼用java紅黑樹 java trie樹 快速

java8不是用紅黑樹來管理hashmap，而是在hash值相同的情況下（且重復數量大於8），用紅黑樹來管理數據。 紅黑樹相當於排序數據。可以自動的使用二分法進行定位。性能較高。
一般情況下，hash值做的比較好的話基本上用不到紅黑樹。