Insertion and deletion methods from java.util.TreeMap 528 public V put(K key, V value) { 529 Entry t = root; 530 if (t == null) { 531 compare(key, key); // type (and possibly null) check 532 533 root = new Entry<>(key, value, null); 534 size = 1; 535 modCount++; 536 return null; 537 } 538 int cmp; 539 Entry parent; 540 // split comparator and comparable paths 541 Comparator cpr = comparator; 542 if (cpr != null) { 543 do { 544 parent = t; 545 cmp = cpr.compare(key, t.key); 546 if (cmp < 0) 547 t = t.left; 548 else if (cmp > 0) 549 t = t.right; 550 else 551 return t.setValue(value); 552 } while (t != null); 553 } 554 else { 555 if (key == null) 556 throw new NullPointerException(); 557 Comparable k = (Comparable) key; 558 do { 559 parent = t; 560 cmp = k.compareTo(t.key); 561 if (cmp < 0) 562 t = t.left; 563 else if (cmp > 0) 564 t = t.right; 565 else 566 return t.setValue(value); 567 } while (t != null); 568 } 569 Entry e = new Entry<>(key, value, parent); 570 if (cmp < 0) 571 parent.left = e; 572 else 573 parent.right = e; 574 fixAfterInsertion(e); 575 size++; 576 modCount++; 577 return null; 578 } 2035 private static boolean colorOf(Entry p) { 2036 return (p == null ? BLACK : p.color); 2037 } 2038 2039 private static Entry parentOf(Entry p) { 2040 return (p == null ? null: p.parent); 2041 } 2042 2043 private static void setColor(Entry p, boolean c) { 2044 if (p != null) 2045 p.color = c; 2046 } 2047 2048 private static Entry leftOf(Entry p) { 2049 return (p == null) ? null: p.left; 2050 } 2051 2052 private static Entry rightOf(Entry p) { 2053 return (p == null) ? null: p.right; 2054 } 2055 2056 /** From CLR */ 2057 private void rotateLeft(Entry p) { 2058 if (p != null) { 2059 Entry r = p.right; 2060 p.right = r.left; 2061 if (r.left != null) 2062 r.left.parent = p; 2063 r.parent = p.parent; 2064 if (p.parent == null) 2065 root = r; 2066 else if (p.parent.left == p) 2067 p.parent.left = r; 2068 else 2069 p.parent.right = r; 2070 r.left = p; 2071 p.parent = r; 2072 } 2073 } 2074 2075 /** From CLR */ 2076 private void rotateRight(Entry p) { 2077 if (p != null) { 2078 Entry l = p.left; 2079 p.left = l.right; 2080 if (l.right != null) l.right.parent = p; 2081 l.parent = p.parent; 2082 if (p.parent == null) 2083 root = l; 2084 else if (p.parent.right == p) 2085 p.parent.right = l; 2086 else p.parent.left = l; 2087 l.right = p; 2088 p.parent = l; 2089 } 2090 } 2091 2092 /** From CLR */ 2093 private void fixAfterInsertion(Entry x) { 2094 x.color = RED; 2095 2096 while (x != null && x != root && x.parent.color == RED) { 2097 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { 2098 Entry y = rightOf(parentOf(parentOf(x))); 2099 if (colorOf(y) == RED) { 2100 setColor(parentOf(x), BLACK); 2101 setColor(y, BLACK); 2102 setColor(parentOf(parentOf(x)), RED); 2103 x = parentOf(parentOf(x)); 2104 } else { 2105 if (x == rightOf(parentOf(x))) { 2106 x = parentOf(x); 2107 rotateLeft(x); 2108 } 2109 setColor(parentOf(x), BLACK); 2110 setColor(parentOf(parentOf(x)), RED); 2111 rotateRight(parentOf(parentOf(x))); 2112 } 2113 } else { 2114 Entry y = leftOf(parentOf(parentOf(x))); 2115 if (colorOf(y) == RED) { 2116 setColor(parentOf(x), BLACK); 2117 setColor(y, BLACK); 2118 setColor(parentOf(parentOf(x)), RED); 2119 x = parentOf(parentOf(x)); 2120 } else { 2121 if (x == leftOf(parentOf(x))) { 2122 x = parentOf(x); 2123 rotateRight(x); 2124 } 2125 setColor(parentOf(x), BLACK); 2126 setColor(parentOf(parentOf(x)), RED); 2127 rotateLeft(parentOf(parentOf(x))); 2128 } 2129 } 2130 } 2131 root.color = BLACK; 2132 } 2133 2134 /** 2135 * Delete node p, and then rebalance the tree. 2136 */ 2137 private void deleteEntry(Entry p) { 2138 modCount++; 2139 size--; 2140 2141 // If strictly internal, copy successor's element to p and then make p 2142 // point to successor. 2143 if (p.left != null && p.right != null) { 2144 Entry s = successor(p); 2145 p.key = s.key; 2146 p.value = s.value; 2147 p = s; 2148 } // p has 2 children 2149 2150 // Start fixup at replacement node, if it exists. 2151 Entry replacement = (p.left != null ? p.left : p.right); 2152 2153 if (replacement != null) { 2154 // Link replacement to parent 2155 replacement.parent = p.parent; 2156 if (p.parent == null) 2157 root = replacement; 2158 else if (p == p.parent.left) 2159 p.parent.left = replacement; 2160 else 2161 p.parent.right = replacement; 2162 2163 // Null out links so they are OK to use by fixAfterDeletion. 2164 p.left = p.right = p.parent = null; 2165 2166 // Fix replacement 2167 if (p.color == BLACK) 2168 fixAfterDeletion(replacement); 2169 } else if (p.parent == null) { // return if we are the only node. 2170 root = null; 2171 } else { // No children. Use self as phantom replacement and unlink. 2172 if (p.color == BLACK) 2173 fixAfterDeletion(p); 2174 2175 if (p.parent != null) { 2176 if (p == p.parent.left) 2177 p.parent.left = null; 2178 else if (p == p.parent.right) 2179 p.parent.right = null; 2180 p.parent = null; 2181 } 2182 } 2183 } 2184 2185 /** From CLR */ 2186 private void fixAfterDeletion(Entry x) { 2187 while (x != root && colorOf(x) == BLACK) { 2188 if (x == leftOf(parentOf(x))) { 2189 Entry sib = rightOf(parentOf(x)); 2190 2191 if (colorOf(sib) == RED) { 2192 setColor(sib, BLACK); 2193 setColor(parentOf(x), RED); 2194 rotateLeft(parentOf(x)); 2195 sib = rightOf(parentOf(x)); 2196 } 2197 2198 if (colorOf(leftOf(sib)) == BLACK && 2199 colorOf(rightOf(sib)) == BLACK) { 2200 setColor(sib, RED); 2201 x = parentOf(x); 2202 } else { 2203 if (colorOf(rightOf(sib)) == BLACK) { 2204 setColor(leftOf(sib), BLACK); 2205 setColor(sib, RED); 2206 rotateRight(sib); 2207 sib = rightOf(parentOf(x)); 2208 } 2209 setColor(sib, colorOf(parentOf(x))); 2210 setColor(parentOf(x), BLACK); 2211 setColor(rightOf(sib), BLACK); 2212 rotateLeft(parentOf(x)); 2213 x = root; 2214 } 2215 } else { // symmetric 2216 Entry sib = leftOf(parentOf(x)); 2217 2218 if (colorOf(sib) == RED) { 2219 setColor(sib, BLACK); 2220 setColor(parentOf(x), RED); 2221 rotateRight(parentOf(x)); 2222 sib = leftOf(parentOf(x)); 2223 } 2224 2225 if (colorOf(rightOf(sib)) == BLACK && 2226 colorOf(leftOf(sib)) == BLACK) { 2227 setColor(sib, RED); 2228 x = parentOf(x); 2229 } else { 2230 if (colorOf(leftOf(sib)) == BLACK) { 2231 setColor(rightOf(sib), BLACK); 2232 setColor(sib, RED); 2233 rotateLeft(sib); 2234 sib = leftOf(parentOf(x)); 2235 } 2236 setColor(sib, colorOf(parentOf(x))); 2237 setColor(parentOf(x), BLACK); 2238 setColor(leftOf(sib), BLACK); 2239 rotateRight(parentOf(x)); 2240 x = root; 2241 } 2242 } 2243 } 2244 2245 setColor(x, BLACK); 2246 }