Why should I use a binary tree when hash tables exist?

Why should I use a binary tree when hash tables exist?

interview questions

Binary trees are a foundational structure, you don't use them directly. They just provide a simple foundation to build other structures out of.

Because you will use them for different things.

To plant seeds and grow plants like Gentoo

Yeah that tree is wrong. The fact that you used that image shows how little you know about binary trees, no wonder you're asking stupid questions. Either that or trolling.

Binary not binary search tree you dumbass

>binary search trees are the only binary trees there are

Is this a Linux thing?

Jesus baiting newfags is so easy. Get out of my Sup Forums queers.

Who said those are the search keys?

>merely pretending to be retarded
Your posting structure looks like some douchey kid wrote it anyway

>it was merely an act
kys

...

And you're the actual idiot or the one originally pretending?

7 nibs = 1 bite

Nothing about that quote implies that those are the only two groups.

Different data structures for different purposes.

>Why would I use a car instead of a television?

Nothing about that quote implies that there are other groups exist either. With your logic, I bet you're the kind of person to believe in gods and fairies.

>actually thinking Descartes came up with that quote
>not realizing that it was some IRC fag

How do you search for a value in a hash table without looking at each key?

How do you even know the range of keys in the table?

Indexes in databases ? searching through Olog(n) results instead of O(n).
>I don't even understand how do you compare this to hash tables?

this

trie

It's faster to do a brute force search unless you have millions of nodes. Its speed is also irrelevant unless its constantly running in some kind of loop.

(you)

Poo in loo detected

As all of the people here have no clue what they're talking about, here is an actual answer for OP:

- Binary trees are much more memory efficient. For a hash table you have to reserve memory in the first place, even though you might only insert few elements. Enlarging a hash table is a very expensive operation to do.
Many database systems have an option to either use B-tree or hashing for searching elements, depending on your data use case.

- You can traverse binary trees in a list fashion. You can't do that with hash tables.

Case closed.

O(1) is expected with most hash table implementations, with the worst case O(n) only being reached with a purposefully degenerative hash function or collision attack

Do you even know what a fucking hash table is?

> given a,b find all records t such that a < t < b

You shouldnt. You should use a self balancing tree.

Binary trees are better before returning values within ranges specifically (i.e all data between two diff years). The worst case search time in a self balancing tree is o logn.

A hash table, depending on how its implementing can be less space efficient (holding 'deleted' values if not linking in collisions) but its lookup is o (1).

Realistically you can use both and many more data structures for different aspects of an application. Whos to say you cant have a binary tree of memory addresses pointing to individual hash tables? Or vise versa?

>- Binary trees are much more memory efficient. For a hash table you have to reserve memory in the first place, even though you might only insert few elements.
Hash tables only need about 25% headspace to retain O(1) performance. There's no reason to run more than 100% headspace unless your hash table algorithm is really primitive, or you just know ahead of time how many elements it will have.

>Enlarging a hash table is a very expensive operation to do.
Not as expensive as you might think. A Perfect Hash Table is O(sqrt(N)) to resize, and is cache & virtual memory optimal. Rebalancing a binary tree is much more expensive than the theoretical limits would lead you to believe, because they have such asstastic locality during the rebalancing phase that for any interesting tree you're pretty much guaranteed to thrash the cache and page tables.

>- You can traverse binary trees in a list fashion. You can't do that with hash tables.
Sure you can. You just can't efficiently traverse a hash table in key order. But if you don't need that, then even a trivial traversal of a hash table is cache & virtual memory optimal.

You have memory overhead for a binary tree too. The only structure with no memory overhead is a list. If I'm only rarely inserting why should I use a binary tree rather than a list that is kept sorted? The only downside is that with the list insertion is O(N).

>A Perfect Hash Table is O(sqrt(N)) to resize

how the fuck? For one thing, resizing anything is O(N) because you have to copy the old memory to the new memory, the only way around it is to amortize so you only have to resize less often. For another thing, a hash table isn't "perfect" unless the keys are part of a known closed set when the hash function is chosen, so you never will resize it.

Anyway, a tree stored as the classic "nodes with pointers" diagram has shit locality for *every* phase, but you can store a balanced tree like this and get better locality and less storage overhead (the "pointers" are implied by the array index).

Sorry user, you need to study your data structures books some more.

The Perfect Hash structure is a 2-level hash table; the top-level hashtable contains either a key/value pair (if there are no collisions at that spot) or a pointer to another hashtable (if there are collisions). The two levels of the hashtable use different hash functions that are linearly independent, ensuring that hash values in the second level are no more likely to collide than random values. The resize logic ensures that the sub-tables are on average sqrt(N) size, thus the top level hash table will also be sqrt(N) size.

Access is still O(1) since at most 2 probes need to be done. The primary table requires at most one probe (the first probe gets you to either the requested key, or the table containing it), and the secondary tables are written so that they grow on first collision, ensuring that they are collision-free, so at most one probe needs to be done there.

A full-hashtable resize is O(n), but this only needs to happen when the hashtable size grows from N to N^2; so the amortized cost of the full-table resize is O(1/N) -> O(1). The resize cost for a secondary table is O(M) - but M is approx N^0.5, so it's O(N^0.5), so the amortized resize cost for the secondary tables is O(1). Amortized resize cost for both levels is therefore O(1).

The Perfect Hash table is an important data structure for implementing more advanced structures like Van Emde Boas trees (which have O(lg lg N) insertion/lookup time, and O(1) prev/next time).

I have no idea what these things are

You should use MongoDB to store data

It's web scale

You still need a tree for hash collisions.

>what is open assessing
>what is chaining (you usually use a linked list, not a binary tree)

O(1) to do what?

what if I want to do a k-nearest neighbors query?

Friendly reminder that this board is not for discussing nerd shit like data structures and algorithms.

Pic highly related.

Fun fact: That was me who said that and I'm still here.

Remember: every data structure thread is one less thread about GPUs

This board is for consumer electronics.

>said by a shemale-looking idiot

no it isn't. it's never been for consumer electronics. i've been on here for, shit, 9 years now.

any thread not about desktops, ffs nowadays WATCHES, HEADPHONES (kys), Desktops, and smartphones is chemo

O(1) to do a key search. If you want k nearest neighbors then you need a different structure. If you have a small dataset snd like being slow then a binary tree will do. If you have a big dataset and you want it to be fast, then you want a van Emde Boas tree (O(lg lg N) lookup, then O(k) for the k nearest neighbors) - and vEB trees are built on top of hash tables.

Pic related. It's Peter van Emde Boas.

>been here longer than Sup Forums has been a tech board
9 years ago, Sup Forums was Sup Forumsuro.