Удаление (вообще) не коммутативно. Вот контрпример:
4
/ \
3 7
/
6
Что, если мы удалим 4, а затем 3?
Когда мы удаляем 4, мы получаем 6 в качестве нового корня:
6
/ \
3 7
Удаление 3 не меняет дерево, но дает нам следующее:
6
\
7
Что, если мы удалим 3, а затем 4?
Когда мы удаляем 3, дерево не меняется:
4
\
7
/
6
Однако, когда мы теперь удаляем 4, новый корень становится 7:
7
/
6
Два получившихся дерева не совпадают, поэтому удаление не является коммутативным.
ОБНОВЛЕНИЕ
Я не читал ограничение, что это когда вы всегда удаляете узел с 2 дочерними элементами. Мое решение для общего случая. Я обновлю его, если/когда найду контрпример.
ДРУГОЕ ОБНОВЛЕНИЕ
У меня нет конкретных доказательств, но я рискну предположить:
В общем случае вы обрабатываете удаление по-разному в зависимости от того, есть ли у вас двое детей, один ребенок или нет детей. В приведенном мной контрпримере я сначала удаляю узел с двумя дочерними элементами, а затем узел с одним дочерним элементом. После этого я удаляю узел без дочерних элементов, а затем другой узел с одним дочерним элементом.
В частном случае удаления только узлов с двумя потомками вы хотите рассмотреть случай, когда оба узла находятся в одном и том же поддереве (поскольку не имеет значения, находятся ли они в разных поддеревьях; вы можете быть уверены, что общая структура не изменится в зависимости от порядка удаления). Что вам действительно нужно доказать, так это то, имеет ли значение порядок удаления узлов в одном и том же поддереве, где каждый узел имеет двух дочерних элементов.
Рассмотрим два узла A и B, где A является предком B. Затем вы можете дополнительно уточнить вопрос:
Является ли удаление коммутативным, когда вы рассматриваете удаление двух узлов из двоичного дерева поиска, которые имеют отношение предок-потомок друг к другу (это будет означать, что они находятся в одном и том же поддереве)?
Когда вы удаляете узел (скажем, A), вы проходите по правому поддереву, чтобы найти минимальный элемент. Этот узел будет конечным узлом и никогда не может быть равен B (поскольку B имеет двух дочерних узлов и не может быть конечным узлом). Затем вы замените значение A значением этого листового узла. Это означает, что единственным структурным изменением дерева является замена значения A значением конечного узла и потеря конечного узла.
Тот же процесс используется для B. То есть вы заменяете значение узла и заменяете конечный узел. В целом, когда вы удаляете узел с двумя дочерними элементами, единственное структурное изменение — это изменение значения удаляемого узла и удаление конечного узла, значение которого вы используете в качестве замены .
Итак, вопрос уточняется:
Можете ли вы гарантировать, что вы всегда будете получать один и тот же заменяющий узел независимо от порядка удаления (когда вы всегда удаляете узел с двумя дочерними элементами)?
Ответ (я думаю) да. Почему? Вот несколько наблюдений:
- Допустим, вы сначала удаляете узел-потомок, а затем — узел-предок. Поддерево, которое было изменено при удалении узла-потомка, нет в левом поддереве правого дочернего узла-предка. Это означает, что это поддерево остается незатронутым. Это также означает, что независимо от порядка удаления изменяются два разных поддерева, и поэтому операция является коммутативной.
- Опять же, предположим, что вы сначала удаляете узел-потомок, а затем — узел-предок. Поддерево, которое было изменено при удалении узла-потомка , находится в левом поддереве правого дочернего узла-предка. Но даже здесь нет совпадений. Причина в том, что когда вы сначала удаляете узел-потомок, вы просматриваете левое поддерево правого потомка узла-потомка. Когда вы затем удалите родительский узел, вы никогда не спуститесь вниз по этому поддереву, поскольку вы будете всегда двигаться влево после того, как вы войдете в правую часть родительского узла. поддерево. Итак, опять же, независимо от того, что вы удаляете первым, вы изменяете разные поддеревья, и поэтому кажется, что порядок не имеет значения.
- Другой случай — если вы сначала удалите узел-предок и обнаружите, что минимальный узел является дочерним по отношению к узлу-потомку. Это означает, что узел-потомок будет иметь один дочерний узел, и удаление одного дочернего узла является тривиальным. Теперь рассмотрим случай, когда в этом сценарии вы сначала удалили дочерний узел. Затем вы замените значение узла-потомка его правым дочерним элементом, а затем удалите правильный дочерний элемент. Затем, когда вы удаляете узел-предок, вы в конечном итоге находите такой же минимальный узел (левый дочерний элемент старого удаленного узла, который также является левым дочерним элементом замененного узла). В любом случае вы получите одну и ту же структуру.
Это не строгое доказательство; это всего лишь некоторые наблюдения, которые я сделал. В любом случае, не стесняйтесь протыкать дыры!
person
Vivin Paliath
schedule
07.06.2010
