Thread: binary tree question

Well a billion is about 2³⁰
So in an ideal binary tree, you would need 30 comparisons to traverse from root to tip.

What you also need is a hash function which turns your address record (or some part of it) into a unique number. A number is good, as they can be typically compared in a single machine cycle.

Choosing a good hash function is key, so that all possible address records are evenly distributed. You don't want massive clumps of similar records being stored under the same hashed value.

Comparing 30 strings would take almost no time as well.

Let's say hypotetically I have billion contacts and program must find that right one to acquire integer, doesn't it take too much time? What is the process behind comparing inserted strings with strings in memory?

Consider that a good desktop machine might have say 16GB of memory.
How much usable data per record do you think you'll have?

I assume your address book can be modeled as a function from names (string) to addresses (strings). If your address book should always be sorted, then a binary tree might be more efficient. However, using a balanced binary tree will require up to log_2(n) potentially expensive name string comparisons when accessing an address by name from the book. A better solution is to use a hash table, which is O(1) (constant time) lookup, insertion, and removal -- given that you can provide an way to convert the name strings to integers such that the integers are evenly distributed over the range of integers.. If your name-hashing function just return the ASCII or Unicode character value of the first character in the name, then all names that start with "D", for example, your O(1) performance will quickly devolve into an O(N) one...