c - 如何从 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. 遍历结束后，只需从数组中构建一棵新树即可。