Как обновить или синхронизировать дерево из отсортированного массива в C

Question

У меня есть один отсортированный массив int и одно дерево avl. Данные массива - это исходный набор данных, а дерево формируется из элементов массива. Необходимо получить список элементов в дереве, которые отсутствуют или добавлены в исходный массив, и сделать дерево похожим на массив, удалив или добавив элемент в дерево.

Пример 1:

    int orig[5] = {10, 20, 25, 30, 40};
    ref_tree = 10, 20, 25, 30, 35, 40, 50

    Delete from tree: 35, 50

Пример 2:

    int orig[6] = {10, 20, 25, 30, 35, 40};
    ref_tree = 10, 20, 25, 35

    Add to tree : 30, 40

ПРИМЕЧАНИЕ. Если длина массивов и количество узлов дерева одинаковы, то предположим, что оба имеют одинаковый список элементов.

Я пробовал что-то вроде этого:

'''
if (array_len < node_count) {
    /*Extra element in ref array */
    while(tree_node) {
        //iterate through all nodes of tree
        bool found = false;
        for (int i=0; i<array_len; i++) {
            if (tree_node->data == orig[i]) {
                found = true;
                break;
            }
        }
        if (found == false) {
            //Data is extra in tree, so delete node to make it similar.
        }
    }

} else {
    /*Missing element from tree */
    for (i=0; i<orig_len; i++) {
        /* Calling tree find api if element is available or not*/ 
        if (find(orig[i], ref_tree) == false) {
            //Element is Missing
            //add that node from tree to make it similar
        }
    }  
}
'''

Я хочу оптимизировать код здесь.

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

2. Зацикливание несколько раз в случае обнаружения дополнительных элементов в дереве, возможно ли объединиться в один цикл и оптимизировать код любым другим способом?

3. Вместо 'if-else', возможно ли иметь общую логику, которая может обрабатывать, чтобы получить элемент, который будет добавлен / удален из дерева?

Answer 1

Вы, кажется, делаете проблему сложнее, чем нужно, по крайней мере, концептуально.У вас есть отсортированный массив, и у вас есть двоичное дерево поиска.Упорядоченный обход дерева будет посещать узлы в порядке значений, которые они содержат.Сопоставляя значения узлов, пройденные с элементами вашего списка, вы можете определить, какие значения отсутствуют в дереве, а какие лишние - даже при наличии нескольких элементов и / или нескольких узлов, имеющих одинаковое значение, и даже есликоличество значений равно количеству узлов.На каждом узле:

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

После завершения обхода любые элементы списка после последнего соответствуют или считаются соответствующими удаленным узлам.

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

1. когда вы обнаружите мутацию дерева, немедленно исправьте ее и затем перезапустите с самого начала, или
2. составьте список мутаций какВы идете и исправляете их все после завершения обхода или, конечно же,
3. после обхода, просто создайте новое дерево из вашего массива.