TreeMap:赤黒ツリーベースのMapインタフェースの実装
13034 ワード
』TreeMap:赤黒ツリーに基づくMapインタフェースの実装である.
赤と黒の木:バランスツリー
取り出すには、前順遍歴、中順遍歴、後順遍歴の3つの方法があります.
』のソート:
A自然並べ替え--TreeMap無パラメトリック構造
Bコンパレータ並べ替え-TreeMapコンパレータのパラメータ構造
』TreeMap put()メソッドソースコード
ケース:
//上記の例では、自然ソートではなくコンパレータソートを使用しているため、keyのStudioとしてComparableインタフェースを実装する必要はありません
赤と黒の木:バランスツリー
取り出すには、前順遍歴、中順遍歴、後順遍歴の3つの方法があります.
』のソート:
A自然並べ替え--TreeMap無パラメトリック構造
TreeMap<key ,value > map= new TreeMap<key ,value >();
//key Comparable , hashCode() equals()
Bコンパレータ並べ替え-TreeMapコンパレータのパラメータ構造
TreeMap<key ,value > map= new TreeMap<key ,value >( new Comparator<key > (){
@Override
compare(){
}
});
』TreeMap put()メソッドソースコード
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
// TBD:
// 5045147: (coll) Adding null to an empty TreeSet should
// throw NullPointerException
//
// compare(key, key); // type check
root = new Entry<K,V>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;// TreeMap comparator null
//
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
//
else {
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<K,V>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
ケース:
package cn.itcast_04;
import java.util.Comparator;
import java.util.Set;
import java.util.TreeMap;
/*
* TreeMap<Student,String>
* :Student
* :String
*/
public class TreeMapDemo2 {
public static void main(String[] args) {
// ( Comparator )
TreeMap<Student, String> tm = new TreeMap<Student, String>(
new Comparator<Student>() {
@Override
public int compare(Student s1, Student s2) {
//
int num = s1.getAge() - s2.getAge();
//
int num2 = num == 0 ? s1.getName().compareTo(
s2.getName()) : num;
return num2;
}
});
//
Student s1 = new Student(" ", 30);
Student s2 = new Student(" ", 35);
Student s3 = new Student(" ", 33);
Student s4 = new Student(" ", 32);
Student s5 = new Student(" ", 33);
//
tm.put(s1, " ");
tm.put(s2, " ");
tm.put(s3, " ");
tm.put(s4, " ");
tm.put(s5, " ");
//
Set<Student> set = tm.keySet();
for (Student key : set) {
String value = tm.get(key);
System.out.println(key.getName() + "---" + key.getAge() + "---"
+ value);
}
}
}
//上記の例では、自然ソートではなくコンパレータソートを使用しているため、keyのStudioとしてComparableインタフェースを実装する必要はありません
package cn.itcast_04;
public class Student {
private String name;
private int age;
public Student() {
super();
}
public Student(String name, int age) {
super();
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
}