std::map rebalancing

[bol...@nowhere.co.uk]

Morning

I'm finding it hard to find out if/how/when the standard map rebalances
itself after deletions. Does it happen after every erase or only after a
certain amount of imbalance occurs? When it does happen how long does it
take and is there a way to force it to happen?

Cheers

[Bonita Montero]

Am 15.06.2020 um 11:10 schrieb bol...@nowhere.co.uk:
> Morning
> I'm finding it hard to find out if/how/when the standard map rebalances
> itself after deletions. Does it happen after every erase or only after a

> certain amount of imbalance occurs? ...

Try an app which simulates a red-black-tree on the web:
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

I don't like red-black-trees. They've superior performance when
there are as equal inserts / deletes as find-operations, but if
the later operations are more frequent AVL-trees become superior.

[Sam]

This is not specified in the standard, and there are no specified ways to
force a rebalance.

[bol...@nowhere.co.uk]

On Mon, 15 Jun 2020 07:00:17 -0400
Sam <s...@email-scan.com> wrote:
>This is a MIME GnuPG-signed message. If you see this text, it means that
>your E-mail or Usenet software does not support MIME signed messages.
>The Internet standard for MIME PGP messages, RFC 2015, was published in 1996.
>To open this message correctly you will need to install E-mail or Usenet
>software that supports modern Internet standards.
>
>--=_monster.email-scan.com-45391-1592218817-0001
>Content-Type: text/plain; format=flowed; delsp=yes; charset="UTF-8"
>Content-Disposition: inline
>Content-Transfer-Encoding: 7bit

Hmm. So in other words if you have a huge map with millions of entries you
could suddenly find your program grinds to a halt for a while when you do an
insert or delete. Thats less than ideal.

[Juha Nieminen]

bol...@nowhere.co.uk wrote:
> Hmm. So in other words if you have a huge map with millions of entries you
> could suddenly find your program grinds to a halt for a while when you do an
> insert or delete. Thats less than ideal.

Not really, since even if your map had a hundred million entries,
the rebalancing would perform operations to about 27 nodes (or perhaps
about double that, as it probably also does something to the other
child node of each of those nodes, so it does something to something
like 54 nodes or so.)

Your program isn't going to "grind to a halt" because the rebalancing
does some minor adjustments to about 50 nodes in your 100-million-node
tree.

[Ian Collins]

Have you learned how to count to three yet?

--
Ian.

[bol...@nowhere.co.uk]

If you think a major rebalance would only involved updating 3 nodes then
you have no idea how balancing works.

[Ian Collins]

I thought not.

--
Ian.

[bol...@nowhere.co.uk]

On Tue, 16 Jun 2020 21:21:24 +1200

Ian Collins <ian-...@hotmail.com> wrote:
>On 16/06/2020 21:04, bol...@nowhere.co.uk wrote:
>> On Tue, 16 Jun 2020 18:06:34 +1200
>> Ian Collins <ian-...@hotmail.com> wrote:
>>> On 15/06/2020 21:10, bol...@nowhere.co.uk wrote:
>>>> Morning
>>>>
>>>> I'm finding it hard to find out if/how/when the standard map rebalances
>>>> itself after deletions. Does it happen after every erase or only after a
>>>> certain amount of imbalance occurs? When it does happen how long does it
>>>> take and is there a way to force it to happen?
>>>
>>> Have you learned how to count to three yet?
>>
>> If you think a major rebalance would only involved updating 3 nodes then
>> you have no idea how balancing works.
>
>I thought not.

You know there's this very useful tool called Google, you might want to
find out about it. In the meantime here's a useful page with a nice example
of a small 11 node tree before and after balancing. I suspect even a
beginner like you will be able to see that more than 3 node updates had to
happen to achieve that:

https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

HTH

[Juha Nieminen]

Rebalancing a binary tree (such as a red-black tree) requires updating
O(log(n)) nodes. Most usually approximately 2*log(n) nodes (no big-O).

So if your tree has 100 million nodes, rebalancing it after an insertion
or deletion requires updating about 54 nodes (give or take).