The introduction
The Map<K,V> interface and the Set<E> interface were described in the first article in the series. The Set<E> interface defines a Set of unrepeatable elements that cannot be added to a Set and cannot be accessed through an index. The Map<K,V> interface defines a set of objects that Map from keys to values. It has also been said that Map<K,V> keysets are implemented by Set<E> because the keyset cannot be repeated. By looking at the constructor for TreeSet<E>, you can see that this is done with TreeMap<K,V>, but only with a key. Therefore, TreeMap<K,V> will be explained in detail in this article, and TreeSet<E> will not be explained too much.
public TreeSet(a) {
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
Copy the codeFrame structure
TreeMap<K,V> inherits SortedMap<K,V> interface, SortedMap<K,V> provides sorting function, using the comparator method to compare each object in TreeMap to achieve sorting purpose. The default sort is ascending, or it can be sorted by passing in the Comparator using the constructor’s Comparator.
// The SortedMap interface contains the comparison method comparator
public interface SortedMap<K.V> extends Map<K.V> {
Comparator<? super K> comparator();
}
public interface Comparator<T> {
int compare(T o1, T o2);
boolean equals(Object obj);
}
// The TreeMap constructor passes in the Comparator
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public Comparator<? super K> comparator() {
return comparator;
}
// The TreeSet constructor passes in the Comparator
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
public Comparator<? super E> comparator() {
return m.comparator();
}
Copy the codeThe data structure
TreeMap<K,V> is an ordered Map, and the underlying data structure is a red-black tree. Red-black tree is a widely used tree structure. Here, I will briefly describe the advantages and disadvantages of red-black tree data structure compared with other tree structures:
- Red-black tree is a kind of self-balanced binary search tree, also called symmetric binary B tree. The search, insert and delete time complexity of red-black tree is O(logn), which is widely used.
- Compared with AVL trees (balanced binary trees), red black trees sacrifice some balance (red black trees are not completely balanced binary trees) in exchange for fewer rotation operations during insert/delete operations, and the overall insert/delete performance is better than AVL trees. So many data structures sorted in memory are stored using red-black trees rather than AVL trees.
- Red-black tree than b-tree and B + tree, under the condition of the same node red-black tree due to the depth is deeper than B and B + tree, to read and write IO very frequently, so that fits in the memory of a small amount of reading, and B – and B + tree is very much, because each node element access IO number is relatively small, suitable for large amounts of data stored in the disk, A storage structure similar to database records. Due to the limited space in this paper, we will focus on binary trees and red-black trees, not on AVL trees, B- trees, B+ trees.
Binary sort tree
TreeMap<K,V> = TreeMap<K,V> = TreeMap<K,V> = TreeMap<K,V> = TreeMap<K,V> = TreeMap<K,V> = TreeMap<K,V> = TreeMap<K,V> Binary tree Sorting tree is a very typical tree structure, usually using a linked list as the storage structure (can also use arrays). Because each node in a tree stores references to parent nodes, it is easier to express it in a linked list. If the array is used for storage, it is a waste of array space when there is no child node. At the same time, when searching for a specific element, because there is no reference to the parent node of the element of the array, it can only be traversed according to certain rules, which is very inconvenient. Therefore, in most cases, linked lists are used to store the tree structure. Binary trees can obtain an ordered sequence through middle order traversal, which is very convenient to search and delete. In general, the time complexity is O(logn), and O(n) is the worst. A sorted binary tree is either an empty tree or has the following properties:
- If the left subtree of any node is not empty, the values of all nodes in the left subtree are less than the values of its root node.
- If the right subtree of any node is not empty, the values of all nodes in the right subtree are greater than the values of its root node.
- The left and right subtrees of any node are binary search trees respectively.
- There are no nodes with equal keys. Here is a typical binary tree:
Binary tree traversal
Binary tree as a tree structure, the purpose of traversal is to visit all nodes in the tree in turn, and make each node is only visited once. There are many ways of traversal, including pre-middle-post-sequence and sequential traversal. Middle-order traversal is to visit the left subtree first, then the root node, and finally the right node. According to the properties of binary sorting trees, middle-order traversal can obtain a sorting sequence from smallest to largest (by default). So middle-order traversal is used most frequently. Below is the legend and code implementation of the middle-order traversal:
public class BinaryTree {
public void traversalBinaryTree(TreeNode tree) {
// If you reach the leaf node, exit the current method and continue searching
if (tree == null) {
return;
}
// Iterate over the left node, all the way to the leftmost leaf node
traversalBinaryTree(tree.left);
System.out.println(tree.value);
// Iterate over the right node, all the way to the leftmost leaf node
traversalBinaryTree(tree.right);
}
class TreeNode {
// Node value
int value;
/ / the left node
TreeNode left;
/ / right node
TreeNode right;
/ / the parent node
TreeNode parent;
public TreeNode(int treeValue, TreeNode parentNode) {
value = treeValue;
parent = parentNode;
left = null;
right = null; }}}Copy the codePre-order traversal and post-order traversal:
// preorder traversal
System.out.println(tree.value);
traversalBinaryTree(tree.left);
traversalBinaryTree(tree.right);
// after the sequence traversal
traversalBinaryTree(tree.left);
traversalBinaryTree(tree.right);
System.out.println(tree.value);
Copy the codeAdd binary tree
Understanding binary tree traversal, understanding binary tree adding is very simple, through the middle order traversal from small to large to find the empty leaf node to add value, we implement a binary tree adding method:
public void addBinaryTreeNode(int value) {
/ / the root node
TreeNode tree = root;
if (tree == null) {
// If the root node is empty, create a new node
root = new TreeNode(value, null);
return;
}
// Store the parent node of the new node
TreeNode parentNode;
do {
// Use the node after the last loop as a reference
parentNode = tree;
// If the newly inserted value is less than the current value, look left
if (value < tree.value) {
tree = tree.left;
// If the newly inserted value is greater than the current value, look to the right
} else if (value > tree.value) {
tree = tree.right;
// If it is equal, the same node is proved
} else {
return; }}while(tree ! =null);
// create a node. ParentNode is the parentNode of the new node
TreeNode node = new TreeNode(value, parentNode);
// The new node is the left or right node
if (value < parentNode.value) {
parentNode.left = node;
} else{ parentNode.right = node; }}public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
binaryTree.addBinaryTreeNode(10);
binaryTree.addBinaryTreeNode(5);
binaryTree.addBinaryTreeNode(20);
binaryTree.addBinaryTreeNode(7);
binaryTree.addBinaryTreeNode(6);
binaryTree.addBinaryTreeNode(3);
binaryTree.addBinaryTreeNode(15);
binaryTree.addBinaryTreeNode(30);
binaryTree.traversalBinaryTree(binaryTree.root);
}
// Console:
/ / 3
/ / 5
/ / 6
/ / 7
/ / 10
/ / 15
/ / 20
/ / 30
Copy the codeThrough the above binary tree to add nodes logic, we will analyze TreeMap<K,V> source code to add nodes to achieve. TreeMap<K,V> puts the key and value into an Entry<K,V> Node using the PUT (K key, V value) method. Entry<K,V> is equivalent to the Node in the above code.
public V put(K key, V value) {
/ / the root node
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
// If the root node is empty, create a new node
root = new Entry<>(key, value, null);
// Record the number of Map elements
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
// If the comparator is not empty, the custom comparator is used for sorting
if(cpr ! =null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
// If the newly inserted key is smaller than the current key, look left
if (cmp < 0)
t = t.left;
// If the newly inserted key is larger than the current key, look to the right
else if (cmp > 0)
t = t.right;
// Equal overwrites
else
return t.setValue(value);
} while(t ! =null);
}
// If the comparator is empty, the default comparator is used for sorting
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);
}
,v>
Entry<K,V> e = new Entry<>(key, value, parent);
// If the newly inserted key is smaller than the key of the parent node, the inserted node is the left child of the parent node
if (cmp < 0)
parent.left = e;
// If the newly inserted key is larger than the key of the parent node, the inserted node is the right child of the parent node
else
parent.right = e;
// Focus: fix red black tree
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
Copy the codeBinary tree deletion
Deleting a binary tree is a bit more complicated than adding, because if the deleted node is not a leaf node, you need to consider that node to replace the current node. Deletion can be divided into six cases:
- If the deleted node has no left or right child nodes and no parent node, it is the root node and can be deleted directly.
- The deleted node does not have left and right child nodes, but has a parent node, which is a leaf node, and can be deleted directly.
- The deleted node is the root node, which has left or right nodes. Replace the deleted root node with the left node or right node.
- The deleted node is not the root node, but only the left node. Replace the deleted node with the left node.
- The deleted node is not the root node, but only the right node. Replace the deleted node with the right node.
- The deleted node has left and right child nodes. Replace the value of the deleted node with the immediate successor of the deleted node, and then delete the immediate successor. The situation changes to 2, 4, or 5.
Below, we will implement a binary tree deletion algorithm according to the six cases of binary tree deletion:
public void removeBinaryTreeNode(int value) {
/ / the root node
TreeNode tree = root;
if (tree == null) {
return;
}
TreeNode currentNode = findBinaryTreeNode(value);
if (currentNode == null) {
return;
}
if (currentNode.left == null && currentNode.right == null) {
// Delete the root node and have no left or right children
if (currentNode.parent == null) {
root = null;
} else {
// Delete the leaf node
if (currentNode.parent.left == currentNode) {
currentNode.parent.left = null;
} else {
currentNode.parent.right = null;
}
currentNode.parent = null; }}else if (currentNode.left == null || currentNode.right == null) {
TreeNode replaceNode = currentNode.left == null ? currentNode.right : currentNode.left;
replaceNode.parent = currentNode.parent;
// Delete the root node and have only one child node
if (currentNode.parent == null) {
root = replaceNode;
// The left node is not the root node
} else if (currentNode == currentNode.parent.left) {
currentNode.parent.left = replaceNode;
// The right node is not the root node
} else {
currentNode.parent.right = replaceNode;
}
currentNode.parent = currentNode.left = currentNode.right = null;
} else {
// There are both left and right nodes
// the successorNode needs to remove its successorNode
TreeNode successorNode = currentNode.right;
TreeNode parentNode;
// Find the successor node
do {
parentNode = successorNode;
successorNode = successorNode.left;
} while(successorNode ! =null);
successorNode = parentNode;
// Overrides the value of the node to be deleted to the value of the successor node
currentNode.value = successorNode.value;
// The left node of the successor node must be empty. If it is not empty, the current node is not the successor node
if(successorNode.right ! =null) {
// Associate the right node of the successor node with the parent of the successor node
TreeNode replaceNode = successorNode.right;
replaceNode.parent = successorNode.parent;
if (successorNode.parent.left == successorNode) {
successorNode.parent.left = replaceNode;
}
if(successorNode.parent.right == successorNode) { successorNode.parent.right = replaceNode; }}// Delete subsequent nodes
successorNode.parent = successorNode.left = successorNode.right = null; }}// Find the tree node corresponding to the current value
public TreeNode findBinaryTreeNode(int value) {
/ / the root node
TreeNode tree = root;
if (tree == null) {
return null;
}
// Store the parent node of the new node
TreeNode parentNode;
do {
// The loop iterates from small to large until the leaf is empty
parentNode = tree;
if (value < tree.value) {
tree = tree.left;
} else if (value > tree.value) {
tree = tree.right;
} else {
returnparentNode; }}while(tree ! =null);
return null;
}
Copy the codeThrough the above binary tree to delete the node logic, and then to analyze the TreeMap<K,V> source code to delete the node implementation. TreeMap<K,V> uses remove(Object key) to delete the node represented by the key. First, getEntry(key) is used to find Entry<K,V> P of the node to be deleted, and then deleteEntry(Entry<K,V> p) is used to delete P.
public V remove(Object key) {
// find node p represented by key
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
// If the deleted node is not empty, find the immediate successor of P, overwrite the key and value of P with the key and value of the successor node, and then delete the successor node.
// This step is very clever. The node to be deleted is converted to the immediate successor of the node to be deleted, and case six is converted to case two, four, five
if(p.left ! =null&& p.right ! =null) {
// Find the immediate successor of P
Entry<K,V> s = successor(p);
// Subsequent nodes overwrite keys and values to P
p.key = s.key;
p.value = s.value;
// The node to be deleted becomes the successor node of P
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
// Find the node to replace
// If P has a left node, then there is no right node. Because if both left and right nodes exist, the successor is found (the left node of the successor must be empty).
// If the left node of P does not exist and the right node exists, replace it with the right node.Entry<K,V> replacement = (p.left ! =null ? p.left : p.right);
// The preceding steps show that only one left/right node can exist at the same time. Replacement is any of the left/right child nodes
if(replacement ! =null) {
// Link replacement to parent
// The p node will be deleted, and the parent of the node to be replaced points to the parent of p
replacement.parent = p.parent;
// if the parent node of p is empty, the root node is deleted.
if (p.parent == null)
root = replacement;
//replace to the left node
else if (p == p.parent.left)
p.parent.left = replacement;
//replace to the right node (case 5)
else
p.parent.right = replacement;
// Null out links so they are OK to use by fixAfterDeletion.
// Delete the P node
p.left = p.right = p.parent = null;
// Fix replacement
// Focus: fix red black tree
if (p.color == BLACK)
fixAfterDeletion(replacement);
// If the replacement node is empty and the parent node of p is also empty, the root node is deleted.
} else if (p.parent == null) { // return if we are the only node.
root = null;
// If the replacement node is empty, the parent node of P is not empty, indicating that it is a leaf node.
} else { // No children. Use self as phantom replacement and unlink.
// Focus: fix red black tree
if (p.color == BLACK)
fixAfterDeletion(p);
// Remove the association between the leaf node and the parent node
if(p.parent ! =null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null; }}}// Find the immediate successor of t node
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if(t.right ! =null) {
Entry<K,V> p = t.right;
while(p.left ! =null)
p = p.left;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while(p ! =null && ch == p.right) {
ch = p;
p = p.parent;
}
returnp; }}Copy the codeconclusion
In this article, we realized the operation logic of traversal, node addition and node deletion of binary tree by ourselves, and then explained the logic of node deletion and addition in TreeMap<K,V> in detail, skipping the operation of red-black tree. After reading this, I believe you have some understanding of the basic operation of binary trees. In the next article, WE will explain in detail the operation of TreeMap<K,V> to satisfy the properties of red-black trees.