Phonebook using a trie

Question

I implemented a PhoneBook utilizing a Trie data structure.

Could I ask you to evaluate it?

Did I apply Trie correctly for such case or is it better to store data somehow else?

I'm looking not only for working solution but also for an optimal one in terms of run-time and storage.

From my calculations, it takes NlogT to add() and get() where N is a number of chars and T is a number of children.

Am I right?

Here is the logic

public final class PhoneBook {

    private final Node name;

    private final Node surname;

    private final Comparator<Record> comparator;

    public PhoneBook() {
        this.name = new Node();
        this.surname = new Node();
        comparator = (r1, r2) -> {
            int result = r1.getName().compareTo(r2.getName());
            if (result == 0) {
                result = r1.getSurname().compareTo(r2.getSurname());
                if (result == 0) {
                    result = r1.getNumber().compareTo(r2.getNumber());
                }
            }
            return result;
        };
    }

    public void add(final Record record) {
        add(record.getName().toLowerCase(), record, name);
        add(record.getSurname().toLowerCase(), record, surname);
    }

    public SortedSet<Record> get(final String prefix) {
        final String lc = prefix.toLowerCase();
        final List<Record> recordsRetrievedByName = get(lc, name);
        final List<Record> recordsRetrievedBySurname = get(lc, surname);
        final SortedSet<Record> result = new TreeSet<>(comparator);
        result.addAll(recordsRetrievedByName);
        result.addAll(recordsRetrievedBySurname);
        return result;
    }

    private List<Record> get(final String prefix, final Node ancestor) {
        Node node = ancestor;
        for (final char c: prefix.toCharArray()) {
            final Node child = node.children.get(c);
            if (child == null) {
                return Collections.emptyList();
            }
            node = child;
        }
        return node.records;
    }

    private void add(final String str, final Record record, final Node ancestor) {
        Node node = ancestor;
        for (final char c: str.toCharArray()) {
            final Node child;
            if (node.children.containsKey(c)) {
                child = node.children.get(c);
            } else {
                child = new Node();
                node.children.put(c, child);
            }
            child.records.add(record);
            node = child;
        }
    }

    private static final class Node {

        private final Map<Character, Node> children = new TreeMap<>();

        private final List<Record> records = new ArrayList<>();

    }

}

And the Record immutable object

public final class Record {

    private final String name;

    private final String surname;

    private final String number;

    //constructor, getters, toString
}

Answer 1

Naming:

name and surname are somewhat unclear in what they specifically mean. The "actual" purpose of these variables is to serve as "root" of the trie. Incidentally I'd rename ancestor to rootin all the usages in your code, simply because I'm more used to it. YMMV :)
I'd rename name and surname to nameRoot and surnameRoot.

Simplifications:

• Initialize private fields that are not dependent on constructor arguments in the field declaration to save on space and complexity.
• Use Comparator.comparing and thenComparing to simplify your comparator.

I personally also prefer to not leave too much space between fields.

private final Node name = new Node();
private final Node surname = new Node();
private static final Comparator<Record> comparator = Comparator.comparing(Record::getName)
    .thenComparing(Record::getSurname).thenComparing(Record::getNumber);

Note that I also changed the comparator to be static. It could also do with a better name, but I'm coming up empty right now...

Possible Trie Optimizations:

Currently your trie is using a lot of memory. It's not quite as bad as it could be, but considering that names are very much non-uniform, you will have a lot of "degenerated branches", where the branching factor is very low, if not 1 for "long" stretches of the data structure.

These long stretches of basically linked lists can be collapsed by sacrificing a WORD of memory to store how many characters you can skip before the next actual branching.

Currently Node does not support this in any way.

---

The traversal during add can be simplified a bit with computeIfAbsent like so:

for (final char c: str.toCharArray()) {
    final Node child = node.children.computeIfAbsent(c, Node::new);
    child.records.add(record);
    node = child;
}

This simplification pretty quickly vanishes when you implement the optimization mentioned above (or rather it becomes somewhat complicated).