Ytdyklly

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

}