Поиск общего узла с ключом между двумя разными BinarySearchTrees - PullRequest
Новая
       36

Поиск общего узла с ключом между двумя разными BinarySearchTrees

0 голосов
/ 24 октября 2018

В настоящее время я пытаюсь написать методы, которые проверяют все узлы в двух разных деревьях двоичного поиска и находят узлы с общими ключами между двумя деревьями.(т.е. пытается найти узел из дерева 1 и узел из дерева 2, содержащий те же ключи. Если общий узел найден, метод возвращает значение true, в противном случае он возвращает значение false. Второе дерево хранится в другом объекте, чем дерево1, называется GraphicalObject. И ключ в форме координат и сравнения размеров выполняется с использованием порядка столбцов.

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

1) Метод, который проверяет, совпадает ли узел дерева 1 с каждым узлом дерева 2, используя рекурсивные вызовы.метод compareTo определяется иначе, где. 

public boolean findPixel(BinaryNode node1, BinaryNode node2, GraphicalObject gobj) {
    //Creating the final coordinate key by altering the original key in nodes of tree 2.
    int xCor = node2.getData().getLocation().xCoord() + gobj.getOffset().xCoord() - graphicPos.xCoord();
    int yCor = node2.getData().getLocation().yCoord() + gobj.getOffset().yCoord() - graphicPos.yCoord();
    Location newLoc = new Location(xCor, yCor); //Creates the final key to be checked up on
    if(node1.getData().getLocation().compareTo(newLoc) == 0) { //If keys are the same
        return true;
    } else {
        if(node1.getData().getLocation().compareTo(newLoc) == -1) { //if key from node 1 is smaller than key from node 2.
            node2 = node2.getLeft();
            findPixel(node1, node2, gobj);
        } else {
            node2 = node2.getRight();
            findPixel(node1, node2, gobj);
        }
    }
    return false; 
}

2) Метод, использующий метод findPixel для проверки каждого узла в дереве 1 и сравнения их с каждым узлом в дереве 2, используя обход по порядку.

private boolean findCommonNode(BinaryNode node1, BinaryNode node2, GraphicalObject gobj) {
    if(node1 != null) {
        findCommonNode(node1.getLeft(), node2, gobj);
        return findPixel(node1, node2, gobj);
        findCommonNode(node1.getRight(), node2, gobj);
    }
}

3) метод, который возвращает true, если общий узел между двумя деревьями найден, или false в противном случае. 

public boolean intersects(GraphicalObject gobj){
    BinaryNode tempNode = newTree.getRoot();
    BinaryNode tempNode2 = gobj.getTree().getRoot();
    if (findCommonNode(tempNode, tempNode2, gobj) == true) {
        return true;
    } else {
        return false;
    }
}

Что-то не так с этим кодом?Или я могу что-то сделать, чтобы сделать его лучше или работать эффективнее?

1 Ответ

0 голосов
/ 24 октября 2018

В вашем коде есть пара вещей, которые кажутся неправильными:

В первом методе, который вы вызываете рекурсивным вызовом findPixel - вам нужно вернуть ответ метода обратно.Это должно быть так: 

} else {
    if(node1.getData().getLocation().compareTo(newLoc) == -1) 
        return findPixel(node1, node2.getLeft(), gobj);
    else
        return findPixel(node1, node2.getRight(), gobj);
}
return false;

Вы также должны добавить проверку для null для node2 перед извлечением местоположения.Добавьте это в первую строку функции findPixel: 

if (node2 == null)
    return false;

Во втором методе вы используете оператор return внутри функции ->, поэтому вы не получите обход по порядку, но он проигнорирует правую частьдерево.Этот код должен выглядеть следующим образом: 

if(node1 != null) {
    return (findCommonNode(node1.getLeft(), node2, gobj)) ||  (findPixel(node1, node2, gobj)) || (findCommonNode(node1.getRight(), node2, gobj));
}

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

Последнее,Третий метод может быть изменен на (удобочитаемость): 

BinaryNode tempNode = newTree.getRoot();
BinaryNode tempNode2 = gobj.getTree().getRoot();
return (findCommonNode(tempNode, tempNode2, gobj));

Это для вашего заданного кода.

Однако, более оптимистичным решением будет переход по одному дереву и вставка туда значения (после хеша).) в хэш-карте - затем пройти по второму дереву и для каждого узла: проверить, существует ли он в хэш-карте.это будет O(n) сложность в отличие от вашего решения, которое O(n^2).

Надеюсь, эта помощь!

...