Рубрики

Структуры данных | Двоичные поисковые деревья | вопрос 2

В операции удаления BST нам нужен преемник (или предшественник) узла, когда удаляемый узел имеет левый и правый дочерние элементы как непустые. Что из следующего верно для преемника inorder, необходимого в операции удаления?
(A) Inorder Successor всегда является листовым узлом
(B) Преемник преемника всегда является либо листовым узлом, либо узлом с пустым левым потомком
(C) наследник преемника может быть предком узла
(D) Преемник преемника всегда является либо листовым узлом, либо узлом с пустым правым потомком

Ответ: (Б)
Объяснение: Пусть X будет удаляемым узлом в дереве с корнем в качестве «корня». Есть три случая для удаления

1) X — это листовой узел: мы меняем левый или правый указатель родителя на NULL (в зависимости от того, является ли X левым или правым потомком своего родителя) и удаляем X
2) Один дочерний элемент X пуст: мы копируем значения непустого дочернего элемента в X и удаляем непустой дочерний элемент.
3) Оба потомка X непустые: в этом случае мы находим преемник неупорядоченного X. Пусть преемником неоправданного является Y. Мы копируем содержимое Y в X и удаляем Y.

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

Рекомендуемые посты:

Структуры данных | Двоичные поисковые деревья | вопрос 2

0.00 (0%) 0 votes