Language independent – use hash mapping to optimize the binary tree and insert o (1) to write to the subtree

First of all, I assume that I have missed some important things when considering this problem, but I still want to release it to see if I really haven't missed anything and use it

I have a very rewritten binary tree (about 50 / 50 between write and read). On my way home, I'm considering how to optimize this, especially to make writing faster - that's what I proposed

Considering that the operation add (T, x) of adding x to tree T first consists of find (T, x) to check whether x already exists, and in this case, it does not return the parent, so we can add it instead of one of the parent empty leaves

If we add a hash table as an intermediate cache to the add operation, what really happens when we call add (T, x) is that x is hashed and inserted into the hash map M this is it. Optimization occurs in other places where we need to find (T). Now when we search the tree, we will go to the leaf node, because X has not been inserted into the tree (it only exists in the hash map m). We hash X and compare it with the key in M to see whether it should be in the tree If it is found in M, we add it to the tree and delete it from M

This will eliminate the find (T, x) operation on add (T, x) and reduce it to add (m, x), i.e. o (1) Then (AB) – use the find (T, x) operation we performed when we first inserted the node

Solution

Why not use a hash table for everything and omit the binary tree altogether?

It all depends on why you use a binary tree first If you choose binary tree to enhance sharing, the hash table cache will be lost because the hash table will not be shared

Caching does not make it easier to compare two maps

Edit:

If there are few operations that take advantage of the particularity of the tree (you mentioned the sorting fact of using RB tree), on the other hand, if you often find the recently added key or change the value of the recently added key, it may be meaningful to use a small cache implemented by other structures You can also consider using a hash table representation, occasionally converted to a tree

The additional complexity of this cache layer may mean that you don't get any time in practice, or it's not enough to pay off the technical debt with such temporary data structures