Location>code7788 >text

TreeMap source code - thoroughly understand the red-black tree balancing operations

Popularity:863 ℃/2024-09-11 21:04:23

present (sb for a job etc)

TreeSetcap (a poem)TreeMaphas the same implementation in Java, the former is simply a wrapper around the latter, i.e., theThere is a TreeMap inside a TreeSet.(adapter mode).

Java TreeMapRealizedSortedMapinterface, i.e., the keys will be pairs in the order of their size.MapThe size of the key can be judged either by its own natural ordering or by a comparator passed in at construction time.

TreeMap bottom through the red-black tree (Red-Black tree) to achieveThis means that containsKey(), get(), put(), remove() all have log(n) time complexity.

  1. When TreeMap stores Key-Value pairs, it needs to be sorted according to the key-value pairs.TreeMap can guarantee that all Key-Value pairs are in an ordered state.

    • Under normal circumstances a TreeMap cannot store a key with a null value.

    • However, a custom comparator enables the TreeMap to deposit a key with a value of null.

    • Values stored for null keys cannot be retrieved through it, but only by traversing the Values directly.

  2. The underlying TreeSet uses a red-black tree structure to store data.

  3. The ordering of the Key of the TreeMap:

    • Natural sorting: all the keys of the TreeMap must implement the Comparable interface, and all the keys should be objects of the same class, otherwise a ClasssCastException will be thrown.

    • Customized sorting: When creating a TreeMap, pass in a Comparator object, which is responsible for sorting all the keys in the TreeMap. There is no need for the Map's key to implement the Comparable interface.

  4. TreeMap judge two keys equal to the standard: two keys through the compareTo () method or compare () method returns 0.

underlying implementation

Key methods for inheriting interfaces

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, 

Returns the comparator used to sort the keys in this mapping, or null if this mapping uses the natural ordering of its keys.

SortedMap interface:

Comparator<? super K> comparator()
Returns the comparator used to sort the keys in this mapping, or null if this mapping uses the natural ordering of its keys.

Set<<K,V>> entrySet()
Returns a Set view of the mappings contained in this mapping.

K firstKey()
Returns the first (lowest) key in the current mapping.

K lastKey()
Returns the last (highest) key in the current mapping.

NavigableMap interface:

<K,V> ceilingEntry(K key)
Returns the key-value map associated with the smallest key greater than or equal to the given key, or null if there is no such key.

K ceilingKey(K key)
Returns the smallest key greater than or equal to the given key, or null if there is no such key.

NavigableMap<K,V> descendingMap()
Returns a descending view of the mappings contained in this map.

<K,V> firstEntry()
Returns the key-value mapping associated with the smallest key in this mapping, or null if the mapping is empty.

<K,V> floorEntry(K key)
Returns the key-value mapping associated with the largest key less than or equal to the given key, or null if there is no such key.

SortedMap<K,V> headMap(K toKey)
Returns a view of the portion of this map whose keys are strictly less than toKey.

<K,V> higherEntry(K key)
Returns the key-value map associated with the smallest key strictly greater than the given key, or null if there is no such key.

<K,V> lastEntry()
Returns the key-value mapping associated with the largest key in this mapping, or null if the mapping is empty.

<K,V> lowerEntry(K key)
Returns the key-value mapping associated with the largest key strictly less than the given key, or null if there is no such key.

<K,V> pollFirstEntry()
Removes and returns the key-value mapping associated with the smallest key in the mapping, or null if the mapping is empty.

<K,V> pollLastEntry()
Removes and returns the key-value mapping associated with the largest key in this mapping, or null if the mapping is empty.

SortedMap<K,V> subMap(K fromKey, K toKey)
Returns a view of the portion of this mapping whose keys range from fromKey (contained) to toKey (exclusive).

SortedMap<K,V> tailMap(K fromKey)
Returns a view of the portion of this map with keys greater than or equal to fromKey.

Initial Properties

//comparator
private final Comparator<? super K> comparator;

//rootValue of the root
private transient Entry<K,V> root;

//mapmedium data volume
private transient int size = 0;

//Number of revisions
private transient int modCount = 0;

constructor method

public TreeMap() {
    public TreeMap() { comparator = null; }
}

// Parametric construction, can redefine the comparator
public TreeMap(Comparator<? super K> comparator) {
     = comparator; }
}

//Parametric construction, the other map with TreeMap storage
public TreeMap(Map< ? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}

put method

public V put(K key, V value) {
    // Assign root to a local variable.
    Entry<K,V> t = root.
    if (t == null) {// initial operation
        // check if key is null
        compare(key, key); // type (and possibly null) check
        // Encapsulate the key value to be added into an entry object and assign it to root
        root = new Entry<>(key, value, null); // size = 1; // if the key is null, assign it to root; // if the value is null, assign it to root.
        size = 1; modCount++;
        modCount++; return null; return null
        return null; }
    }
    int cmp; int cmp; Entry<K,V> parent
    Entry<K,V> parent;// parent node
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;// get comparator
    if (cpr ! = null) {
        do {
            parent = t;//assign root to parent
            cmp = (key, );//compare size with root node
            if (cmp < 0)//key is smaller than root, t makes it the left node
                t = ;
            else if (cmp > 0)//otherwise make it right node
                t = ;
            t = ; else
                return (value);// equal size, change value directly
        } while (t ! = null); }
    }
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = (); if (cmp < 0)
            if (cmp < 0)
                key; do { parent = t; cmp = (); if (cmp < 0)
            else if (cmp > 0)
                t = ;
            t = ; else
                return (value); } while (t !
        } while (t ! = null); }
    }
    // Here t is the parent of the node to be inserted.
    // Encapsulate the k v pair into an entry object.
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
         = e;// insert node to the left of parent
    if (cmp < 0) = e;//insert node to the left of parent
         = e;//Insert node to the right of the parent.
    fixAfterInsertion(e);//balance the red-black tree
    size++; modCount++;
    modCount++.
    return null; }
}

The balance of the red and black trees will be described later on

red and black trees

The nature of the red-black tree

  • Each node is either black or red.

  • The root node is black.

  • Each leaf node (NIL) is black.

  • Both children of each red node must be black.

  • The path from any node (containing itself) to its leaf nodes contains the same number of black nodes.

Advantages of red and black trees:

Due to the AVL tree, due to the AVL tree is absolutely balanced, all in the insertion and deletion, in order to maintain its absolute balance, sometimes the operation of modifying the node, you need to carry out to the root node, the number of rotations is more, so the emergence of the red-black tree, when the data is not static data but dynamic data, insertion and deletion do not have to go to the maintenance of the absolute balance, which also Reduced the number of rotations, as usual, can improve efficiency, and the average search efficiency of the red-black tree or logn

Red-black tree equilibrium source code

The initial color of the inserted red-black tree must be red, note that.The insertion node must be redThe reason is simple, red in the parent node (if exists) is a black node, red-black tree black balance is not destroyed, do not need to do self-balancing operation. However, if the insertion node is black, the black node of the subtree where the insertion position is located is always 1 more, and must do self-balancing.

You can start by looking at the TreeMap red-black tree balancing source code, or you can start by looking at the post-scenario

private void fixAfterInsertion(Entry<K,V> x) {
     = RED;// Insertion by first setting the color to red
    //The loop condition is that x is not equal to null, x is not the root, and the parent node is red.
    //The reason is that (i) if x is the root, it can be directly set to black (corresponding to scenario 1); (ii) if the parent node is black, x is directly inserted in red, which does not affect the balance condition (corresponding to scenario 3)
    while (x ! = null && x ! = root && == RED) {
        // determine if the parent node is the left node of the grandfather node
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            // Get the right node of the grandfather node, which is the uncle node S
            Entry<K,V> y = rightOf(parentOf(parentOf(x))));
            // if uncle node is red (corresponding to scenario 4.1)
            if (colorOf(y) == RED) {
                //1. set P and S to black 2. set PP to red 3. set PP to the current insertion node then execute the rule
                setColor(parentOf(x), BLACK).
                setColor(parentOf(x), BLACK); setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED)
                x = parentOf(parentOf(x));
            } else {// Uncle node does not exist (corresponds to scenario 4.2)
              // if x is the right node of the parent (corresponding to scenario 4.2.2)
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);// use x's parent P as the insertion node
                    rotateLeft(x);//rotate left
                } //After rotateLeft, the insertion node x is the left node of P.
                //If x is the left node of the parent node; then do only one right rotation (corresponding to scenario 4.2.1)
                setColor(parentOf(x), BLACK);//set P to black
                setColor(parentOf(parentOf(x)), RED);//set PP to red color
                rotateRight(parentOf(parentOf(x)));//rotate right
            }
        } else {// Parent is the right node of the grandfather node
            // Get the left node of the grandfather node, which is the uncle node S
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {// (corresponds to scenario 4.1)
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED)
                x = parentOf(parentOf(x));
            } else {// (corresponding to scenario 4.3)
                if (x == leftOf(parentOf(x))) {// (corresponds to scenario 4.3.2)
                    x = parentOf(x);
                    rotateRight(x);
                }
                //(corresponding to scenario 4.3.1)
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    // The color of the root node is black
     = BLACK.
}

Left rotation: a node as a pivot point (rotation node), its right child node becomes the parent node of the rotation node, the left child node of the right child node becomes the right child node of the rotation node, and the left child node of the rotation node remains unchanged. The left child of the right child node is "disconnected" from the right child node and reconnected to the rotating node.

//levitra
private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        //
        Entry<K,V> r = ;
         = ;
        if ( != null)
             = p;
         = ;
        if ( == null)
            root = r;
        else if ( == p)
             = r;
        else
             = r;
         = p;
         = r;
    }
}

Right rotation: a node as the fulcrum (rotation node), its left child node becomes the parent of the rotation node, the right child of the left child node becomes the left child of the rotation node, the right child of the rotation node remains unchanged. The right child of the left child node is "disconnected" from the left child node and reconnected to the rotating node.

private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> l = ;
         = ;
        if ( != null)  = p;
         = ;
        if ( == null)
            root = l;
        else if ( == p)
             = l;
        else  = l;
         = p;
         = l;
    }
}

The operations inserted in the following scenarios are reproduced in:/p/e136ec79235c

Scenario 1: Red and black trees are empty

For the simplest scenario, just use the insertion node as the root node directly, but note that according to the red-black tree property 2: the root node is black. You also need to set the insertion node to black.

Processing: Use the insertion node as the root node and set the node to black.

Scenario 2: The Key of the inserted node already exists

The Key of the insertion node already exists, and since the red-black tree is always balanced, and the red-black tree was already balanced before the insertion, the insertion node is set to the color of the node it will replace, and then the value of the node is updated to complete the insertion (here, the update is actually the value of the same key).

Processing:

  • Set I to the color of the current node

  • Update the value of the current node to the value of the inserted node

Scenario 3: The parent of the insertion node is the black node

Since the inserted node is red, when the black of the inserted node is inserted, it does not affect the balance of the red-black tree, and can be inserted directly without doing self-balancing.

Processing: Direct insertion.

Scenario 4: The parent of the inserted node is a red node

Recall again Property 2 of the red-black tree: the root node is black. If the inserted parent node is red, then that parent node cannot be the root node, so there is always a grandfather node at the inserted node. This is important because subsequent rotations will definitely require the involvement of the grandfather node.

Scenario 4.1: Uncle node exists and is a red node

From the red-black tree property 4 can be, the grandfather node must be a black node, because there can not be two connected red nodes at the same time. Then at this time the insertion of the subtree of the number of red and black layers of the case is: black red red. Obviously the simplest way to deal with it is to change it to: red black red.

(In the following description I is the insertion node, P is the parent node, PP is the grandfather node and S is the uncle node)

Processing:

  • Set P and S to black

  • Set PP to red

  • Set PP as the current insertion node

The PP node is set to red, if PP's parent node is black, then there is no need to do any processing; but if PP's parent node is red, according to property 4 (each red node's two children must be black.), then the red-black tree is no longer balanced. At this point, the red-black tree is no longer balanced, so it is also necessary to treat PP as a new insertion node and continue to do the insertion operation to self-balance the processing until it is balanced.

Imagine when PP happens to be the root node, then according to property 2, PP must be reset to black, then the red-black structure of the tree becomes: black-black-red. In other words, the black node is increased in the path from the root node to the leaf nodes. This is the only insertion scenario that will increase the number of layers of black nodes in a red-black tree.

There is another lesson we can draw: red-black trees grow from the bottom up. This is different from ordinary binary lookup trees, which grow top-down.

Scenario 4.2: The uncle node does not exist and the insertion node's father node is the left child of the grandfather node

Looking purely at the insertion front, i.e., not counting the case when scenario 4.1 is processed bottom-up, the uncle node non-red is a leaf node (Nil).

We have not considered the case where the uncle node is a black node because if the uncle node is black and the parent is red, then the subtree in which the uncle node is located has more black nodes than the subtree in which the parent is located, which does not satisfy property 5 of red-black trees.5 The same is true of the subsequent scenarios, which will not be explained further.

Scenario 4.2.1: The insertion node is the left child of its parent node

Processing:

  • Set P to black

  • Set PP to red

  • Right-rotation of PP

With two red nodes on the left and none on the right, then one on one side is just right, and because it's red, it certainly doesn't upset the balance of the tree.

Scenario 4.2.2: The insertion node is the right child of its parent node

This scenario can obviously be translated into scenario 4.2.1

Processing:

  • A left-handed rotation of P

  • Setting P as the insertion node gives scenario 4.2.1

  • Carrying out scenario 4.2.1

Scenario 4.3: The uncle node does not exist and the father node of the insertion node is the right child of the grandfather node

This scenario corresponds to scenario 4.2, except that the direction is reversed.

Scenario 4.3.1: The insertion node is the right child of its parent node

Processing:

  • Set P to black

  • Set PP to red

  • Left-rotation on PP

Scenario 4.3.2: The insertion node is the left child of its parent node

Processing:

  • A right-handed rotation of P

  • Setting P as the insertion node gives scenario 4.3.1

  • Carrying out scenario 4.3.1

About the Author.

From the first-line programmer Seven's exploration and practice, continuous learning iteration in the~

This article is included in my personal blog:https://

Public number: seven97, welcome to follow~