Come on, guys, let’s meet each other.
I am a worldly wanderer, a Java programming ape who has been wandering for many years
Having already introduced HashMap, today we’ll take a look at another subclass of Map: TreeMap
Front knowledge
Before we introduce TreeMap, let’s take a look at some of the basics
The sorting way
Before we get into sorting, let’s talk a little bit about what it is: ordered, unordered, sort
The orderly
Ensure that the order of insertion is the same as the order of storage in the container, typically:
- List
A disorderly
Not inserted in the same order as stored in the container, typically:
- Set
- Map
The sorting
Output the order of elements that match the rule when iterating based on a rule, for example:
- TreeMap
- TreeSet
So let’s see how we sort this
So, there’s a requirement that we print the elements of the set in some order, so what do we do? In this way, Java provides us with two implementations:
Comparable
Implementing this interface requires an entity object and overriding it compareTo(). Let’s look at an example:
// Define a Student object
class Student implements Comparable<Student> {
public int id;
public String name;
public int age;
public Student(int id, String name, int age) {
this.id = id;
this.name = name;
this.age = age;
}
/** ** */
@Override
public int compareTo(Student o) {
// Sort by age from youngest to oldest
return age - o.age;
}
@Override
public String toString(a) {
return "Student{" +
"id=" + id +
", name='" + name + '\' ' +
", age=" + age +
'} '; }}/ / small case
ArrayList<Student> students = new ArrayList<Student>(6) {{
add(new Student(1."Zhang".20));
add(new Student(2."里斯".18));
add(new Student(3."Fifty".38));
add(new Student(4."Zhao Liu".10));
add(new Student(5."The weather".77));
}};
// Output before sort
System.out.println("Output before sort :");
System.out.println(students);
System.out.println("= = = = = = = = = = = = = = = =");
// Sort operations
Collections.sort(students);
System.out.println("Sorted output :");
System.out.println(students);
[Student{id=1, name=' c ', age=20}, Student{id=2, name=' c ', age=18}, Student{id=3, name=' c ', age=38}, Student {id = 4, name = 'Zhao Liu', the age = 10}, Student {id = 5, name = 'weather', the age = 77}] = = = = = = = = = = = = = = = = [Student {id = 4, name = 'Zhao Liu', the age = 10}, Student {id = 2, name = 'rees, age = 18}, Student {id = 1, name =' zhang 'age = 20}, Student {id = 3, name =' Cathy ', the age = 38}, Student {id = 5, Name =' weather ', age=77}] **/
Copy the codeYou can see that we’ve implemented sorting by age from youngest to oldest
One thing to note here is that in compareTo(), the object passed in is compared to the current object:
- If the comparison is greater than 0, it is sorted in descending order
- If the comparison is less than 0, it is sorted in ascending order
- If the contrast is equal to 0, the current doesn’t change
Comparator
Is it written as an external class, or as the code above? Let’s change a few things:
Collections.sort(students, new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
// Sort by descending ID
return (int) (o2.id - o1.id); }});/** Output before sorting: [Student {id = 1, name = 'zhang' age = 20}, Student {id = 2, name = 'rees, age = 20}, Student {id = 3, name =' Cathy ', the age = 38}, Student {id = 4, Name = 'Zhao Liu, age = 10}, Student {id = 5, name =' weather ', the age = 77}] = = = = = = = = = = = = = = = = sorted output: [Student{id=5, name=' 1 ', age=77}, Student{id=4, name=' 2 ', age= 60}, Student{id=5, name=' 3 ', age= 60}, Student{id=5, name=' 3 ', age= 60}, Student{id=2, Name = 'rees, age = 20}, Student {id = 1, name =' zhang 'age = 20}] * * /
Copy the codeView that the requirements have been implemented
The comparison of returned values in compare() is the same as in the first method
We choose a reasonable sorting way according to the actual needs
The tree is introduced
Tree is a kind of data structure, it is composed of N (N >=1) finite nodes of a hierarchical relationship set. It’s called a tree because it looks like an upside-down tree, meaning it has roots up and leaves down. It has the following characteristics:
- Each node has zero or more children;
- Nodes that have no parents are called root nodes;
- Each non-root node has one and only one parent;
- In addition to the root, each child can be divided into multiple disjoint subtrees
Excerpt from: Baidu Encyclopedia: Tree
Binary tree
Binary tree is an important type of tree structure. It is one of the most commonly used tree structures in data structures. Each node has at most two child nodes
Binary search tree
As the name implies, binary search trees are organized by binary trees. Compared with binary trees, binary search trees have the following features:
- Each node can have a maximum of two nodes
- Insert element nodes using the rule of smaller on the left and larger on the right, if equal, to the right
- So it can be used when traversing nodesdichotomyTo reduce the query of elements
Binary search tree insertion process
Balanced tree
Also known as AVL tree, is based on binary search tree is an extension, that is to say, has all the characteristics of binary search tree. Binary search trees have disadvantages:
- Data insertion mode, easy to cause two sides of the node, one side long side short problem, so in the passdichotomyThere are also performance issues when iterating over elements
The AVL tree has been modified for this situation:
- AVL tree will rotate the unbalanced tree, optimize the whole data structure, ensure the balance of the whole tree, and ensure the efficiency of the whole binary search
- Rotation rule: The absolute value of the difference between the height of the left and right child nodes of each node is at most 1, that is, the balance factor is in the range [-1,1].
Red and black tree
Based on an evolution of balanced tree, there is also rotation operation to maintain the balance of binary tree, and on this basis, color changing operation is added, which has the following characteristics:
- Nodes are red or black
- The root node is black, and each leaf node (NUIL node) is black
- If a node is red, its children are black (i.e., there can be no consecutive red nodes).
- All paths from any node to each of its leaves contain the same number of black nodes
- The maximum path is not more than twice the minimum path
Here is not explained in detail, simply say that there is a concept
Source code analysis TreeMap
Let’s take a look at TreeMap:
Some of the problems I mentioned earlier: We encountered a class where the most important thing was the annotation in the class. Let’s first look at how the annotation for TreeMap describes TreeMap:
- Map based on red-black tree
- Depending on the constructor we use, TreeMap is ordered and we can specify how to sort it
- TreeMap is thread-unsafe, and you need to wrap TreeMap if you want to implement it
SortedMap m = Collections.synchronizedSortedMap(newTreeMap(...) );Copy the codeA constructor
Let’s take a look at how we use TreeMap
TreeMap<String, String> treeMap = new TreeMap<>();
new TreeMap<String, Long>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return 0; }});Copy the codepublic TreeMap(a) {
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
Copy the codeThe second constructor passes in a comparator, which we talked about in sorting, and see what it means to return
But a note of caution here: if we pass no comparator and default to NULL, then we need to understand:
- The Key passed in must implement the type of the Comparable interface, which is explained in the ** PUT ()** method
put()
Before we look at this method, let’s look at a class:
static final class Entry<K.V> implements Map.Entry<K.V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent; }}Copy the codeWe already know that TreeMap’s underlying structure is a red-black tree to store data, so the corresponding implementation in the code looks like this.
Now, how do we add elements
public V put(K key, V value) {
Entry<K,V> t = root;
/ / the root node
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
// The comparator compares the parent node to which the current node belongs
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
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();
@SuppressWarnings("unchecked")
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);
}
// Assign
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// Change color, rotate
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
Copy the codeTo sum up, it can be divided into four steps:
-
Determines that if the current root node is null, the first element currently inserted is the root node element
-
If there is a root node, then the collator compares the element to verify whether the current element should be on the left or the right when the element is added. If the comparison is 0, the current element exists in TreeMap and is overwritten directly. This illustrates the point: In TreeMap, there are no duplicate elements
-
Find its own position, and then reference the pointer
-
Node discoloration operation and rotation operation
The first 3 points are simple, but do.. The while loop uses the collator to compare, and here’s the point I mentioned in the constructor:
class A {
public Long id;
}
TreeMap<A, String> map = new TreeMap<>();
map.put(new A(), "11");
map.put(new A(), "11");
System.out.println(map);
// java.lang.ClassCastException: zopx.top.study.jav.maps.A cannot be cast to java.lang.Comparable
Copy the codeWhen the default constructor is used, there is an error in this approach: type conversion exceptions, which is why TreeMap: Key must be Comparable
Next we will focus on node discoloration and rotation operations
private void fixAfterInsertion(Entry<K,V> x) {
// Mark the current node in red
x.color = RED;
// If there is an imbalance after the element is inserted, adjust it
while(x ! =null&& x ! = root && x.parent.color == RED) {// Check if it is the left node
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if(x == rightOf(parentOf(x))) { x = parentOf(x); rotateLeft(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); }}else {
// Otherwise, the right node
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if(x == leftOf(parentOf(x))) { x = parentOf(x); rotateRight(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); }}}// The root node is always black
root.color = BLACK;
}
Copy the codeLet me analyze the code by drawing it so that it is easier to understand:
This is the simplest example with very few nodes, so you can walk through the code and understand the logic of the code
Right hand operation
private void rotateRight(Entry<K,V> p) {
if(p ! =null) {
Entry<K,V> l = p.left;
p.left = l.right;
if(l.right ! =null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
elsep.parent.left = l; l.right = p; p.parent = l; }}Copy the codeAlso, there are left-handed operations in the red-black tree, which you can see in the source code: rotateLeft(), which is very similar to right-handed operations
It is best to be able to analyze the source code and draw pictures to deepen your understanding
This is how TreeMap is implemented based on red black trees
Remove (Object key) method and put() method similar, you can see the source code
get()
Here’s a quick look at the get() method:
Entry<K,V> p = getEntry(key);
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if(comparator ! =null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
// Default constructor
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while(p ! =null) {
// Continuously compare, if ==0, then this is the current required Entry
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
// Custom sorting
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator<? super K> cpr = comparator;
if(cpr ! =null) {
Entry<K,V> p = root;
while(p ! =null) {
// Continuously compare, if ==0, then this is the current required Entry
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
returnp; }}return null;
}
Copy the codeThis method is relatively simple, with the comparison done through the comparator in the while() loop
TreeMap more API methods
For more information on how to use TreeMap, see its documentation:
TreeMap API documentation
Data structure visualization site