I am looking for a data structure that could ensure at least Log(n) complexity for deletion and insertion of a node and something close to O(1) or amortized Log(n) to search the maximum (or minimum) value.
I was thinking to use a self-balanced BST (which one?) modified to sort of remember the maximum (or minimum) value inserted.
Any suggestion?
Sorry I have to edit the question...of course a self-balanced BST can allow to search max and min in log(n), but I was thinking about something more toward O(1).
You can use just about any self-balancing BST (e.g. red-black, AVL).
If you keep track of the minimum and maximum, the queries to get them will take O(1).
Since the minimum and maximum can only change on insertions and deletions, you can essentially just redetermine it (in O(log n)) when doing those operations (the running time of them will still be O(log n)).
Though it's probably a better idea to just redetermine the minimum or maximum when you receive a query for it and there was an insert or delete since the last query.
It's also possible to be more intelligent about it - if you've only gone left thus far, you're at the minimum, if you've only gone right, you're at the maximum. When inserting, just replace the minimum / maximum if appropriate. When deleting, just look around in the tree from the deleted node to find the new minimum / maximum.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments