Decision tree (?) reduction

Question

I need to check certain conditions (of size n) on an object and perform one of several options available (size m) based on the result. Seems to me it fits a tree.

Now. The tree is quite large and I wonder if there's a way to reduce it.

Here's a sample of it

The conditions are marked as c1,...,cn and the functions to perform are marked as f1,...,fm (the crossed zeros are dont-care values)

Answer 1

Indeed, a tree is a good data structure for that. You can then create a BST which will allow to find by lookup a specific action based on the c₁ to c_n conditions.

Obviously, this has a huge benefit of avoiding ugly code such as:

if (c1) {
    if (c2) {
        if (c3) {
            ...
        }
        ...
    }
    ...
}

Whether the BST can be simplified even more depends on the exact association between the conditions and the actions. Look for a pattern. Imagine what would happen if you put c₁ after c₂.

How do I search for the action?

If you express your conditions as an array of n elements [c₁, c₁, ⋯ c_n], you can then search for the action either recursively or iteratively. For instance, a recursive approach would look like this:

var findAction = function (conditions, node) {
    // `shift` also removes the element from the array.
    var currentCondition = conditions.shift();

    if (typeof node !== 'boolean') {
        return node;
    }

    return findAction(conditions, node[currentCondition]);
}

which can be called like this:

var conditions = [false, false, true, false];
var tree = {
    true: {
        true: f1,
        false: {
            true: f2,
            false: f1
        }
    },
    false: {
        true: {
            true: f5,
            false: f3
        },
        false: {
            true: {
                true: f2,
                false: f6
            },
            false: f4
        }
    }
};


findAction(conditions, tree)(); // Will execute `f6`.

The Karnaugh map seems much easier...

It is, but it also has a limitation: all your leafs should be at the same depth. This is actually the case in the table you've shown, but may not necessarily be the case in the real problem you are attempting to solve.

If, for instance, some nodes are two levels deep while others are eight levels deep, with Karnaugh map, you have to align them to be eight levels deep, which will probably result in severe duplication (but not necessarily in reduced maintainability; it may actually be that maintainability will only increase). With a BST, you don't have to do that.

A simplistic example of the following BST:

var tree = {
    true: {
        true: f1,
        false: {
            true: {
                true: f2,
                false: f3
            },
            false: f4
        }
    },
    false: f5
};

will be expressed like this Karnaugh map:

var tree = {
    true: {
        true: {
            true: {
                true: f1,
                false: f1
            },
            false: {
                true: f1,
                false: f1
            }
        },
        false: {
            true: {
                true: f2,
                false: f3
            },
            false: {
                true: f4,
                false: f4
            }
        }
    },
    false: {
        true: {
            true: {
                true: f5,
                false: f5
            },
            false: {
                true: f5,
                false: f5
            }
        },
        false: {
            true: {
                true: f5,
                false: f5
            },
            false: {
                true: f5,
                false: f5
            }
        }
    }
};