TreeMap, private void deleteEntry(Entry p) случай с заметой
сперва посмотрите на этот кусок кода
// Fix replacement
if (p.color == BLACK)
fixAfterDeletion(replacement);
ниже полный код метода
/**
* Delete node p, and then rebalance the tree.
*/
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 (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// Link replacement to parent
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
// Null out links so they are OK to use by fixAfterDeletion.
p.left = p.right = p.parent = null;
// Fix replacement
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else { // No children. Use self as phantom replacement and unlink.
if (p.color == BLACK)
fixAfterDeletion(p);
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;
}
}
}
вопрос: зачем нам делать проверку так, как показано в первом блоке кода, если перед этим мы делаем проверку:
if (replacement != null) {
и, следовательно, если замена != null, то единственный возможный случай - это то, что «p» точно черный с одной красной заменой.
и потом мы просто меняем цвет замены на черный в методе:
fixAfterDeletion(replacement);
я могу понять почему мы делаем это в отдельном методе, имею ввиду
fixAfterDeletion(replacement);
допустим что бы сгруппировать код в одном месте, в итоге будет вызнана одна строчка кода
setColor(x, BLACK);
но все же не могу понять случай с заменой, и проверкой, зачем она нужна?
Ответы (1 шт):
Я получил ответ на англоязычном сообществе как оказалось проверка совсем не нужна, и скорее всего она несет в себе характер оповещения о том что мы удаляем черную ноду и будем делать ребалансировку дерева, кому интересно вот сылка на вопрос с ответом на английском - https://stackoverflow.com/questions/78253926/treemap-private-void-deleteentryentryk-v-p-replacement-case