2–4 trees, for any sequence of operations. The 2–4 tree isometry was described in 1978 by Sedgewick. With 2–4 trees, the isometry is resolved by a "color flip," corresponding to a split, in which the red color of two children nodes leaves the children and moves to the parent node. The original description of the tango tree, a type of tree optimised for fast searches, specifically uses red–black trees as part of its data structure. As of Java 8, the HashMap has been modified such that instead of using a LinkedList to store different elements with colliding hashcodes, a red–black tree is used. This results in the improvement of time complexity of searching such an element from to where is the number of elements with colliding hashcodes. Operations The read-only operations, such as search or tree traversal, on a red–black tree require no modification from those used for binary search trees, because every red–black tree is a special case of a simple binary search tree. However, the immediate result of an insertion or removal may violate the properties of a red–black tree, the restoration of which is called rebalancing so that red–black trees become self-balancing. It requires in the worst case a small number, in Big O notation, where is the number of objects in the tree, on average or amortized , a constant number, of color changes (which are very quick in practice); and no more than three tree rotations (two for insertion). If the example implementation below is not suitable, other implementations with explanations may be found in Ben Pfaff’s annotated C library GNU libavl (v2.0.3 as of June 2019). The details of the insert and removal operations will be demonstrated with example C++ code, which uses the type definitions, macros below, and the helper function for rotations: // Basic type definitions: enum color_t { BLACK, RED }; struct RBnode { // node of red–black tree RBnode* parent; // == NIL if root of the tree RBnode* child[2]; // == NIL if child is empty // The index is: // LEFT := 0, if (key < parent->key) // RIGHT := 1, if (key > parent->key) enum color_t color; int key; }; #define NIL NULL // null pointer or pointer to sentinel node #define LEFT 0 #define RIGHT 1 #define left child[LEFT] #define right child[RIGHT] struct RBtree { // red–black tree RBnode* root; // == NIL if tree is