Процедура удаления для бинарного дерева поиска

Question

Рассмотрим процедуру удаления на BST, когда у удаляемого узла есть два дочерних элемента. Допустим, я всегда заменяю его узлом, содержащим ключ минимума в правом поддереве.

Вопрос: эта процедура коммутативна? То есть удаление x, а затем y имеет тот же результат, что и удаление сначала y, а затем x?

Я думаю, что ответ - нет, но я не могу найти контрпример или найти какие-либо веские аргументы.

EDIT:

Может быть, я должен быть яснее.

Рассмотрим процедуру transplant(node x, node y): она заменяет x на y (и его поддерево). Итак, если я хочу удалить узел (скажем, x), у которого есть два потомка, я заменяю его узлом, содержащим минимальный ключ в его правом поддереве:

y = minimum(x.right)
transplant(y, y.right) // extracts the minimum (it doesn't have left child)
y.right = x.right
y.left = x.left
transplant(x,y)

Вопрос заключался в том, как доказать, что описанная выше процедура не является коммутативной.

Answer 1

Удаление (в общем) не является коммутативным.Вот контрпример:

    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.То есть вы заменяете значение узла и заменяете листовой узел.Таким образом, в общем случае, когда вы удаляете узел с двумя дочерними элементами, единственным структурным изменением является изменение значения удаляемого вами узла и удаление конечного узла, значение которого вы используете в качестве замены .

Итак, вопрос уточняется:

Можете ли вы гарантировать, что вы всегда получите один и тот же замещающий узел независимо от порядка удаления (когда вы всегда удаляете узел с двумя дочерними узлами)?

Ответ (я думаю) - да.Зачем?Вот несколько наблюдений:

• Допустим, вы сначала удалили узел-потомок, а затем узел-предок.Поддерево, которое было изменено при удалении узла-потомка, это , а не в левом поддереве правого потомка узла-предка.Это означает, что это поддерево остается неизменным.Это также означает, что независимо от порядка удаления два разных поддерева модифицируются, и поэтому операция является коммутативной.
• Опять, допустим, вы сначала удалили узел-потомок, а затем узел-предок. Поддерево, которое было изменено при удалении узла-потомка , равно в левом поддереве правого дочернего узла-предка. Но даже здесь нет совпадений. Причина в том, что когда вы сначала удаляете узел-потомок, вы смотрите на левое поддерево дочернего узла-потомка right . Когда вы затем удалите узел-предок, вы никогда не пойдете вниз по этому поддереву, так как вы будете всегда идти влево после того, как войдете в левый под-дочерний узел узла-предка дерево. Итак, опять же, независимо от того, что вы удаляете первым, вы изменяете разные поддеревья, и, следовательно, порядок не имеет значения.
• В другом случае вы сначала удаляете узел-предок и обнаруживаете, что минимальный узел является дочерним по отношению к узлу-потомку. Это означает, что у узла-потомка будет один дочерний узел, и удаление одного дочернего узла тривиально. Теперь рассмотрим случай, когда в этом сценарии вы сначала удалили узел-потомок. Затем вы должны заменить значение узла-потомка его правым потомком, а затем удалить правого потомка. Затем, когда вы удаляете узел-предок, вы в конечном итоге находите такой же минимальный узел (левый дочерний узел старого удаленного узла, который также является левым дочерним узлом замененного узла). В любом случае, вы в конечном итоге с той же структурой.

Это не строгое доказательство; это всего лишь некоторые наблюдения, которые я сделал. Во что бы то ни стало, не стесняйтесь тыкать отверстия!

Answer 2

Мне кажется, что контрпример, показанный в ответе Вивина, является единственным случаем некоммутативности, и что он действительно устраняется ограничением, что только узлы с двумя дочерними элементами могут быть удалены.

Но это также может быть устранено, если мы отбросим то, что кажется одной из предпосылок Вивина, то есть то, что мы должны пройти как можно меньше по правому поддереву, чтобы найти приемлемого преемника.Если вместо этого мы всегда выдвигаем наименьший узел в правом поддереве в качестве преемника, независимо от того, как далеко он окажется, то даже если мы ослабим ограничение на удаление узлов с менее чем двумя дочерними элементами, результат Вивина

    7
   /
  6

никогда не достигается, если мы начинаем с

    4
   / \
  3   7
     /
    6

Вместо этого мы сначала удалили 3 (без преемника), а затем удалили 4 (с 6 в качестве преемника), получив

    6
     \
      7

, что аналогично тому, как если бы порядок удаления был обратным.

Удаление тогда было бы коммутативным, и я думаю, что это всегда коммутативно, учитывая предпосылку, которую я назвал (преемник всегда самый маленький узелв правом поддереве удаленного узла).

У меня нет формального доказательства, просто перечисление случаев:

1. Если удаляются два узлав разных поддеревьях удаление одного не влияет на другое.Только когда они находятся на одном и том же пути, порядок удаления может повлиять на результат.

   Таким образом, любое влияние на коммутативность может возникнуть только тогда, когда узел предка и один из его потомков оба удалены.Теперь, как их вертикальное отношение влияет на коммутативность?

2. Потомок в левом поддереве предка. Эта ситуация не повлияет на коммутативность, потому что преемник происходит от справаподдерево и не может влиять на левое поддерево вообще.

3. Потомок в правом поддереве предка. Если преемник предка всегда является наименьшим узлом в правом поддереве, то порядок удаления не может изменить выборнаследник, независимо от того, какой потомок удаляется до или после предка.Даже если преемник предка оказывается узлом-потомком, который также должен быть удален, этот потомок также заменяется следующим по величине узлом, и у этого потомка не может быть своего собственного оставшегося поддерева, которое должно быть обработано.,Таким образом, удаление предка и любого потомка из правого поддерева всегда будет коммутативным.

Answer 3

Я думаю, что есть два одинаково жизнеспособных способа удаления узла, когда у него есть 2 дочерних элемента:
Пропустить на случай 4 ...

Случай 1: Удалить 3 (конечный узел)
2 3
/ \ -> / \
1 3 1

Случай 2: удалить 2 (левый дочерний узел)
2 3
/ \ -> / \
1 3 1

Случай 3: удалить 2 (правый дочерний узел)
2 2
/ \ -> / \
1 3 3

______________________________________________________________________
Случай 4: удалить 2 (левый и правый дочерние узлы)
2 2 3
/ \ -> / \ или / \
1 3 1 3
ОБА РАБОТАЮТ и получаются разные деревья :): ______________________________________________________________________
Как объяснил алгоритм здесь: http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Trees/AVL-delete.html Deleting a node with 2 children nodes: 1) Replace the (to-delete) node with its in-order predecessor or in-order successor 2) Then delete the in-order predecessor or in-order successor

Answer 4

Я отвечаю здесь на второе обновление Вивина.

Я думаю, что это хороший пересмотр вопроса:

Является ли удаление коммутативным, если вы рассматриваете удаление двух узлов избинарное дерево поиска, которое имеет отношение предок-потомок друг к другу (это будет означать, что они находятся в одном и том же поддереве)?

, но приведенное ниже смелое предложение неверно:

Когда вы удаляете узел (скажем, A), вы пересекаете правое поддерево, чтобы найти минимальный элемент. Этот узел будет конечным узлом и никогда не может быть равен B

, поскольку минимальный элемент в правом поддереве A может иметь правый дочерний элемент .Так что это не лист.Назовем минимальный элемент в правом поддереве А successor(A).Теперь верно, что B не может быть successor(A), но может находиться в своем правом поддереве.Итак, это беспорядок.

Я пытаюсь подвести итог.

Гипотеза :

1. А и В имеют по два ребенка в каждом.
2. A и B. находятся в одном и том же поддереве.

Другие вещи мы можем вывести из гипотезы:

1. B не successor(A), ни A не является successor(B).

Теперь, учитывая, что, я думаю, есть 4 разных случая (как обычно, пусть A является предком B):

1. B находится в левом поддереве A
2. B является предком successor(A)
3. successor(A) является предком B
4. B и преемником (A) donнет никаких отношений.(они находятся в разных поддеревьях А)

Я думаю (но, конечно, я не могу это доказать), что случаи 1, 2 и 4 не имеют значения.Итак, только в случае successor(A) предок B процедура удаления не может быть коммутативной.Или это могло быть?

Я передаю мяч:)

С уважением.