java - Generating an always balanced binary seach tree only true insertion

Question

So i was thinking of a problem i find very interesting and i would like to share the concept of this, the problem starts of with an hypotetical data structure you define (it can be a list, array, tree, binary search tree, red black tree, Btree, etc.), the goal of this is obviously to optimize insertion, search, delete and update (but you can consider this as a search with replacement), the time complexity has to be has low as possible for every single type of operation (possibly O(1) or O(log(n) try to not use a solution of O(n)) the second part of the problem is that this structure during a normal day of work receives new elements with a key of increasing value starting from 1 to N where N can be Long.MAX_LONG, obviously when a new key is given it has to be inserted immediately so it will go as follows:

[1,2,3,4,...,N]

I think i am close to the solution of this problem but i am missing a little bit more of optimization, i was thinking of using either a Tree or a Hashtable but in the case of Hashtable there is a problem when N becomes very high it's needed to rehash the entire structure or the complexity would become O(n), this however is not a problem with a Tree but i think it may become a sequence of elements (keep in mind that we have to put every new element when it comes) like this:

And in this case you can clearly see that this Tree is not just a Tree it's a List, using a BST would give the same result. I think the correct structure to use is the BST (or something like it for example Red Black Tree) and find a way to always have it balanced, but i am missing something.

question from:https://stackoverflow.com/questions/65901006/generating-an-always-balanced-binary-seach-tree-only-true-insertion

Answer 1

If the "key" is an integer and the key are generated by incrementing a counter starting from 1, then the obvious data structure for representing the key -> value mapping is a ValueType[]. Yes, an array.

There are two problems with this:

1. Arrays do not "grow" in Java.

   Solutions:

   1. Preallocate the array to be big enough to start with.
   2. Use an ArrayList instead of a array.
   3. "Borrow" the algorithm that ArrayList uses to grow a list and use it with a bare array.

2. Arrays cannot have more than Integer.MAX_VALUE elements. (And ArrayList has the same problem.

   Solution: use an array of arrays, and do some arithmetic to convert the long keys into a pair of ints for indexing the arrays.