CODEWITHSUNDEEP
algorithmdata-structuresbinary-search-tree
Xinrui Ma
Xinrui Ma

Reputation: 2105

Searching on Multiple Fields using BST

Suppose we need to create an address book that can provide search functionality on multiple fields, with a large number of records. The structure is very simple – name, phone number and city name.

I can type "begin with Ron..." or "begin with 202..." or "begin with Arling..."

Then it will give me the expected results.

First solution come up to my mind is, create three BST, one based on phone number, one based on name, the third one based on city.

NOW I AM THINKING, is there a way to create one BST (or any other methods), but still make the search work, without sort it every time?

Thanks in advance.

Upvotes: 2

Views: 1652

Answers (1)

Jim Mischel
Jim Mischel

Reputation: 133995

You could do it with a single BST. The BST node would be:

class BSTNode
{
    string Key;
    byte KeyType; // 0=Name, 1=City, 2=Phone
    AddressRec Record;
}

And the AddressRec is of course a reference to the actual address record.

You end up having three entries in the BST for each record. So given an address record:

rec0 = { Name = "Jim", City = "Austin", Phone="512-555-1212" }

You would add the records:

BST.Add(rec0.Name, 0, rec0);
BST.Add(rec0.City, 1, rec0);
BST.Add(rec0.Phone, 2, rec0);

And your search would take the record type as a parameter.

This is easier to manage in that you only have one BST, but searching is going to be a little slower, but by a constant factor. Search in a BST is O(log n), and your combined BST is going to have three times as many nodes as the three special-purpose trees. Still, it's not linearly slower. That is, if you have 1,024 address entries then each of your special-purpose trees will have 1024 nodes. log2(1024) is 10. Your single tree will have 3,072 nodes. log2(3,072) is 11.58. So individual searches will be slightly slower.

Note, though, that it's slightly slower by a constant factor. Consider this table:

   n   log2(n)   log2(3n)
  16      4        5.58
 128      7        8.58
1024     10       11.58
2^20     20       21.58

On average the single tree will require approximately two extra probes per search, regardless of how many items are in the BST.

Upvotes: 5

Related Questions