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 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…