Удаление узла из презентации arrayList <String> - PullRequest
Новая
       4

Удаление узла из презентации arrayList <String>

0 голосов
/ 03 марта 2020

У меня проблема с реализацией метода удаления BST. МассивList находится на уровне обхода порядка, который включает в себя все узлы, даже нули. Например 

    toBSTArray = [20,3,2] -> BSTArray<String> = ["20","3","null","2","null","null","null"]

Это то, что я получил до сих пор 

        public void deleteFromStr(ArrayList<String> arr, String delVal){
        int i = 0;
        int leftChild, rightChild, parent;
        String node,leftChildStr,rightChildStr,parentString;
        while(!(arr.get(i).equals(delVal))){
            i++;
        }
        node = arr.get(i);
        leftChild =(2*i + 1);
        rightChild= (2 * i + 2);
        parent = (i - 1)/2;
        leftChildStr = arr.get(leftChild);
        rightChildStr = arr.get(rightChild);
        parentString = arr.get(parent);
        if(leftChildStr.equals("null") && rightChildStr.equals("null"))
            arr.remove(i);
    }

1 Ответ

1 голос
/ 03 марта 2020

Две вещи:

  1. у вас есть представление с прямой индексацией, вы не можете фактически удалить узлы из середины списка, вы можете установить их только на "null" (я бы предпочел рассмотреть используя null, кстати)
  2. в двоичном дереве поиска (независимо от его представления) удаление узла имеет несколько случаев в зависимости от его дочерних элементов

Если дочерних элементов нет, Вы можете просто удалить узел (null это). Эта часть есть в вашем коде, просто она не должна быть remove(): 

if(leftChildStr.equals("null") && rightChildStr.equals("null"))
    arr.set(i,"null"); // instead of arr.remove(i);

Если один дочерний элемент null, другой должен быть перемещен вверх со всем своим поддеревом.
Я мог бы представить себе рекурсивную вспомогательную функцию для этого: 

void moveup(ArrayList<String> arr,int from,int to){
    if(from>=arr.size()){
        arr.set(to,"null");
        return;
    }
    String nodeString=arr.get(from);
    arr.set(to,nodeString);
    if(!nodeString.equals("null")){
        moveup(arr,from*2+1,to*2+1);
        moveup(arr,from*2+2,to*2+2);
    }
}

(Это moveup, потому что он не проверяет слишком большой to и не пытается расширить список)
Тогда случаи (продолжая if сверху): 

else if(leftChildStr.equals("null"))
    moveup(arr,rightChild,i);
else if(rightChildStr.equals("null"))
    moveup(arr,leftChild,i);

И есть окончательный else для обработки присутствия как левых, так и правых детей. Это сложно, на самом деле я не хочу думать об этом, но Википедия имеет некоторое представление:

Удаление узла с двумя детьми: вызовите удаляемый узел D. Не удаляйте D. Вместо этого выберите либо узел-предшественник по порядку, либо его узел-преемник по порядку в качестве узла замены E (см. рисунок). Скопируйте пользовательские значения E в D. [примечание 2] Если E не имеет дочернего элемента, просто удалите E из своего предыдущего родителя G. Если E имеет дочерний элемент, скажем F, это правильный дочерний элемент. Замените E на F у родителя E.

В сочетании с иллюстрацией:

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

...