Data structure in C++ or C

Rosario19

unread,

Jun 20, 2018, 11:11:16 AM6/20/18

to

does exist one data structure that if N is the number of elements in
it it has at last O(log(N)) for insert and O(log(N)) for search?

i think could be ok binary tree, i wrote something for that
and seems ok; but binary tree admit the insert of duplicate elemnts?
it seems yes but possible here i think wrong...

it would be one hash table too
but tipically it has to have its N as 1_000_000 of elements or
16_000_000 of chars in a pc that has not too much memory...

It would be possible using hash tables for big number of elements to
save?

Robert Wessel

unread,

Jun 20, 2018, 1:13:02 PM6/20/18

to

On Wed, 20 Jun 2018 17:15:59 +0200, Rosario19 <R...@invalid.invalid>
wrote:

Some sort of binary tree will have those performance requirements. But
you'll want to pick a type that's self-balancing. Red-black trees are
a fairly simple, and popular, choice.

Some tree structures can handle duplicate keys, others can't, but even
the ones that can't, can be adapted by adding a sequence number to
each element, and using that as the low part of the key.

red floyd

unread,

Jun 20, 2018, 1:58:48 PM6/20/18

to

Please do your own homework.

This is also off-topic for comp.lang.c++.

Juha Nieminen

unread,

Jun 21, 2018, 3:35:35 AM6/21/18

to

Rosario19 <R...@invalid.invalid> wrote:
> does exist one data structure that if N is the number of elements in
> it it has at last O(log(N)) for insert and O(log(N)) for search?
>
> i think could be ok binary tree, i wrote something for that
> and seems ok; but binary tree admit the insert of duplicate elemnts?
> it seems yes but possible here i think wrong...

std::set or std::map for unique elements, std::multiset or std::multimap
for repeated elements.

Rosario19

unread,

Jun 22, 2018, 2:37:42 PM6/22/18

to

i read all this code on "red-black" binary tree
but it seems to me too much conplex...
even normal code for tree it seems to me too much complex...

i like normal binary tree, that gets its input in random form

i has to have one limitation, it is easier than i write the right code
alone, [better if read something general and not particular] better
than copy or adact some code seen in one book

red floyd

unread,

Jun 22, 2018, 5:10:06 PM6/22/18

to

Straight up binary trees have an O(N) worst case. Try creating one
with an ordered sequence (e.g. 1, 2, 3, 4, 5, 6, 7, ...). You wind up
with a linked list.

Vir Campestris

unread,

Jun 22, 2018, 6:15:21 PM6/22/18

to

On 22/06/2018 19:42, Rosario19 wrote:
> i read all this code on "red-black" binary tree
> but it seems to me too much conplex...
> even normal code for tree it seems to me too much complex...

I read what set and friends do, and don't worry about the
implementation. Using them is easy.

Perhaps one day I'll be writing a new STL library - but it seems pretty
unlikely. Until that day I won't need to know how it works, only how it
behaves. Which is O(log N).

(I did have to wrote a hashmap ~5 years back. Because it needed to be in
C - which of course doesn't have STL)

Andy

Rosario19

unread,

Jun 23, 2018, 1:23:29 AM6/23/18

to

yes what about put first 100 in a buffer and random swap them just
first than insert them all in the binary tree?

so the data container is a buffer, and a binary tree

Rosario19

unread,

Jun 23, 2018, 1:28:55 AM6/23/18

to

there are good sides and wrong sides in rewrite something

wrong sides are that they could be wrong, or slow in some fundamental
case...the workaroung on this is find the right test using rand()
function
the good side is that code drive itself in what it is useful, and one
can modify all or follow the path code show be ok

>Andy