getEntryUsingComparator
Copy the code1. Class definition
public class TreeMap<K.V>
extends AbstractMap<K.V>
implements NavigableMap<K.V>, Cloneable.java.io.Serializable
Copy the codeYou can see this in the class definition
- TreeMap is a generic class
- TreeMap inherits from AbstractMap
- TreeMap implements NavigableMap, indicating that TreeMap is directional and supports navigation
- TreeMap implements the Cloneable interface, indicating that TreeMap supports cloning
- TreeMap implements the java.io.Serializable interface, indicating that TreeMap supports serialization
2. Field attributes
// The order of treemaps is determined by the comparator. If the comparator is empty, the order is determined by the comparator that comes with the key
private final Comparator<? super K> comparator;
// The root node, Entry is a red-black tree structure
private transient Entry<K,V> root;
// Number of nodes
private transient int size = 0;
// Modify statistics
private transient int modCount = 0;
// Cache the set of key-value pairs
private transient EntrySet entrySet;
// Cache key Set
private transient KeySet<K> navigableKeySet;
private transient NavigableMap<K,V> descendingMap;
Copy the codeYou can see this in the field properties
- TreeMap is a red-black tree structure
- TreeMap holds the root node root
3. Construction method
// The default constructor
public TreeMap(a) {
// The comparator defaults to null
comparator = null;
}
// Pass in a comparator object
public TreeMap(Comparator<? super K> comparator) {
// Set the comparator
this.comparator = comparator;
}
// Pass in a Map object
public TreeMap(Map<? extends K, ? extends V> m) {
// Set the comparator to null
comparator = null;
// Add Map object data
putAll(m);
}
// Pass a SortedMap object
public TreeMap(SortedMap<K, ? extends V> m) {
// Assign the SortedMap comparator to the current comparator
comparator = m.comparator();
try {
// Add data to the SortedMap object
buildFromSorted(m.size(), m.entrySet().iterator(), null.null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
Copy the codeYou can see this in the constructor
- TreeMap defaults to null and essentially uses the comparator that comes with the Key. If the default comparator is null, objects for the Key must implement the Comparable interface
- TreeMap can be initialized by specifying a comparator
- TreeMap can receive a Map object for initialization
- TreeMap can receive a SortedMap object to initialize
Method 4.
The size method
// Get the number of elements
public int size(a) {
// Return the size of the cache
return size;
}
Copy the codeEither containsKey method
// Check whether the node corresponding to the key exists
public boolean containsKey(Object key) {
// getEntry is used to obtain the node corresponding to the key
returngetEntry(key) ! =null;
}
Copy the codeThe get method
// Find the value based on the passed key
public V get(Object key) {
// Use getEntry to find the node corresponding to the key
Entry<K,V> p = getEntry(key);
// Return null if the node does not exist, return value of the node
return (p==null ? null : p.value);
}
Copy the codeThe getEntry method
// Get the corresponding node based on the passed key
final Entry<K,V> getEntry(Object key) {
if(comparator ! =null)
// If there is a comparator, call the getEntryUsingComparator method to find the node
return getEntryUsingComparator(key);
// Check the validity of the key
if (key == null)
throw new NullPointerException();
// Objects for key must implement the Comparable interface
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
// Get a copy of the root node
Entry<K,V> p = root;
// Search through the while loop
while(p ! =null) {
//key for comparison
int cmp = k.compareTo(p.key);
if (cmp < 0)
// If the key passed in is smaller than the key of the current node, look left
// Point the current node to the left child node
p = p.left;
else if (cmp > 0)
// If the key passed in is larger than the current node's key, look to the right
// Point the current node to the right child node
p = p.right;
else
// The current node is returned
return p;
}
// Not found, return null
return null;
}
Copy the codeGetEntryUsingComparator method
// Use TreeMap's built-in comparator to find nodes
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
// Get a copy of the comparator
Comparator<? super K> cpr = comparator;
if(cpr ! =null) {
// If the comparator is not null
// Get a copy of the root node
Entry<K,V> p = root;
// Use the while loop to find
while(p ! =null) {
// Use TreeMap's built-in comparator for comparison
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
// If the key passed in is smaller than the key of the current node, look left
// Point the current node to the left child node
p = p.left;
else if (cmp > 0)
// If the key passed in is larger than the current node's key, look to the right
// Point the current node to the right child node
p = p.right;
else
// The current node is returned
returnp; }}// Not found, return null
return null;
}
Copy the codeGetCeilingEntry method
// Returns a node that is only greater than or equal to the key passed in
final Entry<K,V> getCeilingEntry(K key) {
// Get a copy of the root node
Entry<K,V> p = root;
// Exit the while loop with p null
while(p ! =null) {
// Compare the passed key with the current key traversing the node
int cmp = compare(key, p.key);
if (cmp < 0) {
// If the key passed in is smaller than the key currently traversed by the node
if(p.left ! =null)
If the left child of the current traversal node is not null, continue traversal to the left
// Refer the current traversal node to the left child node
p = p.left;
else
// Smaller than the current node, but the current node does not have a left child node
return p;
} else if (cmp > 0) {
// If the key passed is greater than the key currently traversed the node
if(p.right ! =null) {
// If the right child of the current traversal node is not null, continue traversal to the right
// Point the current traversal node to the right child node
p = p.right;
} else {
// If the current traversal node right child node is null
// Get the parent of the current traversal node
Entry<K,V> parent = p.parent;
// A copy of the node currently traversed
Entry<K,V> ch = p;
// the while loop iterates
// The parent node is the left child of the grandfather node
while(parent ! =null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
// returns the grandfather node
returnparent; }}else
// The passed key is equal to the current traversal node key, returns the current node
return p;
}
return null;
}
Copy the codeGetFloorEntry method
// Returns a node that is only less than or equal to the key passed in
final Entry<K,V> getFloorEntry(K key) {
// Get a copy of the root node
Entry<K,V> p = root;
// Exit the while loop with p null
while(p ! =null) {
// Compare the passed key with the current key traversing the node
int cmp = compare(key, p.key);
if (cmp > 0) {
// If the key passed is greater than the key currently traversed the node
if(p.right ! =null)
// If the key currently traversed has a right child, continue traversing to the right
// Point the current traversal node to the right child node
p = p.right;
else
// If the current traversal node does not have a right child, returns the current traversal node
return p;
} else if (cmp < 0) {
// If the key passed in is smaller than the key currently traversed by the node
if(p.left ! =null) {
If the left child of the current traversal node is not null, continue traversal to the left
// The current traversal node refers to the left child
p = p.left;
} else {
// If the left child of the current traversal node is null
// Get the parent of the current traversal node
Entry<K,V> parent = p.parent;
// A copy of the node currently traversed
Entry<K,V> ch = p;
// the while loop iterates
// Look up until the parent node is the right child of the grandfather node
while(parent ! =null && ch == parent.left) {
ch = parent;
parent = parent.parent;
}
// returns the grandfather node
returnparent; }}else
// If the key passed is equal to the current traversal node, return the current traversal node
return p;
}
return null;
}
Copy the codeGetHigherEntry method
// Returns a node that is only larger than the key passed in
final Entry<K,V> getHigherEntry(K key) {
// Get a copy of the root node
Entry<K,V> p = root;
//while loop, p is null and exits
while(p ! =null) {
// Compare the incoming key with the current traversal node key
int cmp = compare(key, p.key);
if (cmp < 0) {
// If the key passed in is smaller than the key currently traversed by the node
if(p.left ! =null)
If the left child of the currently traversed node is not null, continue traversing to the left
// The current traversal node refers to the left child
p = p.left;
else
// If the left child of the current traversal node is null
// Returns the current node
return p;
} else {
// If the key passed is greater than or equal to the current traversal node key
if(p.right ! =null) {
// If the right child of the current traversal node is not null, continue traversal to the right
// The current traversal node points to the right child node
p = p.right;
} else {
// If the right child of the current traversal node is null
// Get the parent of the current traversal node
Entry<K,V> parent = p.parent;
// Save a copy of the current traversal node
Entry<K,V> ch = p;
// the while loop iterates
// Look up until the parent node is the left child of the grandfather node
while(parent ! =null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
// returns the grandfather node
returnparent; }}}return null;
}
Copy the codegetLowerEntry
// Returns a node that is only smaller than the key passed in
final Entry<K,V> getLowerEntry(K key) {
// Get a copy of the root node
Entry<K,V> p = root;
//while loop, p is null and exits
while(p ! =null) {
// Compare the incoming key with the current traversal node key
int cmp = compare(key, p.key);
if (cmp > 0) {
// If the key passed is greater than the key currently traversed the node
if(p.right ! =null)
// If the key currently traversed has a right child, continue traversing to the right
// Point the current traversal node to the right child node
p = p.right;
else
// If the current traversal node does not have a right child, returns the current traversal node
return p;
} else {
// If the key passed is less than or equal to the current traversal node key
if(p.left ! =null) {
If the left child of the current traversal node is not null, continue traversal to the left
// The current traversal node refers to the left child
p = p.left;
} else {
// Get the parent of the current traversal node
Entry<K,V> parent = p.parent;
// A copy of the node currently traversed
Entry<K,V> ch = p;
// the while loop iterates
// Look up until the parent node is the right child of the grandfather node
while(parent ! =null && ch == parent.left) {
ch = parent;
parent = parent.parent;
}
// returns the grandfather node
returnparent; }}}return null;
}
Copy the codeContainsValue method
// Check whether the corresponding value exists
public boolean containsValue(Object value) {
// Use the for loop to find
//getFirstEntry gets the leftmost child node, which is the smallest node
Succeeded in obtaining the next node that is only larger than the current node
// The for loop is traversed from small to large by key
for(Entry<K,V> e = getFirstEntry(); e ! =null; e = successor(e))
// Use valEquals to compare values
if (valEquals(value, e.value))
// If it exists, return true
return true;
// Does not exist, return false
return false;
}
Copy the codeGetFirstEntry method
// Get the first node with the smallest key, the leftmost child node
final Entry<K,V> getFirstEntry(a) {
// Get a copy of the root node
Entry<K,V> p = root;
if(p ! =null)
// If the root is not null
// Walk through the tree from the root node
while(p.left ! =null)
// Point the node to the left child node
p = p.left;
// Return the node found all the way to the left
return p;
}
Copy the codeFirstEntry method
// Deep copy the first node
public Map.Entry<K,V> firstEntry(a) {
//getFirstEntry gets the first node with the smallest key, the leftmost child node
//exportEntry Returns a new SimpleImmutableEntry object
return exportEntry(getFirstEntry());
}
Copy the codeGetLastEntry method
// Get the rightmost node, the node with the largest key, that is, the rightmost child node
final Entry<K,V> getLastEntry(a) {
// Get a copy of the root node
Entry<K,V> p = root;
if(p ! =null)
// If the root is not null
// Walk through the tree from the root node
while(p.right ! =null)
// Point the node to the right child node
p = p.right;
// Return the node found all the way to the right
return p;
}
Copy the codeLastEntry method
// Deep copy the last node
public Map.Entry<K,V> lastEntry(a) {
//getLastEntry gets the rightmost node with the largest key, that is, the rightmost child node
//exportEntry Returns a new SimpleImmutableEntry object
return exportEntry(getLastEntry());
}
Copy the codeSuccessor method
// Find the node whose key is only larger than the current node
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
// If the node is passed in as null, null is returned
return null;
// Find the leftmost child of the right child
else if(t.right ! =null) {
// If the right child is not null
// Save a copy of the right child node
Entry<K,V> p = t.right;
// Use the while loop to keep looking to the left
while(p.left ! =null)
p = p.left;
// Returns the last node found
return p;
} else {
// If the current node is the right node
// The while loop keeps looking up until it finds that the parent is the left child, which is always smaller than the right
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 codeValEquals method
// Compare whether two objects are equal
static final boolean valEquals(Object o1, Object o2) {
return (o1==null ? o2==null : o1.equals(o2));
}
Copy the codeComparator method
// Get the comparator
public Comparator<? super K> comparator() {
return comparator;
}
Copy the codeFirstKey method
// Get the key of the first node (the leftmost child node)
public K firstKey(a) {
//getFirstEntry gets the first node
//key Obtains the key of the node
return key(getFirstEntry());
}
Copy the codeLastKey method
// Get the key of the last node (the rightmost child node)
public K lastKey(a) {
//getLastEntry gets the last node
//key Obtains the key of the node
return key(getLastEntry());
}
Copy the codeThe key way to
// Get the key of the node
static <K> K key(Entry
e)
,?> {
// If the node is null, an exception is thrown
if (e==null)
throw new NoSuchElementException();
return e.key;
}
Copy the codeKeyOrNull method
If the node is null, null is returned
static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
return (e == null)?null : e.key;
}
Copy the codePollFirstEntry method
// Get the first element and delete it
public Map.Entry<K,V> pollFirstEntry(a) {
//getFirstEntry gets the first node with the smallest key, the leftmost child node
Entry<K,V> p = getFirstEntry();
// Generate a new Entry object according to p
Map.Entry<K,V> result = exportEntry(p);
if(p ! =null)
// If p is not null, delete p
deleteEntry(p);
// Returns the newly generated object
return result;
}
Copy the codePollLastEntry method
// Get the last element and delete it
public Map.Entry<K,V> pollLastEntry(a) {
//getLastEntry gets the rightmost node with the largest key, that is, the rightmost child node
Entry<K,V> p = getLastEntry();
// Generate a new Entry object according to p
Map.Entry<K,V> result = exportEntry(p);
if(p ! =null)
// If p is not null, delete p
deleteEntry(p);
// Returns the newly generated object
return result;
}
Copy the codeLowerEntry method
// Get a node that is only smaller than the key passed in and wrap it as a new object
public Map.Entry<K,V> lowerEntry(K key) {
//getLowerEntry gets the node that is only smaller than the key passed in
//exportEntry wraps a new object
return exportEntry(getLowerEntry(key));
}
Copy the codeLowerKey method
// Get the key of the node that is only smaller than the key passed in
public K lowerKey(K key) {
//getLowerEntry gets the node that is only smaller than the key passed in
//keyOrNull Obtains the key of the node
return keyOrNull(getLowerEntry(key));
}
Copy the codeFloorEntry method
// Returns a node that is no less than or equal to the key passed in, wrapped as a new object
public Map.Entry<K,V> floorEntry(K key) {
//getFloorEntry returns a node that is only less than or equal to the incoming key
//exportEntry wraps a new object
return exportEntry(getFloorEntry(key));
}
Copy the codeFloorKey method
// Returns the key of the node that is only less than or equal to the key passed in
public K floorKey(K key) {
//getFloorEntry returns a node that is only less than or equal to the incoming key
//keyOrNull Obtains the key of the node
return keyOrNull(getFloorEntry(key));
}
Copy the codeCeilingEntry method
// Returns a node that is only greater than or equal to the key passed in, wrapped as a new object
public Map.Entry<K,V> ceilingEntry(K key) {
//getCeilingEntry returns a node that is only greater than or equal to the passed key
//exportEntry wraps a new object
return exportEntry(getCeilingEntry(key));
}
Copy the codeCeilingKey method
// Returns the key of the node that is only greater than or equal to the key passed in
public K ceilingKey(K key) {
//getCeilingEntry returns a node that is only greater than or equal to the passed key
//keyOrNull Obtains the key of the node
return keyOrNull(getCeilingEntry(key));
}
Copy the codeHigherEntry method
// Returns a node just larger than the key passed in, wrapped as a new object
public Map.Entry<K,V> higherEntry(K key) {
//getHigherEntry returns a node that is only larger than the passed key
//exportEntry wraps a new object
return exportEntry(getHigherEntry(key));
}
Copy the codeHigherKey method
// Returns the key of the node that is only larger than the key passed in
public K higherKey(K key) {
//getHigherEntry returns a node that is only larger than the passed key
//keyOrNull Obtains the key of the node
return keyOrNull(getHigherEntry(key));
}
Copy the codeKeySet method
// Get the Set of all keys
public Set<K> keySet(a) {
// Call navigableKeySet
return navigableKeySet();
}
Copy the codeNavigableKeySet method
// Return a Set of keys
public NavigableSet<K> navigableKeySet(a) {
// Use the cache first
KeySet<K> nks = navigableKeySet;
// If the cache is empty, recreate the KeySet object
// Note that KeySet is the inner class of TreeMap and can get all the properties of the TreeMap object
//KeySet is a subclass of NavigableSet that implements the NavigableSet interface
return(nks ! =null)? nks : (navigableKeySet =new KeySet<>(this));
}
Copy the codeDescendingKeySet method
/ / get descendingMap
public NavigableSet<K> descendingKeySet(a) {
return descendingMap().navigableKeySet();
}
Copy the codeDescendingMap method
/ / return descendingMap
public NavigableMap<K, V> descendingMap(a) {
NavigableMap<K, V> km = descendingMap;
// If the cache is empty, recreate the DescendingSubMap object
// Note that DescendingSubMap is the inner class of TreeMap and retrieves all the attributes of the TreeMap object
return(km ! =null)? km : (descendingMap =new DescendingSubMap<>(this.true.null.true.true.null.true));
}
Copy the codeValues method
// Get the Colletion collection of all values
public Collection<V> values(a) {
// Use cache
Collection<V> vs = values;
if (vs == null) {
// If the cache is empty, recreate the Values object
// Note that Values is the inner class of TreeMap and can get all the attributes of the TreeMap object
vs = new Values();
values = vs;
}
// Return the Colletion collection of value
return vs;
}
Copy the codeEntrySet method
// Get Entry objects for all key-value pairs
public Set<Map.Entry<K,V>> entrySet() {
// Use cache
EntrySet es = entrySet;
// If the cache is empty, re-create the EntrySet object
// Note that EntrySet is an inner class of TreeMap and can get all the properties of the TreeMap object
return(es ! =null)? es : (entrySet =new EntrySet());
}
Copy the codeThe replace method
@Override
// To change the value of the node, compare the old value
public boolean replace(K key, V oldValue, V newValue) {
// Get the node by getEntry
Entry<K,V> p = getEntry(key);
if(p! =null && Objects.equals(oldValue, p.value)) {
// If the node is not null and the value of the node is equal to the oldValue passed in
// Assign the new value to the node
p.value = newValue;
// Successful modification, return true
return true;
}
// Node does not exist, return false
return false;
}
@Override
// Change the value of the node without comparing the old value
public V replace(K key, V value) {
// Get the node by getEntry
Entry<K,V> p = getEntry(key);
if(p! =null) {
// If the node is not null
// Get the old value of the node
V oldValue = p.value;
// Assign the new value to the node
p.value = value;
// Return the old value
return oldValue;
}
// Node does not exist, return null
return null;
}
Copy the codeThe forEach method
@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
// Check the validity of the parameter
Objects.requireNonNull(action);
// Get a copy of the modified statistics
int expectedModCount = modCount;
// The BiConsumer method is called on each node
for(Entry<K, V> e = getFirstEntry(); e ! =null; e = successor(e)) {
action.accept(e.key, e.value);
// Throw an exception if some other thread changes during the traversal
if(expectedModCount ! = modCount) {throw newConcurrentModificationException(); }}}Copy the codeReplaceAll method
@Override
public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
// Check the validity of the parameter
Objects.requireNonNull(function);
// Get a copy of the modified statistics
int expectedModCount = modCount;
// The BiFunction method is called on each node
for(Entry<K, V> e = getFirstEntry(); e ! =null; e = successor(e)) {
e.value = function.apply(e.key, e.value);
// Throw an exception if some other thread changes during the traversal
if(expectedModCount ! = modCount) {throw newConcurrentModificationException(); }}}Copy the codeExportEntry method
// Wrap the Entry object into a new object, deep copy?
static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
return (e == null)?null :
new AbstractMap.SimpleImmutableEntry<>(e);
}
Copy the codePutAll method
// Add elements to the Map object
public void putAll(Map<? extends K, ? extends V> map) {
// Get the size of the map object passed in
int mapSize = map.size();
if (size==0&& mapSize! =0 && map instanceof SortedMap) {
// If map is SortedMap
// Get the map comparatorComparator<? > c = ((SortedMap<? ,? >)map).comparator();if(c == comparator || (c ! =null && c.equals(comparator))) {
// If the map comparator is equal to the current comparator
// Add 1 to the modified statistics
++modCount;
try {
// Use buildFromSorted to add elements
buildFromSorted(mapSize, map.entrySet().iterator(),
null.null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return; }}// If it is just a normal Map object, use the superclass method to add elements
super.putAll(map);
}
// The putAll method of the parent class
public void putAll(Map<? extends K, ? extends V> m) {
// Loop through the Map element to get the key-value pair and call the put method to add it
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
// Call the put method to add elements
put(e.getKey(), e.getValue());
}
Copy the codePut method
// Add key-value pair elements
public V put(K key, V value) {
// Get a copy of the root node
Entry<K,V> t = root;
if (t == null) {
// If root is null
// Type check and null check. If the current comparator is NULL, objects for key must implement the Comparable interface
compare(key, key); // type (and possibly null) check
// Create a new node based on the key and value, and use the new node as the root node
root = new Entry<>(key, value, null);
// Set the element count to 1
size = 1;
// Modify statistics by 1
modCount++;
/ / returns null
return null;
}
// The root node is not null
int cmp;
//parent Inserts the parent node of the node
Entry<K,V> parent;
// split comparator and comparable paths
// Get the current comparator
Comparator<? super K> cpr = comparator;
if(cpr ! =null) {
// If there is a comparator
// The while loop iterates through the search
do {
// Point parent to the current node
parent = t;
// The key of the current node and the key passed in
cmp = cpr.compare(key, t.key);
if (cmp < 0)
// If the key passed in is smaller than the key of the current node, look left
// Point the current node to the left child node
t = t.left;
else if (cmp > 0)
// If the key passed in is larger than the current node's key, look to the right
// Point the current node to the right child node
t = t.right;
else
// If found, replace the value of the current node with the value passed in
return t.setValue(value);
} while(t ! =null);
}
// No comparator exists, use key comparator
else {
if (key == null)
// If the passed key is empty, an exception is thrown
throw new NullPointerException();
/ / to turn the key
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
// The while loop iterates through the search
do {
// Point parent to the current node
parent = t;
// Use key's built-in comparator for comparison
cmp = k.compareTo(t.key);
if (cmp < 0)
// If the key passed in is smaller than the key of the current node, look left
// Point the current node to the left child node
t = t.left;
else if (cmp > 0)
// If the key passed in is larger than the current node's key, look to the right
// Point the current node to the right child node
t = t.right;
else
// If found, replace the value of the current node with the value passed in
return t.setValue(value);
} while(t ! =null);
}
// Create a new node with the last node traversed as its parent
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
// If the inserted key is smaller than the parent's key, the new node is the left child node
parent.left = e;
else
// If the inserted key is larger than the parent's key, the new node is the right child node
parent.right = e;
// Balance after insertion
fixAfterInsertion(e);
// The number of elements increases by 1
size++;
// Modify statistics by 1
modCount++;
/ / returns null
return null;
}
Copy the codeFixAfterInsertion method
// Balance the red-black tree after inserting the node
private void fixAfterInsertion(Entry<K,V> x) {
// Set the inserted node to red by default
x.color = RED;
//while loop operation
// If the current node is not empty, the current node is not the root node, and the parent of the current node is a red node, the loop will continue
Exit the loop until the parent node is black or reaches the root node
while(x ! =null&& x ! = root && x.parent.color == RED) {/ / * * * * * * * * * * * * * * * * if the parent node is grandfather left child node of the * * * * * * * * * * * * * * * * *
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
// Get the right node of the grandfather node, which is the right uncle node
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
// If the right uncle node is red
// Color the parent node black
setColor(parentOf(x), BLACK);
// Color the right uncle node black
setColor(y, BLACK);
// Color the grandfather node to red
setColor(parentOf(parentOf(x)), RED);
// Point the current node to the grandfather node for the next loop
x = parentOf(parentOf(x));
} else {
// If the right uncle node is black
if (x == rightOf(parentOf(x))) {
// If the current node is the right node of the parent node
// Point the current node to the parent node
x = parentOf(x);
// Rotate the node left based on the current node
rotateLeft(x);
}
// Color the parent node to black
setColor(parentOf(x), BLACK);
// Color the grandfather node into a red node
setColor(parentOf(parentOf(x)), RED);
// Based on the grandparent node, the node is right-handed
rotateRight(parentOf(parentOf(x)));
// Do the next loop
}
//*************************end************************
} else {
/ / = = = = = = = = = = = = = = = = = = = = if the parent node is grandfather node's right child node = = = = = = = = = = = = = = = = = = = = = = = = = = = =
// Get the left child of the grandfather node, i.e. the left uncle node
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
// If the left uncle node is red
// Color the parent node to black
setColor(parentOf(x), BLACK);
// color the left uncle node to black
setColor(y, BLACK);
// Color the grandfather node into a red node
setColor(parentOf(parentOf(x)), RED);
// Point the current node to the grandparent node for the next loop
x = parentOf(parentOf(x));
} else {
// If the left uncle node is black
if (x == leftOf(parentOf(x))) {
// If the current node is the left child node
// The current node points to the parent node
x = parentOf(x);
// Rotate the node right based on the current node
rotateRight(x);
}
// Color the parent node to black
setColor(parentOf(x), BLACK);
// Color the grandfather node into a red node
setColor(parentOf(parentOf(x)), RED);
// The node is left-handed based on the grandfather node
rotateLeft(parentOf(parentOf(x)));
// Do the next loop
}
//============================end=====================}}// Color the root node black
root.color = BLACK;
}
Copy the codeYou can see from above that staining => sinistral => dextral or staining => dextral => sinistral
-
The inserted node defaults to red, which minimizes changes
-
If the uncle node is a red node
- The parent node and the uncle node are dyed black, and the grandfather node is dyed red. Repeat the operation with the new node inserted as the grandfather node
-
If the uncle node is black
-
If the current node and the uncle node are both left child nodes
- Points the current node to the parent node
- The node is right-handed based on the current node
- Color the parent node black
- Color the grandfather node red
- Based on the grandfather node, several points are left handed
- And then the next cycle
-
If the current node is the right child, the uncle node is the left child
- Color the parent node black
- Color the grandfather node red
- Based on the grandfather node, several points are left handed
- And then the next cycle
-
If the current node and the uncle node are both right child nodes
- Points the current node to the parent node
- The current node is used as the base node for left-rotation
- Color the parent node black
- Color the grandfather node red
- Based on the grandfather node, several points are left handed
- And then the next cycle
-
If the current node is the left child, the uncle node is the right child
- Color the parent node black
- Color the grandfather node red
- Based on the grandfather node, several points are left handed
- And then the next cycle
-
RotateLeft method
/ / left
private void rotateLeft(Entry<K,V> p) {
if(p ! =null) {
// If the current node is not null
// Get the right child of the current node
Entry<K,V> r = p.right;
// Point the right child of the current node to the left child of the right child of the current node
p.right = r.left;
if(r.left ! =null)
// If the left child of the right child of the current node is not null
// Point the parent of the right child of the current node to the left child of the current node
r.left.parent = p;
// The parent of the current node's right child points to the parent of the current node
r.parent = p.parent;
if (p.parent == null)
// If the parent of the current node is null, the current node is the root node
// Point the root node to the right child of the current node
root = r;
else if (p.parent.left == p)
// If the current node is the left child of the parent node
// Point the left child of the parent node to the right child of the current node
p.parent.left = r;
else
// If the current node is the right child of the parent node
// Point the right child of the parent node to the right child of the current node
p.parent.right = r;
// The left child of the right node points to the current node
r.left = p;
// The parent of the current node points to the right child nodep.parent = r; }}Copy the codeAs you can see from the top, the essence of sinistral is
- The current node P becomes the left child of pr, the right child of the current node P
- The right child of the current node P becomes the left child PRL of the right child PR
RotateRight method
/ / right
private void rotateRight(Entry<K,V> p) {
if(p ! =null) {
// If the current node is not null
// Get the left child of the current node
Entry<K,V> l = p.left;
// The left child of the current node points to the right child of the current node's left child
p.left = l.right;
// If the right child of the left child of the current node is not null
// Point the parent of the left child of the current node to the current node
if(l.right ! =null) l.right.parent = p;
The parent of the left child of the current node points to the parent of the current node
l.parent = p.parent;
if (p.parent == null)
// If the parent of the current node is null, the current node is the root node
// Point the root node to the left child of the current node
root = l;
else if (p.parent.right == p)
// If the current node is the right child of the parent node
// Point the right child of the parent node to the left child of the current node
p.parent.right = l;
// If the current node is the left child of the parent node
// Point the left child of the parent node to the left child of the current node
else p.parent.left = l;
// The right node of the current node's left child points to the current node
l.right = p;
// The parent of the current node points to the left child of the current nodep.parent = l; }}Copy the codeAs you can see from the top, the essence of dextral rotation is
- The current node P becomes the right child of pl, the left child of current node P
- The left child of the current node P becomes the right child of the left child pl PLR
The remove method
// Remove the node corresponding to the key
public V remove(Object key) {
// Use getEntry to get the node corresponding to the key
Entry<K,V> p = getEntry(key);
if (p == null)
// If no corresponding node exists, null is returned
return null;
// Get the value of the corresponding node
V oldValue = p.value;
// Delete the node using deleteEntry
deleteEntry(p);
// Return the old value
return oldValue;
}
Copy the codeClear method
// Clear all elements
public void clear(a) {
// Modify statistics by 1
modCount++;
// Set the number of elements to 0
size = 0;
// Set the root node to null
root = null;
}
Copy the codeDeleteEntry method
// Delete a node
private void deleteEntry(Entry<K,V> p) {
// Modify statistics by 1
modCount++;
// The number of elements is reduced by 1
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
if(p.left ! =null&& p.right ! =null) {
// If both the left and right children of the p node exist
// Find elements only greater than p
Entry<K,V> s = successor(p);
// Set p key and value to S key and value
p.key = s.key;
p.value = s.value;
// point p to s
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
// Set the node to be replaced. If the left child exists, use the left child, but not the right childEntry<K,V> replacement = (p.left ! =null ? p.left : p.right);
if(replacement ! =null) {
// If p has child nodes
// Link replacement to parent
/ / * * * * * * * * * * * * * * * replacement parent node connected to the p * * * * * * * * * * * * * * * * * * * *
replacement.parent = p.parent;
if (p.parent == null)
// If the parent of p is null, p is the root node
// Set the root node to replacement
root = replacement;
else if (p == p.parent.left)
// If p is the left child of the parent
// Point the left child of the parent of the p node to replacement
p.parent.left = replacement;
else
// If p is the right child of the parent
// Point the right child of the parent of the p node to replacement
p.parent.right = replacement;
//***************end********************
// set all references to p to null
p.left = p.right = p.parent = null;
// Fix replacement
if (p.color == BLACK)
// If p is black
// call fixAfterDeletion to balance the red-black tree
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
// If the parent of p is null, p is the root node
// Set root to null
root = null;
} else { // No children. Use self as phantom replacement and unlink.
//p has no child node
if (p.color == BLACK)
// If p is black
// call fixAfterDeletion to balance the red-black tree
fixAfterDeletion(p);
if(p.parent ! =null) {
// If the parent of p is not null
if (p == p.parent.left)
// If p is the left child of the parent
// Set the left child of the parent node to null
p.parent.left = null;
else if (p == p.parent.right)
// If p is the right child of the parent
// Set the right child of the parent node to null
p.parent.right = null;
// set p's parent reference to null
p.parent = null; }}}Copy the codeFixAfterDeletion method
// Balance the red-black tree after deleting the node
private void fixAfterDeletion(Entry<K,V> x) {
// If x is not the root node and x is black, continue the while loop
while(x ! = root && colorOf(x) == BLACK) {if (x == leftOf(parentOf(x))) {
// If the current node is the left child of the parent node
// Get the right child of the parent node of the current node
Entry<K,V> sib = rightOf(parentOf(x));
if (colorOf(sib) == RED) {
// If the right sibling is red
// Color the right sibling node to black
setColor(sib, BLACK);
// Color the parent of the current node as a red node
setColor(parentOf(x), RED);
// The base node is left-handed based on the parent node
rotateLeft(parentOf(x));
// Reset the right sibling node
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
// If the children of the right sibling node are all black nodes
// Color the right sibling node to red
setColor(sib, RED);
// Point the current node to the parent node
x = parentOf(x);
// Do the next loop
} else {
// The child of the right sibling has a red node
if (colorOf(rightOf(sib)) == BLACK) {
// If the right child of the right sibling is black (the left child is red)
// Color the left child of the right sibling to black
setColor(leftOf(sib), BLACK);
// Color the right sibling node to red
setColor(sib, RED);
// Rotate the base node with the right sibling node as the base node
rotateRight(sib);
// Reset the right sibling node
sib = rightOf(parentOf(x));
}
// Dye the color of the right sibling to the color of the parent
setColor(sib, colorOf(parentOf(x)));
// Color the parent node to black
setColor(parentOf(x), BLACK);
// Color the right child of the right sibling to black
setColor(rightOf(sib), BLACK);
// The base node is left-handed based on the parent node
rotateLeft(parentOf(x));
// Exit the while loop by pointing to rootx = root; }}else { // Symmetric Is symmetric with the following
// If the current node is the right child of the parent node
// Get the left child of the parent node of the current node
Entry<K,V> sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
// If the left sibling is a red node
// Color the left sibling node to black
setColor(sib, BLACK);
// Color the parent node to red
setColor(parentOf(x), RED);
// Rotate the base node to the parent node
rotateRight(parentOf(x));
// Reset the left sibling node
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
// If the children of the left sibling are all black nodes
// Color the left sibling node to red
setColor(sib, RED);
// Point the current node to the parent node
x = parentOf(x);
// Do the next loop
} else {
// The child of the left sibling node has red nodes
if (colorOf(leftOf(sib)) == BLACK) {
// If the left child of the left sibling is black (and the right child is red)
// Color the right child of the left sibling node to black
setColor(rightOf(sib), BLACK);
// Color the left sibling node to red
setColor(sib, RED);
// Perform left-rotation based on the left sibling node
rotateLeft(sib);
// Reset the left sibling node
sib = leftOf(parentOf(x));
}
// Color the left sibling node to the parent node
setColor(sib, colorOf(parentOf(x)));
// Color the parent node to black
setColor(parentOf(x), BLACK);
// Color the left child of the left sibling node to black
setColor(leftOf(sib), BLACK);
// Rotate the parent node as the base node
rotateRight(parentOf(x));
Exit the while loop by pointing the current node to the root nodex = root; }}}// Color the current node X to black
setColor(x, BLACK);
}
Copy the codeSummary:
- The deletion balancing operation of red black trees is not well understood
- Staining, left-handedness, right-handedness is the key to balance
- The following data structure section will be illustrated in combination with the diagram, setting a flag first