Какова сложность Big-Oh этого общего метода дерева? - PullRequest
Новая
       41

Какова сложность Big-Oh этого общего метода дерева?

0 голосов
/ 07 ноября 2019

Меня попросили реализовать метод, который удаляет из (не бинарных, n-арных) узлов дерева, которые имеют высоту заданного значения K, и только одного дочернего элемента. Это моя реализация:

Это функция высоты узла дерева, хотя я знаю, что это O (n), я не совсем понимаю, почему. 

private int height(Position<E> pos) throws InvalidPositionException { // O(n)
        //Inicia un valor antes del try para evitar que no se inicie.
        TNode<E> nodo = null;
        int maxHeight = 0; 
        try {
            nodo = checkPosition(pos);          //Casteo
            } catch (InvalidPositionException e) {
                e.printStackTrace();
            }
        if (isExternal(nodo)) {
            return 0;
        }
        else {
            for (TNode<E> aux : nodo.getChildren()) {
                int auxHeight = height(aux);
                if (auxHeight > maxHeight) {
                    maxHeight = auxHeight;
                }
            }
            return 1+maxHeight;
        }   
    } 

private TNode<E> checkPosition(Position<E> p) throws InvalidPositionException{
        if (p==null) throw new InvalidPositionException("Posición Inválida");
        try{
            return (TNode<E>) p; //Intenta castear
        }
        catch (ClassCastException e){
            throw new InvalidPositionException("Posición Inválida.");
        }
    }

И это сложная функция, в которой мне нужен Big-O: 

public void removerNodos(int K) throws InvalidPositionException {
        for (Position<E> pos : positions()) {
            TNode<E> nodo = checkPosition(pos);
            if ((height(nodo) == K) && nodo.getChildren().size()==1) {

                //Si el nodo que cumple las caracteristicas es la raiz, lo eliminamos.
                if (isRoot(nodo)) {
                    try {
                        root.setElement(null);
                        root.setChildren(null);
                        root = root.getChildren().first().element();
                        root.setParent(null);

                    } catch (EmptyListException e) {
                        e.printStackTrace();
                    }
                }
            //Caso contrario: ASUMO PASAJE DE HIJO AL PADRE.
            else {      
                try {
                        TNode<E> hijo = nodo.getChildren().first().element();
                        TNode<E> padre = nodo.getParent();
                        hijo.setParent(padre);
                        padre.getChildren().addLast(hijo);
                        E value  = nodo.element();

                        //Busca en la lista de posiciones de nodos del padre el elemento a
                        //eliminar, y lo quita. Operación de lista.
                        for (TDALista.Position<TNode<E>> aux : padre.getChildren().positions()) {
                            if (aux.element() == nodo) padre.getChildren().remove(aux);
                        }
                        nodo.setElement(null);
                        nodo.setChildren(null);
                        nodo.setParent(null);
                        size--; 
                        //Reducimos el tamaño del arbol.
                        //System.out.println("Se eliminó el nodo "+value+".");

                    } catch (EmptyListException | TDALista.InvalidPositionException e) {
                            System.out.println("Lista de nodos vacia, o posición inválida");
                    }       
                }
            }   
        }
    }

Если вам нужно понять имена переменных, просто прокомментируйте, и я могу их перевести.

1 Ответ

0 голосов
/ 07 ноября 2019

Прежде всего, функция height имеет временную сложность O (n) , потому что она будет выполняться только один раз на узел (передаваемый в качестве аргумента) - рекурсивные вызовы никогда не происходят дважды длятот же узел.

Основная функция removerNodos выполняется с временной сложностью, которая зависит от фактической арности узла и высоты дерева. Худший случай - O (n²) . Например, наихудший случай возникает в дереве, где у каждого узла есть один дочерний элемент, кроме одного: единственный лист - цепочка. Функция height вызывается для каждого узла, поэтому общее количество посещений узла для этого конкретного формата дерева составляет 1 + 2 + 3 + ... + n = O (n²) .

Манипуляция для удаления одного узла - O (1) , когда мы рассматриваем арность как постоянную, так что это не влияет на общую сложность времени.

Некоторыепроблемы в коде

Не ваш вопрос, но есть некоторые недостатки:

  • size не уменьшается в случае if, т.е. при удалении рута.

  • Когда вы вызываете .setChildren(null), любой последующий вызов .getChildren() вернет пустой список, и поэтому .first() не вернет дочерний узел, так как дочерние элементы были просто отсоединены и не будутвосстановлено больше. Поэтому лучше изменить следующее: 

        root.setChildren(null);
    root = root.getChildren().first().element();

    на: 

        TNode<E> hijo = root.getChildren().first().element();
    root.setChildren(null);
    root = hijo;

Улучшения

Код не очень эффективен. Вы получили бы лучшую временную сложность, если бы не вызывали height для каждого узла, но фактически выполняли бы поиск в глубину (как в функции height) и объединяли бы вычисление высоты с логикой удаления. Другими словами, используйте функцию height в качестве функции main ;добавьте к нему параметр k и реализуйте в нем логику удаления.

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

Если вы реализуете его таким образом, он будет работать в O (n) .

...